Skip to Main content Skip to Navigation
Journal articles

IVM-based parallel branch-and-bound using hierarchical work stealing on multi-GPU systems

Jan Gmys 1, 2 Mohand Mezmaz 2 Nouredine Melab 1 Daniel Tuyttens 2
1 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 : Tree-based exploratory methods, like Branch-and-Bound (B&B) algorithms, are highly irregular applications which makes their design and implementation on graphics processing unit (GPU) challenging. In this paper, we present a multi-GPU B&B algorithm for solving large permutation-based combinatorial optimization problems. To tackle the problem of the irregular workload, we propose a hierarchical work stealing (WS) strategy that balances the workload inside the GPU and between different GPUs and CPU cores. Our B&B is based on an Integer-Vector-Matrix data structure instead of a pool of permutations, and work units exchanged are intervals of factoradics instead of sets of nodes. Two variants of the algorithm, using the same hierarchical WS strategy, are proposed: one for combinatorial optimization problems where the evaluation of nodes is costly and one for fine-grained problems. The latter variant uses a new hypercube-based WS strategy and a trigger mechanism to balance the work load inside the GPU. The proposed approach has been extensively experimented using the flowshop scheduling, the n-queens and the asymmetric travelling salesman problems as test-cases. The reported results show that the proposed hierarchical WS mechanism is capable of handling fine and coarse-grained types of workloads efficiently, reaching near-linear speed-up on up to four GPUs for a set of ten flowshop instances and large instances of fine-grained problems
Complete list of metadatas

Cited literature [35 references]  Display  Hide  Download
Contributor : Jan Gmys <>
Submitted on : Tuesday, March 3, 2020 - 3:02:38 PM
Last modification on : Wednesday, March 4, 2020 - 1:19:40 AM
Document(s) archivé(s) le : Thursday, June 4, 2020 - 3:59:01 PM


Files produced by the author(s)




Jan Gmys, Mohand Mezmaz, Nouredine Melab, Daniel Tuyttens. IVM-based parallel branch-and-bound using hierarchical work stealing on multi-GPU systems. Concurrency and Computation: Practice and Experience, Wiley, 2017, 29 (9), ⟨10.1002/cpe.4019⟩. ⟨hal-01419072⟩



Record views


Files downloads