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
Type de document :
Article dans une revue
Concurrency and Computation: Practice and Experience, Wiley, 2016, 29 (9), 〈10.1002/cpe.4019〉
Liste complète des métadonnées

https://hal.inria.fr/hal-01419072
Contributeur : Jan Gmys <>
Soumis le : dimanche 18 décembre 2016 - 15:11:55
Dernière modification le : vendredi 13 avril 2018 - 01:28:05

Identifiants

Collections

Citation

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, 2016, 29 (9), 〈10.1002/cpe.4019〉. 〈hal-01419072〉

Partager

Métriques

Consultations de la notice

290