IVM-based parallel branch-and-bound using hierarchical work stealing on multi-GPU systems - Archive ouverte HAL Access content directly
Journal Articles Concurrency and Computation: Practice and Experience Year : 2017

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

(1, 2) , (2) , (1) , (2)
1
2

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
Fichier principal
Vignette du fichier
PPAM-SI-Gmys-et-al.pdf (575.06 Ko) Télécharger le fichier
Origin : Files produced by the author(s)
Loading...

Dates and versions

hal-01419072 , version 1 (03-03-2020)

Identifiers

Cite

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, 2017, 29 (9), ⟨10.1002/cpe.4019⟩. ⟨hal-01419072⟩
190 View
178 Download

Altmetric

Share

Gmail Facebook Twitter LinkedIn More