Combining multi-core and GPU computing for solving combinatorial optimization problems.

Abstract : In this paper, we revisit the design and implementation of Branch-and-Bound (B&B) algorithms for solving large combinatorial optimization problems on GPU-enhanced multi-core machines. B&B is a tree-based optimization method that uses four operators (selection, branching, bounding and pruning) to build and explore a highly irregular tree representing the solution space. In our previous works, we have proposed a GPU-accelerated approach in which only a single CPU core is used and only the bounding operator is performed on the GPU device. Here, we extend the approach (LL-GB&B) in order to minimize the CPU–GPU communication latency and thread divergence. Such an objective is achieved through a GPU-based fine-grained parallelization of the branching and pruning operators in addition to the bounding one. The second contribution consists in investigating the combination of a GPU with multi-core processing. Two scenarios have been explored leading to two approaches: a concurrent (RLL-GB&B) and a cooperative one (PLL-GB&B). In the first one, the exploration process is performed concurrently by the GPU and the CPU cores. In the cooperative approach, the CPU cores prepare and off-load to GPU pools of tree nodes using data streaming while the GPU performs the exploration. The different approaches have been extensively experimented on the Flowshop scheduling problem. Compared to a single CPU-based execution, LL-GB&B allows accelerations up to (×160) for large problem instances. Moreover, when combining multi-core and GPU, we figure out that using RLL-GB&B is not beneficial while PLL-GB&B enables an improvement up to 36% compared to LL-GB&B.
Type de document :
Article dans une revue
Journal of Parallel and Distributed Computing, Elsevier, 2013, 73 (12), pp.1563-1577. 〈10.1016/j.jpdc.2013.07.023〉
Liste complète des métadonnées

https://hal.inria.fr/hal-00935890
Contributeur : Imen Chakroun <>
Soumis le : vendredi 24 janvier 2014 - 11:37:04
Dernière modification le : mardi 23 janvier 2018 - 14:37:18

Identifiants

Citation

Imen Chakroun, N. Melab, Mohand-Said Mezmaz, Daniel Tuyttens. Combining multi-core and GPU computing for solving combinatorial optimization problems.. Journal of Parallel and Distributed Computing, Elsevier, 2013, 73 (12), pp.1563-1577. 〈10.1016/j.jpdc.2013.07.023〉. 〈hal-00935890〉

Partager

Métriques

Consultations de la notice

236