Performance analysis of parallel constraint-based local search

Yves Caniou (1, 2) , Daniel Diaz (3) , Florian Richoux , Philippe Codognet (4) , Salvador Abreu (5)

1 LIP - Laboratoire de l'Informatique du Parallélisme
2 AVALON - Algorithms and Software Architectures for Distributed and HPC Platforms
3 CRI - Centre de Recherche en Informatique de Paris 1
4 LIP6 - Laboratoire d'Informatique de Paris 6
5 CENTRIA - Centre for Artificial Intelligence

We present a parallel implementation of a constraint-based local search algorithm and investigate its performance results for hard combinatorial optimization problems on two different platforms up to several hundreds of cores. On a variety of classical CSPs benchmarks, speedups are very good for a few tens of cores, and good up to a hundred cores. More challenging problems derived from reallife applications (Costas array) shows even better speedups, nearly optimal up to 256 cores.

Keywords: local search; constraint based local search; CBLS; adaptive search; costas arrays; parallel programming

Domains: Computer Science [cs]; Software Engineering [cs.SE]; Computer Science [cs]; Distributed, Parallel, and Cluster Computing [cs.DC]

Yves Caniou, Daniel Diaz, Florian Richoux, Philippe Codognet, Salvador Abreu. Performance analysis of parallel constraint-based local search. Principles and Practice of Parallel Programming, Feb 2012, New Orleans, United States. pp.337-338, ⟨10.1145/2145816.2145883⟩. ⟨hal-00693266⟩