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 (CRIStAL) - 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.
Type de document :
Article dans une revue
Journal of Computer and System Sciences, Elsevier, 2015, 81 (1), pp.72-84. 〈10.1016/j.jcss.2014.06.012〉
Liste complète des métadonnées

https://hal.inria.fr/hal-01095425
Contributeur : Nouredine Melab <>
Soumis le : lundi 15 décembre 2014 - 15:46:09
Dernière modification le : mardi 3 juillet 2018 - 11:48:04

Identifiants

Citation

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〉

Partager

Métriques

Consultations de la notice

254