Skip to Main content Skip to Navigation

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 :
Complete list of metadata

Cited literature [8 references]  Display  Hide  Download
Contributor : Thé Van Luong Connect in order to contact the contributor
Submitted on : Monday, May 4, 2009 - 11:54:43 AM
Last modification on : Thursday, January 20, 2022 - 5:27:53 PM
Long-term archiving on: : Wednesday, September 22, 2010 - 12:58:56 PM


Files produced by the author(s)


  • HAL Id : inria-00380624, version 2


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



Record views


Files downloads