
## The Parallel Algorithm

The Cell/BE processor architecture is reflected on the task structure, in which a controller thread resides in the PPE and each SPE has a worker thread.

- The PPE gets the real time T0, launches a given number of threads, each with an identical SPU
context, and then waits for a solution.

- Each SPE starts with a random configuration (held entirely in its local storage) and improves it step by step, applying the algorithm of section 3.

- As soon as an SPE finds a solution, it sends it to the main memory (using a DMA operation) and informs the PPE.

- The PPE then propagates this information to all other SPEs to stop their job and waits until all SPUs have finished (join). After that, it gets the real time T1 and provides both the solution and the execution time 1 T = T1−T0.
It is worth pointing out that SPEs do not communicate among themselves and only do so with the PPE
upon termination: each SPE can work blindly on its configuration until it reaches an outcome (solution or failure). Indeed, we managed to fit both the program and the data in the 256KB of local store of each SPU, even for admittedly large benchmarks. This turns out to be possible for two reasons: (1) the simplicity and compactness of the algorithm, (2) the compactness of the encoding of the combinatorial problem as a CSP, that is, variables with finite domains and many predefined constraints, including arithmetics. This is especially true when compared, for instance, to a SAT encoding where only boolean variables can be used and each constraint has to be explicitly decomposed into a set of boolean formulas yielding problem formulations which easily reach several thousands of literals.

To summarize, the Adaptive Search method requirements are a good match for the Cell/BE architecture: *not much data but a lot of computation*.

## 5 Performance Evaluation

We now present and discuss the performance of our implementation of AS/Cell. The code running on each SPU is derived from the code used in [4, 5] which is an implementation of the Adaptive Search for permutation problems. It is worth noting that no code specialization has been made to benefit from the full potential of the Cell processor (namely vectorization, branch removing, ...) It is reasonable to expect a significant speedup when these aspects are taken into account.

Since the Adaptive Search uses random configurations and progression, each benchmark has been executed 50 times. There are two interesting ways for aggregating those results: considering the average case (average of 50 executions times after removing both the lowest and the highest times) and considering the worst case (maximum of the 50 executions). On one hand, the former is classical and gives a precise idea of the behavior of the AS/Cell. On the other hand, the latter is also interesting for real-time applications since it represents the "worst-case" one can encounter (too high a value can even prevent the use in time-critical applications). Interestingly, AS/Cell improves both cases, achieving linear speedups and sometimes even super-linear speedups.