GPU Computing for Parallel Local Search Metaheuristics

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 metaheuristics (LSMs) are efficient methods for solving complex problems in science and industry. They allow significantly to reduce the size of the search space to be explored and the search time. Nevertheless, the resolution time remains prohibitive when dealing with large problem instances. Therefore, the use of GPU-based massively parallel computing is a major complementary way to speed up the search. However, GPU computing for LSMs is rarely investigated in the literature. In this paper, we introduce a new guideline for the design and implementation of effective LSMs on GPU. Very efficient approaches are proposed for CPU-GPU data transfer optimization, thread control, mapping of neighboring solutions to GPU threads and memory management. These approaches have been experimented using four well-known combinatorial and continuous optimization problems and four GPU configurations. Compared to a CPU-based execution, accelerations up to x80 are reported for the large combinatorial problems and up to x240 for a continuous problem. Finally, extensive experiments demonstrate the strong potential of GPU-based LSMs compared to cluster or grid-based parallel architectures.
Type de document :
Article dans une revue
IEEE Transactions on Computers, Institute of Electrical and Electronics Engineers, 2013, 62 (1), pp.173-185
Liste complète des métadonnées

Littérature citée [25 références]  Voir  Masquer  Télécharger

https://hal.inria.fr/inria-00638805
Contributeur : Thé Van Luong <>
Soumis le : lundi 7 novembre 2011 - 13:29:54
Dernière modification le : jeudi 11 janvier 2018 - 06:22:13
Document(s) archivé(s) le : mercredi 8 février 2012 - 02:30:24

Fichiers

TC-2010-07-0376.R1-main_with_b...
Fichiers produits par l'(les) auteur(s)

Identifiants

  • HAL Id : inria-00638805, version 1

Citation

Thé Van Luong, Nouredine Melab, El-Ghazali Talbi. GPU Computing for Parallel Local Search Metaheuristics. IEEE Transactions on Computers, Institute of Electrical and Electronics Engineers, 2013, 62 (1), pp.173-185. 〈inria-00638805〉

Partager

Métriques

Consultations de la notice

391

Téléchargements de fichiers

761