
| all   | number   | perfect   | magic   |        |
|-------|----------|-----------|---------|--------|
| SPUs  | interval | partit    | square  | square |
| 450   | 2600     | 5         | 100     |        |
| 1     | 891.2    | 24.0      | 122.0   | 915.7  |
| 2     | 459.6    | 16.0      | 54.4    | 18.5   |
| 4     | 223.9    | 6.9       | 26.6    | 12.7   |
| 8     | 65.4     | 2.8       | 16.3    | 10.0   |
| 12    | 61.0     | 1.9       | 10.4    | 3.4    |
| 16    | 40.0     | 1.5       | 6.3     | 3.8    |

method can benefit easily from the Cell: when running several SPUs in parallel, the PPE simply has to ask each SPU to obtain its best pseudo-solution (together with the corresponding cost) and then to chose the best of these bests. Indeed, another good property regarding the Cell features, is the fact that the only data a SPU needs to pass is the current configuration (an array of integers) and the associated cost.

## 7 Concluding Remarks

We presented a simple yet effective initial port of the Adaptive Search algorithm to the Cell/BE architecture, which we used to solve combinatorial search problems. The experimental evaluation we carried out indicates that linear speedups are to be expected in most cases, and even some situations of superlinear speedups are possible. Scaling the problem size seems never to degrade the speedups, even when dealing with very difficult problems. We even ran a reputedly very hard benchmark with increasing speedups when the problem size grows.

An important, if somewhat unexpected, fringe benefit is that the worst case execution time gets even higher speedups than the average case. This characteristic opens up several domains of application to the use of combinatorial search problem formulations: this is particularly true of real-time applications and other time-sensitive usages, for instance interactive games.

Clearly the Cell/BE has a very significant potential to make good on combinatorial search problems. We plan to work on two separate directions: on one hand, to optimize the code as per the IBM
guidelines [15] and on the other, to experiment with more sophisticated organizations and forms of communication among the processors involved in a computation.

## Acknowledgements

The equipment used to perform the benchmarks described herein was provided by IBM Corporation, as a grant from the Shared University Research (SUR) program awarded to CENTRIA and U. of Evora. ´

## References

[1] Jiri Barnat, Lubos Brim & Petr Rockai (2007): *Scalable Multi-core LTL Model-Checking*. In: *SPIN*. pp.

187–203. Available at http://dx.doi.org/10.1007/978-3-540-73370-6_13.