to tackle very large combinatorial problems which are out of range for the classical exhaustive search methods. Local search and metaheuristics have been used in Combinatorial Optimization for finding optimal or near-optimal solutions and have been applied to many different types of problems such as resource allocation, scheduling, packing, layout design, frequency allocation, etc.

To enable the use of the Cell/BE for combinatorial optimization applications, we have developed a parallel extension of a constraint-based local search algorithm based on a method called "Adaptive Search" which was proposed a few years ago in [4, 5].

To assess the viability of this approach, we experimented on several classical benchmarks of the constraint programming community from CSPlib [6]. These structured problems are somehow abstractions of real problems and are therefore representative of real-life applications; they are classically used in the community for benchmarking new methods. The preliminary implementation results for the parallel Adaptive Search method show a good behavior when scaling up the number of cores (from one to sixteen): speedups are, most of 'the time, practically linear, especially for large-scale problems and our experiments even exhibit a few super-linear speedups because the simultaneous exploration of different subparts of the search space may converge faster towards a solution.

Another interesting point to mention is that all experiments show a better robustness of the results on the multi-core version when compared to the sequential algorithm, as will be explained below. Because local search methods make use of randomness for the diversification of the search, execution times may vary from one run to another. This is why, when benchmarking such methods, execution times have to be averaged on many runs (in our experiments, we always take the average of 50 runs). Our implementation results show that for a parallel version running on 16 cores, the difference between the minimal and maximal execution times, as well as the overall variance of the results, decreases significantly with respect to the reference sequential implementation. The main result of this is that execution times become more predictable and this is, of course, an advantage in real-time applications with bounded response time requirements.

The remainder of this article is organized as follows: after an introduction, section 3 discusses the Adaptive Search algorithm and its parallel version is presented in section 4. We proceed with a performance analysis in section 5, which is analyzed and commented on in section 6. Finally, we conclude in section 7 and present our lines for related future research.

## 2 Parallelizing Constraint Solvers

Parallel implementation of search algorithms has a long history, especially in the domain of logic programming, see [9] for an overview. Most of the proposed implementations are based on the so-called OR-parallelism, splitting the search space between different processors but making used of a shared or duplicated stack for coping with the adequate execution environment and they rely on a Shared Memory Multiprocessor (SMP) architecture for the parallel execution support. For some years, similar techniques have been used for Model Checkers, which are used as verification tools for hardware and software, such as the SPIN software [1, 8]. These implementations are also based on some kind of OR-parallelism and, again, these approaches are well-suited for multi-core architecture with shared memory. More recently, there have been several initiatives to extend SAT solvers for parallel machines, in particular multi-cores [7, 3, 16]. However these frameworks require a shared memory model and will thus not be scalable to massively parallel machines or architectures for which communication through (distributed) shared memory is costly such as a cluster system or for hetherogeneous multicore processors such as the Cell/BE. It is worth noticing that now some authors are also extending SAT solvers to PC cluster