Skip to Main content Skip to Navigation
New interface
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 Connect in order to contact the contributor
Submitted on : Monday, December 15, 2014 - 3:46:09 PM
Last modification on : Tuesday, December 6, 2022 - 12:42:13 PM

Links full text



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



Record views