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
Document type :
Conference papers
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 : Friday, September 27, 2019 - 12:16:04 PM

Links full text

openaccess

Identifiers

Collections

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

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

366

Contact

support.ccsd.cnrs.fr
hal.support@ccsd.cnrs.fr
Logo CCSD