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.
Type de document :
[Research Report] RR-6915, INRIA. 2009
Liste complète des métadonnées

Littérature citée [8 références]  Voir  Masquer  Télécharger
Contributeur : Thé Van Luong <>
Soumis le : lundi 4 mai 2009 - 11:54:43
Dernière modification le : jeudi 11 janvier 2018 - 06:22:13
Document(s) archivé(s) le : mercredi 22 septembre 2010 - 12:58:56


Fichiers produits par l'(les) auteur(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〉



Consultations de la notice


Téléchargements de fichiers