Vol de tâches basé sur IVM pour Branch-and-Bound parallèle sur GPU

Gmys, Jan; Mezmaz, Mohand; Melab, N; Tuyttens, D

Document type :

Communication dans un congrès avec actes

Title :

Vol de tâches basé sur IVM pour Branch-and-Bound parallèle sur GPU

Author(s) :

Gmys, Jan [Auteur]

Parallel Cooperative Multi-criteria Optimization [DOLPHIN]
Institut de Mathématiques [Mons]
Mezmaz, Mohand [Auteur]
Institut de Mathématiques [Mons]
Melab, N [Auteur]
Parallel Cooperative Multi-criteria Optimization [DOLPHIN]
Tuyttens, D [Auteur]
Institut de Mathématiques [Mons]

Conference title :

11th Intl. Conf. on Parallel Processing and Applied Mathematics

City :

Krakov

Country :

Pologne

Start date of the conference :

2015-09-06

Book title :

LNCS Springer Verlag

English keyword(s) :

GPU computing
Branch-and-Bound
Combinatorial optimization
Work Stealing

HAL domain(s) :

Informatique [cs]/Calcul parallèle, distribué et partagé [cs.DC]

English abstract : [en]

The irregularity of Branch-and-Bound (B&B) algorithms makes their design and implementation on the GPU challenging. In this paper we present a B&B algorithm entirely based on GPU and propose four work stealing strategies ...
Show more >The irregularity of Branch-and-Bound (B&B) algorithms makes their design and implementation on the GPU challenging. In this paper we present a B&B algorithm entirely based on GPU and propose four work stealing strategies to balance the workload inside the GPU. Our B&B is based on an Integer-Vector-Matrix (IVM) data structure instead of a pool of permutations, and work units exchanged are intervals of factoradics instead of sets of nodes. To the best of our knowledge, the proposed approach is the pioneering to perform the entire exploration process on GPU. The four work stealing strategies have been experimented and compared to a multi-core IVM-based approach using standard flow shop scheduling problem instances. The reported results show, on the one hand, that the GPU-accelerated approach is more than 5 times faster than its multi-core counterpart. On the other hand, the best of the four strategies provides a near-optimal load balance while consuming only 2% of the total execution time of the algorithm.Show less >

Language :

Anglais

Peer reviewed article :

Oui

Audience :

Internationale

Popular science :

Non

Collections :

Centre de Recherche en Informatique, Signal et Automatique de Lille (CRIStAL) - UMR 9189

Source :

Harvested from HAL

Vol de tâches basé sur IVM pour Branch-and-Bound ... BibTeX CSV Excel RIS

Vol de tâches basé sur IVM pour Branch-and-Bound ...

BibTeX

CSV

Excel

RIS