2. select the variable X (not marked Tabu) with highest error 3. evaluate costs of possible moves from X
4. if no improvment move exists then mark X as Tabu until iteration number: Iteration + T
Tabu Nb = Tabu Nb + 1 if Tabu Nb > RL
then randomly reset RP variables in V
(and unmark those which are Tabu)
else select the best move and change the value of X
accordingly to produce next configuration A'
if cost(A') < Opt Cost then Opt Sol = A'
Opt Cost = cost(A')
until a solution is found or Iteration > Max I
until a solution is found or Restart > Max R
output (Opt Sol, Opt Cost)
Adaptive Search is a simple algorithm but it turns out to be quite efficient in practice [5]. Considering the complexity/efficiency ratio, it can be a very effective way to implement constraint solving techniques in larger software tools, especially for anytime algorithms where (approximate) solutions have to be computed within a limited amount of time.

## 4 Parallel Algorithm On The Cell/Be

We will not present the Cell/BE processor architecture here, some features of this architecture, however, deserve mention because they strongly shape what applications may succeed when ported:
- A hybrid multicore architecture, with a general-purpose "controller" processor (the PPE, a PowerPC instance) and eight specialized processors (SPEs.)
- Two Cell/BE processor chips may be linked to appear as a multiprocessor with 16 SPEs.

- The PPEs are connected via a very high-bandwidth internal bus, the EIB.

- The PPEs may only perform operations on their local store, which contains both code and data and is limited to 256KB.

- The PPEs may access system memory and each other's private memory by means of DMA operations.

The interested reader can refer to the IBM Redbook [15] for further information on this architecture, as well as the performance and capacity tradeoffs which affect Cell/BE programs.

The basic idea in extending the algorithm for parallel implementation is to have several distinct parallel search engines for exploring simultaneously different parts of the search space, and to start each such engine a a different processor. This is very natural to achieve with the Adaptive Search algorithm: one just needs to start each engine with a different, randomly computed, initial configuration, that is, a different assignment of values to variables. Subsequently, each "Adaptive Search engine" can perform the sequential algorithm described in the previous section independently. As soon as one process finds a solution, or when all processors reach the maximal number of iterations allowed, all processors are halted and the algorithm finishes with the condition that led to the termination (solution found or maximum iterations reached in all processors).