Skip to Main content Skip to Navigation
New interface
Journal articles

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.
Complete list of metadata
Contributor : Imen Chakroun Connect in order to contact the contributor
Submitted on : Friday, January 24, 2014 - 11:37:04 AM
Last modification on : Thursday, January 20, 2022 - 5:27:52 PM



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, 2013, 73 (12), pp.1563-1577. ⟨10.1016/j.jpdc.2013.07.023⟩. ⟨hal-00935890⟩



Record views