Back to first pageBack to first page Centre for Artificial Intelligence of UNL
Browse our site
You are here:

Publication details

Go back
Publication details
Main information
Parallel local search for solving Constraint Problems on the Cell Broadband Engine (Preliminary Results)
November 2009
DBLP:journals/corr/abs-0910-1264
We explore the use of the Cell Broadband Engine 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 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.
Journal
Salvador Abreu, Daniel Diaz, Philippe Codognet
Electronic Proceedings in Theoretical Computer Science
-
-
5
-
97-111
-
2075-2180
-
http://arxiv.org/abs/0910.1264v1
Export formats
Salvador Abreu and Daniel Diaz and Philippe Codognet, Parallel local search for solving Constraint Problems on the Cell Broadband Engine (Preliminary Results), Electronic Proceedings in Theoretical Computer Science, Vol. 5, Pag. 97-111, ISSN 2075-2180, (http://arxiv.org/abs/0910.1264v1), November 2009.
<b><a href="/people/members/view.php?code=e927e6f7f16b0d293c89324129b1ea0e" class="author">Salvador Abreu</a>, Daniel Diaz and Philippe Codognet</b>, <u>Parallel local search for solving Constraint Problems on the Cell Broadband Engine (Preliminary Results)</u>, Electronic Proceedings in Theoretical Computer Science, Vol. 5, Pag. 97-111, ISSN 2075-2180, (<a href="http://arxiv.org/abs/0910.1264v1" target="_blank">url</a>), November 2009.
@article {DBLP:journals/corr/abs-0910-1264, author = {Salvador Abreu and Daniel Diaz and Philippe Codognet}, title = {Parallel local search for solving Constraint Problems on the Cell Broadband Engine (Preliminary Results)}, journal = {Electronic Proceedings in Theoretical Computer Science}, volume = {5}, pages = {97-111}, issn = {2075-2180}, url = {http://arxiv.org/abs/0910.1264v1}, abstract = {We explore the use of the Cell Broadband Engine 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 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.}, month = {November}, year = {2009}, }
Publication's urls
/publications/view.php?code=49dafd59f7ac95e50f1a608137c2b643
/publications/view.php?code=DBLP:journals/corr/abs-0910-1264
Go back
Centre for Artificial Intelligence of UNL
Departamento de Informática, FCT/UNL
Quinta da Torre 2829-516 CAPARICA - Portugal
Tel. (+351) 21 294 8536 FAX (+351) 21 294 8541

Fundacao_FCT