.png){kind=icon}
.png){kind=icon}
Return
Combining multi-core and GPU computing for solving combinatorial optimization problems
.png){kind=icon}
PRE
AI
DOI：10.1016/j.jpdc.2013.07.023.png)
.png){kind=icon}
Original request for help.png){kind=icon}
Share.png){kind=icon}
Save
Abstract
En 中文
In this paper, we revisit the design and implementation of Branch-and-Bound (B&B) algorithms for solving large combinatorial optimization problems on CPU-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 CPU-accelerated approach in which only a single CPU core is used and only the bounding operator is performed on the CPU device. Here, we extend the approach (LL-GB&B) in order to minimize the CPU-CPU 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 CPU 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 CPU and the CPU cores. In the cooperative approach, the CPU cores prepare and off-load to CPU pools of tree nodes using data streaming while the CPU 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 ( x 160) for large problem instances. Moreover, when combining multi-core and CPU, 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. (C) 2013 Elsevier Inc. All rights reserved.
Keywords:
Multi-core computing
GPU accelerators
Parallel branch-and-bound
Flowshop scheduling problem
Journal
IF:
4
Papers:
3.8K
Citations:
4.8K