Prerequisites 'Solution on ParadisEO-GPU'

In this lesson, you will learn how to implement a solution on ParadisEO-GPU respecting ParadisEO specificities and GPU characteristics . As an example, it will be illustrated on the One Max problem.

1. Introduction

The OneMax Problem (or BitCounting) is a simple problem consisting in maximizing the number of ones of a bit string. Formally, this problem can be described as finding a string , with , that maximize the following equation:

2. Solution on GPU

Implementation

The GPU architecture is a large collection of multiprocessors where each of them has several arithmetic logic units (ALU). At any given clock cycle, each ALU executes the same program (one or a set of instructions) on different data by following the SIMD/SPMD models. Furthermore, each ALU has access to different memory levels.

To benefit from this architecture and facilitate its manipulation, it is strongly advised to organise the data streams to an indexed data structure to make an easy data control and assure memory coalescing (which data will be treated by which thread ...). For this purpose we have initially designed that we can represent a solution in Paradiseo-GPU as a vector of a given type.

In Paradiseo-GPU, the solution of your problem can be defined as an object with two attributes, the vector of data and its size with many methods,this solution will be used on both CPU and GPU.As a consequence, you should define at least two constructor : the default constructor that initialise the size of data vector to zero(solution used on GPU don't need to be allocated on CPU),the second constructor to initialise the size of data vector to a given value in argument.

Depending on your problem structure representation, you should implement many methods, to create a solution, to define a copy assignment operator, to get the size of the solution vector from both the host (CPU) and the device (GPU) and to define accessors (setter and getter) of the solution vector from host-device. Those methods were implemented in ''"moGPUVector"' as :

a- A read-only accessor from the host and the device on the i'th element of the structure representation

    inline __host__ __device__ const ElemType & operator[](unsigned _i) const {
     return vect[_i];
    }

b- An accessor to write on the i'th element of the structure representation

    inline __host__ __device__ ElemType & operator[](unsigned _i) {
     return vect[_i];
    }

c- An inline method to be able to get the structure size from the host and the device

    inline __host__ __device__  unsigned size() {
     return N;
    }

d- An assignment operator to determine the new content of vector

   moGPUVector& operator=(const  moGPUVector & _vector) {

	if (!(N == _vector.N)) {
		N = _vector.N;
		vect = new ElemType[N];
	}
	for (unsigned i = 0; i < N; i++){
		vect[i] = _vector[i];
	}

	if (!(_vector.invalid()))
		fitness(_vector.fitness());
	else
		(*this).invalidate();
	return (*this);

	}

N.B:You do not need to redefine those methods if your solution representation is only a vector of a given type.

To implement a solution as a vector of a specified type in Paradiseo-GPU, you must have a class that inherits from "moGPUVector" and define all pure virtual methods :

a- The method to describe your solution representation

   void create() { ... }

b- The method to set the size of vector

   void setSize(unsigned _size) { ... }

c- The method to write object

   void printOn(std::ostream& _os) { ... }

Example

In order to define an instance of the One-Max problem, we need to define a binary vector and its length N. For a given N, the optimal solution of the problem is a structure with N ones, i.e. all the bits of the string are set to one.

#include <GPUType/moGPUVector.h>

template<class Fitness>

class moGPUBitVector: public moGPUVector<bool, Fitness> {

public:

    using moGPUVector<bool, Fitness>::vect;
    using moGPUVector<bool, Fitness>::N;


    moGPUBitVector() :moGPUVector<bool, Fitness> () {

    }

    moGPUBitVector(unsigned _neighborhoodSize) : moGPUVector<bool, Fitness> (_neighborhoodSize) {
	create();
	}


    void create() {
        for (unsigned i = 0; i < N; i++) 
	      vect[i] = (int) (rng.rand() / RAND_MAX);
    }

    void setSize(unsigned _size) {

		if (_size < N) {
			moGPUBitVector<Fitness> tmp_vect(_size);
			for (unsigned i = 0; i < tmp_vect.N; i++)
				tmp_vect.vect[i] = vect[i];
			(tmp_vect).invalidate();
			(*this) = tmp_vect;
		} else if (_size > N) {
			moGPUBitVector<Fitness> tmp_vect(_size);
			for (unsigned i = 0; i < N; i++)
				tmp_vect.vect[i] = vect[i];
			(tmp_vect).invalidate();
			(*this) = tmp_vect;
		}

    }


     void printOn(std::ostream& _os) const {

		EO<Fitness>::printOn(_os);
		_os << ' ';
		_os << N << ' ';
		for (unsigned int i = 0; i < N; i++)
			_os << (*this)[i] << ' ';

     }
    }

N.B: All what you should include and declare to define your own problem solution is represented by the red color, by the blue, the dependence of your solution vector type and the base class by the green color.