Skip to Main content Skip to Navigation
New interface
Conference papers

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 - 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.
Complete list of metadata
Contributor : Nouredine Melab Connect in order to contact the contributor
Submitted on : Thursday, December 24, 2015 - 8:29:42 PM
Last modification on : Tuesday, December 6, 2022 - 12:42:13 PM


  • HAL Id : hal-01248329, version 1


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. ⟨hal-01248329⟩



Record views