Skip to Main content Skip to Navigation
Book sections

Many-core Branch-and-Bound for GPU accelerators and MIC coprocessors

Nouredine Melab 1 Jan Gmys 1, 2 Mohand Mezmaz 2 Daniel Tuyttens 2
1 BONUS - Optimisation de grande taille et calcul large échelle
Inria Lille - Nord Europe, CRIStAL - Centre de Recherche en Informatique, Signal et Automatique de Lille - UMR 9189
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.
Complete list of metadata

Cited literature [19 references]  Display  Hide  Download
Contributor : Jan Gmys Connect in order to contact the contributor
Submitted on : Friday, November 16, 2018 - 11:38:43 AM
Last modification on : Thursday, March 24, 2022 - 3:42:46 AM
Long-term archiving on: : Sunday, February 17, 2019 - 1:23:31 PM


Files produced by the author(s)


  • HAL Id : hal-01924766, version 1


Nouredine Melab, Jan Gmys, Mohand Mezmaz, Daniel Tuyttens. Many-core Branch-and-Bound for GPU accelerators and MIC coprocessors. T. Bartz-Beielstein; B. Filipic; P. Korosec; E-G. Talbi. High-Performance Simulation-Based Optimization, 833, Springer, pp.16, 2019, Studies in Computational Intelligence, ISBN 978-3-030-18763-7. ⟨hal-01924766⟩



Record views


Files downloads