Skip to Main content Skip to Navigation
Journal articles

Towards a heterogeneous and adaptive parallel Branch-and-Bound algorithm

Imen Chakroun 1 Nouredine Melab 2, 1
1 DOLPHIN - Parallel Cooperative Multi-criteria Optimization
Inria Lille - Nord Europe, CRIStAL - Centre de Recherche en Informatique, Signal et Automatique de Lille - UMR 9189
Abstract : In this work, we revisit the design and implementation of the Branch-and-Bound (B&B) algorithm for heterogeneous environments combining multi-core processors with GPU accelerators. The challenge is to automatically identify the best mapping of computations to the target heterogeneous platform and to adjust the problem, algorithmic and platform parameters. In the proposed meta-algorithm, four hardware configuration scenarios have been considered: 1CPU-1GPU, nCPU-0GPU, nCPU-1GPU, nCPU-nGPU.Over a serial B&B, accelerations up to ×222 have been achieved for large problem instances of the Flow-Shop scheduling problem. The reported results show that: (1) the GPU-accelerated algorithm performs better than its multi-core CPU-based version; (2) combining multi-core and GPU allows improvement up to 36% over a single CPU-GPU execution; (3) the more GPU devices are used, the better the speedups are whatever is the considered problem instance.
Complete list of metadata
Contributor : Nouredine Melab <>
Submitted on : Monday, December 15, 2014 - 3:46:09 PM
Last modification on : Friday, December 11, 2020 - 6:44:05 PM

Links full text



Imen Chakroun, Nouredine Melab. Towards a heterogeneous and adaptive parallel Branch-and-Bound algorithm. Journal of Computer and System Sciences, Elsevier, 2015, 81 (1), pp.72-84. ⟨10.1016/j.jcss.2014.06.012⟩. ⟨hal-01095425⟩



Record views