# Parallel Local Search For Solving Constraint Problems On The Cell Broadband Engine (Preliminary Results)

Salvador Abreu Universidade de Evora and CENTRIA FCT/UNL ´
Portugal spa@di.uevora.pt Daniel Diaz University of Paris 1-Sorbonne France Daniel.Diaz@univ-paris1.fr Philippe Codognet JFLI, CNRS / UPMC / University of Tokyo, Japan Philippe.Codognet@lip6.fr We explore the use of the Cell Broadband Engine (Cell/BE for short) for combinatorial optimization applications: we present a parallel version of a constraint-based local search algorithm that has been implemented on a multiprocessor BladeCenter machine with twin Cell/BE processors (total of 16 SPUs per blade). This algorithm was chosen because it fits very well the Cell/BE architecture and requires neither shared memory nor communication between processors, while retaining a compact memory footprint. We study the performance on several large optimization benchmarks and show that this achieves mostly linear time speedups, even sometimes super-linear. This is possible because the parallel implementation might explore simultaneously different parts of the search space and therefore converge faster towards the best sub-space and thus towards a solution. Besides getting speedups, the resulting times exhibit a much smaller variance, which benefits applications where a timely reply is critical.

## 1 Introduction

The Cell processor has shown its power for graphic and server applications, and more recently has been considered as a good candidate for scientific calculations [15]. Its floating point arithmetic performance and energy efficiency make it useful as a basic block for building super-computers, cf. the "Roadrunner" machine based on Cell processors which is currently the fastest supercomputer. However, its ability to perform well for general-purpose applications has been questioned, and Cell programming has always been considered as very challenging. We investigate in this paper the use of the Cell/BE for combinatorial optimization applications and constraint-based problem solving. It is worth noticing that in these domains most of the attempts to take advantage of the parallelism available in modern multi-core architectures have targeted homogeneous systems, for instance Intel or AMD-based machines and make use of shared memory, e.g. [14, 8, 7]. The different cores are working on shared data-structures which somehow represent a global environment in which the subcomputations are taking place. Such an approach cannot be used for Cell-based machines, because heavy use of shared memory would degrade the overall performance of this particular multi-core system: in order to extend the use of the Cell processor for combinatorial optimization and constraint-based problem solving, new approaches have to be investigated, in particular those that can lead to independent subcomputations requiring little or no communication between processing units and limited or even no accesses to the main (shared) memory. We decided to focus on Local Search algorithms, also called "metaheuristics", which have attracted much attention over the last decade from both the Operations Research and the Artificial Intelligence communities, in order Y. Deville and C. Solnon (Eds): Sixth International Workshop on Local Search Techniques in Constraint Satisfaction (LSCS'09).

EPTCS 5, 2009, pp. 97–111, doi:10.4204/EPTCS.5.8 c Abreu, Diaz & Codognet