Autor(es): Abreu, Salvador ; Caniou, Yves ; Codognet, Philippe ; Diaz, Daniel ; Richoux, Florial
Data: 2012
Identificador Persistente: http://hdl.handle.net/10174/4569
Origem: Repositório Científico da Universidade de Évora
Assunto(s): Constraint Satisfaction; Parallel Computation
We present a parallel implementation of a constraint-based local search algorithm and investigate its performance results on hard- ware with several hundreds of processors. We choose as basic constraint solving algorithm for these experiments the ”adaptive search” method, an efficient sequential local search method for Constraint Satisfaction Problems. The implemented algorithm is a parallel version of adaptive search in a multiple independent-walk manner, that is, each process is an independent search engine and there is no communication between the si- multaneous computations. Preliminary performance evaluation are very encouraging. On a variety of classical CSPs benchmarks from CSPLIB, speedups are very good for a few tens of cores, and good up to a few hundreds of processors. More challenging problems derived from real-life applications (Costas array) shows even better speedups, nearly optimal up to 256 cores.
