Parallel local search for solving Constraint Problems on the Cell Broadband Engine (Preliminary Results)

Salvador Abreu 1 Philippe Codognet 2 Daniel Diaz 3
1 CENTRIA - Centre for Artificial Intelligence
2 LIP6 - Laboratoire d'Informatique de Paris 6
3 CRI - Centre de Recherche en Informatique de Paris 1
Abstract : We explore the use of the Cell Broadband Engine (Cell/BE for short) for combinatorial optimization applications: we present a parallel version of a constraint-based local search algorithm that has been implemented on a multiprocessor BladeCenter machine with twin Cell/BE processors (total of 16 SPUs per blade). This algorithm was chosen because it fits very well the Cell/BE architecture and requires neither shared memory nor communication between processors, while retaining a compact memory footprint. We study the performance on several large optimization benchmarks and show that this achieves mostly linear time speedups, even sometimes super-linear. This is possible because the parallel implementation might explore simultaneously different parts of the search space and therefore converge faster towards the best sub-space and thus towards a solution. Besides getting speedups, the resulting times exhibit a much smaller variance, which benefits applications where a timely reply is critical.
Type de document :
Communication dans un congrès
Sixth International Workshop on Local Search Techniques in Constraint Satisfaction (LSCS'09)., Sep 2009, Lisbon, Portugal. EPTCS, 5, pp.97-111, 2009, 〈10.4204/EPTCS.5.8〉
Liste complète des métadonnées
https://hal-paris1.archives-ouvertes.fr/hal-00663842
Contributeur : Daniel Diaz <>
Soumis le : vendredi 27 janvier 2012 - 16:46:28
Dernière modification le : jeudi 22 novembre 2018 - 14:04:21

Lien texte intégral

arxiv

Identifiants

Collections

CRI | UNIV-PARIS1 | UPMC | LIP6 | SORBONNE-UNIVERSITE

Citation

Salvador Abreu, Philippe Codognet, Daniel Diaz. Parallel local search for solving Constraint Problems on the Cell Broadband Engine (Preliminary Results). Sixth International Workshop on Local Search Techniques in Constraint Satisfaction (LSCS'09)., Sep 2009, Lisbon, Portugal. EPTCS, 5, pp.97-111, 2009, 〈10.4204/EPTCS.5.8〉. 〈hal-00663842〉

Exporter

BibTeX TEI DC DCterms EndNote

Partager

Métriques

Consultations de la notice

106

Contact

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