| HAL-Inria | Publications, software ... of Inria's scientists |
Book sections
Many-core Branch-and-Bound for GPU accelerators and MIC coprocessors
Abstract : Coprocessors are increasingly becoming key building blocks of High Performance Computing platforms. These many-core energy-efficient devices boost the performance of traditional processors. On the other hand, Branch-and-Bound (B&B) algorithms are tree-based exact methods for solving to optimality combinatorial optimization problems (COPs). Solving large COPs results in the generation of a very large pool of subproblems and the evaluation of their associated lower bounds. Generating and evaluating those subproblems on coprocessors raises several issues including processor-coprocessor data transfer optimization, vectorization, thread divergence, and so on. In this paper, we investigate the offload-based parallel design and implementation of B&B algorithms for coprocessors addressing these issues. Two major many-core architectures are considered and compared: Nvidia GPU and Intel MIC. The proposed approaches have been experimented using the Flow-Shop scheduling problem and two hardware configurations equivalent in terms of energy consumption: Nvidia Tesla K40 and Intel Xeon Phi 5110P. The reported results show that the GPU-accelerated approach outperforms the MIC offload-based one even in its vectorized version. Moreover, vectorization improves the efficiency of the MIC offload-based approach with a factor of two.
Cited literature [19 references]
https://hal.inria.fr/hal-01924766
Contributor : Jan Gmys <>
Submitted on : Friday, November 16, 2018 - 11:38:43 AM
Last modification on : Friday, December 11, 2020 - 6:44:07 PM
Long-term archiving on: : Sunday, February 17, 2019 - 1:23:31 PM
Contributor : Jan Gmys <>
Submitted on : Friday, November 16, 2018 - 11:38:43 AM
Last modification on : Friday, December 11, 2020 - 6:44:07 PM
Long-term archiving on: : Sunday, February 17, 2019 - 1:23:31 PM
File
22-Melab-et-al.pdf
Files produced by the author(s)