Skip to Main content Skip to Navigation
Journal articles

Parallel Branch-and-Bound in Multi-core Multi-CPU Multi-GPU Heterogeneous Environments

Trong-Tuan Vu 1 Bilel Derbel 1, 2
1 DOLPHIN - Parallel Cooperative Multi-criteria Optimization
LIFL - Laboratoire d'Informatique Fondamentale de Lille, Inria Lille - Nord Europe
Abstract : We investigate the design of parallel B&B in large scale heterogeneous compute environments where processing units can be composed of a mixture of multiple shared memory cores, multiple distributed CPUs and multiple GPUs devices. We describe two approaches addressing the critical issue of how to map B&B workload with the different levels of parallelism exposed by the target compute platform. We also contribute a throughout large scale experimental study which allows us to derive a comprehensive and fair analysis of the proposed approaches under different system configurations using up to 16 GPUs and up to 512 CPU-cores. Our results shed more light on the main challenges one has to face when tackling B&B algorithms while describing efficient techniques to address them. In particular, we are able to obtain linear speed-ups at moderate scales where adaptive load balancing among the heterogeneous compute resources is shown to have a significant impact on performance. At the largest scales, intra-node parallelism and hybrid decentralized load balancing is shown to have a crucial importance in order to alleviate locking issues among shared memory threads and to scale the distributed resources while optimizing communication costs and minimizing idle times
Complete list of metadatas

https://hal.inria.fr/hal-01067662
Contributor : Bilel Derbel <>
Submitted on : Tuesday, September 23, 2014 - 9:21:23 PM
Last modification on : Tuesday, May 12, 2020 - 5:26:12 PM
Document(s) archivé(s) le : Friday, April 14, 2017 - 4:19:30 PM

File

RR_threembb.pdf
Files produced by the author(s)

Identifiers

  • HAL Id : hal-01067662, version 1

Citation

Trong-Tuan Vu, Bilel Derbel. Parallel Branch-and-Bound in Multi-core Multi-CPU Multi-GPU Heterogeneous Environments. Future Generation Computer Systems, Elsevier, 2014, pp.25. ⟨hal-01067662⟩

Share

Metrics

Record views

797

Files downloads

1291