IVM-based Work Stealing for Parallel Branch-and-Bound on GPU

Jan Gmys 1, 2 Mohand Mezmaz 1 N Melab 2 D Tuyttens 1
2 DOLPHIN - Parallel Cooperative Multi-criteria Optimization
Inria Lille - Nord Europe, CRIStAL - Centre de Recherche en Informatique, Signal et Automatique de Lille (CRIStAL) - UMR 9189
Abstract : 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.
Type de document :
Communication dans un congrès
11th Intl. Conf. on Parallel Processing and Applied Mathematics, Sep 2015, Krakov, Poland. LNCS Springer Verlag
Liste complète des métadonnées

https://hal.inria.fr/hal-01248329
Contributeur : Nouredine Melab <>
Soumis le : jeudi 24 décembre 2015 - 20:29:42
Dernière modification le : mardi 3 juillet 2018 - 11:49:08

Identifiants

  • HAL Id : hal-01248329, version 1

Collections

Citation

Jan Gmys, Mohand Mezmaz, N Melab, D Tuyttens. IVM-based Work Stealing for Parallel Branch-and-Bound on GPU. 11th Intl. Conf. on Parallel Processing and Applied Mathematics, Sep 2015, Krakov, Poland. LNCS Springer Verlag. 〈hal-01248329〉

Partager

Métriques

Consultations de la notice

296