Skip to Main content Skip to Navigation
Conference papers

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
Inria Grenoble - Rhône-Alpes, LIP - Laboratoire de l'Informatique du Parallélisme
3 CRI - Centre de Recherche en Informatique de Paris 1
4 LIP6 - Laboratoire d'Informatique de Paris 6
5 CENTRIA - Centre for Artificial Intelligence
Abstract : 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 : constraint based local search CBLS adaptive search costas arrays parallel programming local search
Complete list of metadatas
https://hal-paris1.archives-ouvertes.fr/hal-00693266
Contributor : Daniel Diaz <>
Submitted on : Wednesday, May 2, 2012 - 11:59:55 AM
Last modification on : Sunday, January 19, 2020 - 6:38:32 PM

Links full text

openaccess

Identifiers

Collections

UNIV-PARIS1 | CNRS | INRIA | LIP | CRI | UPMC | LIP6 | UNIV-LYON1 | SORBONNE-UNIVERSITE | ENS-LYON | SU-SCIENCES | UDL

Citation

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⟩

Export

BibTeX TEI DC DCterms EndNote

Share

Metrics

Record views

420

Contact

Informations

CCSD