Skip to Main content Skip to Navigation
Reports

Parallel Local Search on GPU

Thé Van Luong 1 Nouredine Melab 1 El-Ghazali Talbi 1
1 DOLPHIN - Parallel Cooperative Multi-criteria Optimization
LIFL - Laboratoire d'Informatique Fondamentale de Lille, Inria Lille - Nord Europe
Abstract : Local search algorithms are a class of algorithms to solve complex optimization problems in science and industry. Even if these metaheuristics allow to significantly reduce the computational time of the solution exploration space, the iterative process remains costly when very large problem instances are dealt with. As a solution, graphics processing units (GPUs) represent an efficient alternative for calculations instead of traditional CPU. This paper presents a new methodology to design and implement local search algorithms on GPU. Methods such as tabu search, hill climbing or iterated local search present similar concepts that can be parallelized on GPU and then a general cooperative model can be highlighted. In addition to single-solution based metaheuristics on GPU, this model can be extended with a hybrid multi-core and multi-GPU approach for multiple local search methods such as multistart. The conclusions from both GPU and multi-GPU experiments indicate significant speed-ups compared to CPU approaches.
Document type :
Reports
Complete list of metadatas

Cited literature [8 references]  Display  Hide  Download

https://hal.inria.fr/inria-00380624
Contributor : Thé Van Luong <>
Submitted on : Monday, May 4, 2009 - 11:54:43 AM
Last modification on : Thursday, May 28, 2020 - 9:22:09 AM
Document(s) archivé(s) le : Wednesday, September 22, 2010 - 12:58:56 PM

File

RR-6915.pdf
Files produced by the author(s)

Identifiers

  • HAL Id : inria-00380624, version 2

Citation

Thé Van Luong, Nouredine Melab, El-Ghazali Talbi. Parallel Local Search on GPU. [Research Report] RR-6915, INRIA. 2009. ⟨inria-00380624v2⟩

Share

Metrics

Record views

698

Files downloads

576