Prerequisites 'Neighbor & Neighborhood on GPU'

Like in paradisEO, paradisEO-GPU separates the representation-dependent part (represention of solution, neighbor, evaluation) from the generic part (the order of neighbors generation, selection, replacement, etc.).

So, to define a local search, it is necessary to define:

  1. the solution representation (Lesson 3)
  2. the neighbor representation(see in this lesson)
  3. the neighborhood (generation of the neighbors)
  4. the evaluation function of a solution and neighbor(Lesson4)

A. Neighbor on GPU (example with a bit flipping)

Implementation

The neighbor defines how to modify a solution to compute the neighbor. For example, for the bit string, a neighbor indicates which bit is flipped.

To implement a GPU neighbor for your problem, you must have a class that inherits from "moIndexNeighbor" for the corresponding neighbors.As a consequence, in the neighbor class, you have to implement the following method:

  • move (how to modify a solution to have neighbor)

The neighbor class will be parametrized by the type of GPU solutions(moGPUVector)

Example

Here, we present how to define a move method for a neighbor related to a solution vector of Bit

    virtual void move(EOT & _solution) {
	_solution[key] = !_solution[key];
	     _solution.invalidate();
	}

B. Neighbordhoods on GPU (example with a bit flipping)

The main goal is to use a new concept of general purpose on graphics processing unit to take advantage from the computational power of the graphics card through its high parallel architecture.

For the sake of simplicity, we have chosen a simple parallel design (iterative-level) to implement neighborhoods on GPU as we intend to show you the basic principles to use ParadisEO-MO and the ParadisEO-GPU.

Implementation

To implement a GPU neighborhood for your problem, you must have a class that inherits from "moOrderNeighborhood".As a consequence, in the neighborhood class, you have to implement the following methods:

  • hasNeighbor (test if there is at least one valid neighbor)
  • cont (test if there is again a valid neighbor)
  • next (compute the next valid neighbor)
  • init ( Initialization of the neighborhood and launch a transparent parallel evaluation on GPU)

Example

As noted above, the evaluation of the neighborhood is launched at the same time of the generation of the neighborhood (initialization). The following method initializes the first neighbor and launches the evaluation of all neighbors on GPU:

    virtual void init (EOT & _solution, Neighbor & _neighbor) {
     moOrderNeighborhood<Neighbor>::init(_solution, _neighbor);
     //Compute all neighbors fitnesses at one time
     eval.neighborhoodEval(_solution);
    }

Define type of representation

    typedef moGPUBitVector<eoMaximizingFitness> Solution;

Define type of a bit flipping neighbor

    typedef moGPUBitNeighbor <solution,eoMaximizingFitness> Neighbor;

Define type of the indexed neighborhood

    typedef moGPUOrderNeighborhoodByModif<Neighbor> Neighborhood;

And in the "main" function, a neighborhood and solution are declared:

    Neighborhood neighborhood(SIZE,gpueval);
    solution sol(SIZE);