A GPU implementation of parallel constraint-based local search
dc.contributor.author | Arbelaez, Alejandro | en |
dc.contributor.author | Codognet, Philippe | en |
dc.contributor.funder | Seventh Framework Programme | en |
dc.contributor.funder | Japan Society for the Promotion of Science | en |
dc.date.accessioned | 2024-02-01T15:18:39Z | |
dc.date.available | 2024-02-01T15:18:39Z | |
dc.date.issued | 2014-04-14 | en |
dc.description.abstract | In this paper we study the performance of constraint-based local search solvers on a GPU. The massively parallel architecture of the GPU makes it possible to explore parallelism at two different levels inside the local search algorithm. First, by executing multiple copies of the algorithm in a multi-walk manner and, second, by evaluating large neighborhoods in parallel in a single-walk manner. Experiments on three well-known problem benchmarks indicate that the current GPU implementation is up to 17 times faster than a well-tuned sequential algorithm implemented on a desktop computer. | en |
dc.description.sponsorship | Japan Society for the Promotion of Science (JSPS Postdoctoral Program; kakenhi Grant-in-aid for Scientific Research) | en |
dc.description.status | Peer reviewed | en |
dc.description.version | Accepted Version | en |
dc.format.mimetype | application/pdf | en |
dc.identifier.citation | Arbelaez, A. and Codognet, P. (2014) 'A GPU implementation of parallel constraint-based local search', 2014 22nd Euromicro International Conference on Parallel, Distributed, and Network-Based Processing, Turin, Italy, 12-14 February, pp. 648-655, doi: https://doi.org/10.1109/PDP.2014.28 | en |
dc.identifier.doi | https://doi.org/10.1109/PDP.2014.28 | en |
dc.identifier.endpage | 655 | en |
dc.identifier.isbn | 978-1-4799-2729-6 | en |
dc.identifier.startpage | 648 | en |
dc.identifier.uri | https://hdl.handle.net/10468/15487 | |
dc.language.iso | en | en |
dc.publisher | Institute of Electrical and Electronics Engineers (IEEE) | en |
dc.relation.ispartof | 2014 22nd Euromicro International Conference on Parallel, Distributed, and Network-Based Processing, Turin, Italy, 12-14 February | en |
dc.relation.project | info:eu-repo/grantAgreement/EC/FP7::SP1::ICT/318137/EU/The DIStributed Core for unlimited bandwidth supply for all Users and Services/DISCUS | en |
dc.rights | © 2014, IEEE. Personal use of this material is permitted. Permission from IEEE must be obtained for all other uses, in any current or future media, including reprinting/republishing this material for advertising or promotional purposes, creating new collective works, for resale or redistribution to servers or lists, or reuse of any copyrighted component of this work in other works. | en |
dc.subject | Local Search | en |
dc.subject | CSP | en |
dc.subject | GPU | en |
dc.title | A GPU implementation of parallel constraint-based local search | en |
dc.type | Conference item | en |