Parallel local search for solving Constraint Problems on the Cell Broadband Engine (Preliminary Results)
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...
| Main Authors: | , , |
|---|---|
| Format: | Article |
| Language: | English |
| Published: |
Open Publishing Association
2009-10-01
|
| Series: | Electronic Proceedings in Theoretical Computer Science |
| Online Access: | http://arxiv.org/pdf/0910.1264v1 |
| _version_ | 1811245257017262080 |
|---|---|
| author | Salvator Abreu Daniel Diaz Philippe Codognet |
| author_facet | Salvator Abreu Daniel Diaz Philippe Codognet |
| author_sort | Salvator Abreu |
| collection | DOAJ |
| description | 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. |
| first_indexed | 2024-04-12T14:37:06Z |
| format | Article |
| id | doaj.art-4e10c595142b49498782fce523f1bdaf |
| institution | Directory Open Access Journal |
| issn | 2075-2180 |
| language | English |
| last_indexed | 2024-04-12T14:37:06Z |
| publishDate | 2009-10-01 |
| publisher | Open Publishing Association |
| record_format | Article |
| series | Electronic Proceedings in Theoretical Computer Science |
| spelling | doaj.art-4e10c595142b49498782fce523f1bdaf2022-12-22T03:29:02ZengOpen Publishing AssociationElectronic Proceedings in Theoretical Computer Science2075-21802009-10-015Proc. LSCS 20099711110.4204/EPTCS.5.8Parallel local search for solving Constraint Problems on the Cell Broadband Engine (Preliminary Results)Salvator AbreuDaniel DiazPhilippe CodognetWe 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.http://arxiv.org/pdf/0910.1264v1 |
| spellingShingle | Salvator Abreu Daniel Diaz Philippe Codognet Parallel local search for solving Constraint Problems on the Cell Broadband Engine (Preliminary Results) Electronic Proceedings in Theoretical Computer Science |
| title | Parallel local search for solving Constraint Problems on the Cell Broadband Engine (Preliminary Results) |
| title_full | Parallel local search for solving Constraint Problems on the Cell Broadband Engine (Preliminary Results) |
| title_fullStr | Parallel local search for solving Constraint Problems on the Cell Broadband Engine (Preliminary Results) |
| title_full_unstemmed | Parallel local search for solving Constraint Problems on the Cell Broadband Engine (Preliminary Results) |
| title_short | Parallel local search for solving Constraint Problems on the Cell Broadband Engine (Preliminary Results) |
| title_sort | parallel local search for solving constraint problems on the cell broadband engine preliminary results |
| url | http://arxiv.org/pdf/0910.1264v1 |
| work_keys_str_mv | AT salvatorabreu parallellocalsearchforsolvingconstraintproblemsonthecellbroadbandenginepreliminaryresults AT danieldiaz parallellocalsearchforsolvingconstraintproblemsonthecellbroadbandenginepreliminaryresults AT philippecodognet parallellocalsearchforsolvingconstraintproblemsonthecellbroadbandenginepreliminaryresults |