 |
The open archive HAL of Paris 1 Panthéon-Sorbonne university |
Conference papers
Parallel local search for solving Constraint Problems on the Cell Broadband Engine (Preliminary Results)
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.
https://hal-paris1.archives-ouvertes.fr/hal-00663842
Contributor : Daniel Diaz Connect in order to contact the contributor
Submitted on : Friday, January 27, 2012 - 4:46:28 PM
Last modification on : Wednesday, January 26, 2022 - 3:10:32 PM
Contributor : Daniel Diaz Connect in order to contact the contributor
Submitted on : Friday, January 27, 2012 - 4:46:28 PM
Last modification on : Wednesday, January 26, 2022 - 3:10:32 PM
Links full text
