Large-scale parallelism for constraint-based local search: the costas array case study - Université Pierre et Marie Curie Accéder directement au contenu
Article Dans Une Revue Constraints Année : 2015

Large-scale parallelism for constraint-based local search: the costas array case study

Résumé

We present the parallel implementation of a constraint-based Local Search algorithm and investigate its performance on several hardware plat-forms with several hundreds or thousands of cores. We chose as the basis for these experiments the Adaptive Search method, an efficient sequential Local Search method for Constraint Satisfaction Problems (CSP). After preliminary experiments on some CSPLib benchmarks, we detail the modeling and solving of a hard combinatorial problem related to radar and sonar applications: the Costas Array Problem. Performance evaluation on some classical CSP bench-marks shows that speedups are very good for a few tens of cores, and good up to a few hundreds of cores. However for a hard combinatorial search problem such as the Costas Array Problem, performance evaluation of the sequential version shows results outperforming previous Local Search implementations, while the parallel version shows nearly linear speedups up to 8,192 cores. The proposed parallel scheme is simple and based on independent multi-walks with no communication between processes during search. We also investigated a cooperative multi-walk scheme where processes share simple information, but this scheme does not seem to improve performance.
Fichier principal
Vignette du fichier
constraints14.pdf (593.88 Ko) Télécharger le fichier
Origine : Fichiers produits par l'(les) auteur(s)
Loading...

Dates et versions

hal-01084270 , version 1 (18-11-2014)

Identifiants

Citer

Yves Caniou, Philippe Codognet, Florian Richoux, Daniel Diaz, Salvador Abreu. Large-scale parallelism for constraint-based local search: the costas array case study. Constraints, 2015, 20 (1), pp.30-56. ⟨10.1007/s10601-014-9168-4⟩. ⟨hal-01084270⟩
298 Consultations
379 Téléchargements

Altmetric

Partager

Gmail Facebook X LinkedIn More