Skip to Main content Skip to Navigation
Conference papers

Parallel Branch-and-Bound using private IVM-based work stealing on Xeon Phi MIC coprocessor

Nouredine Melab 1 Rudi Leroy 1 Mohand Mezmaz 2 Daniel Tuyttens 2
1 DOLPHIN - Parallel Cooperative Multi-criteria Optimization
Inria Lille - Nord Europe, LIFL - Laboratoire d'Informatique Fondamentale de Lille
Abstract : Many combinatorial optimization problems are modeled in practice as permutation-based ones. We have recently proposed a new data structure called IVM dedicated to those problems. IVM is memory efficient in terms of size and management time for solving large permutation problems using Branch-and-Bound (B&B) algorithm. We believe that those memory properties make IVM well-suited for Many Integrated Cores (MIC) architecture. This paper deals with the parallel design and implementation of the B&B algorithm on MIC architectures using private IVM-based work stealing. The proposed approach has been extensively experimented on an Intel Xeon Phi 5110P using several instances of the Flow-Shop scheduling permutation problem. The reported results show that the IVM-based work stealing approach is about 10 times faster than the linked-list traditionally used for parallel B&B.
Complete list of metadata

https://hal.inria.fr/hal-01248335
Contributor : Nouredine Melab Connect in order to contact the contributor
Submitted on : Friday, December 25, 2015 - 10:41:28 AM
Last modification on : Thursday, January 20, 2022 - 5:27:54 PM

Identifiers

Citation

Nouredine Melab, Rudi Leroy, Mohand Mezmaz, Daniel Tuyttens. Parallel Branch-and-Bound using private IVM-based work stealing on Xeon Phi MIC coprocessor. HPCS 2015 - International Conference on High Performance Computing & Simulation, Jul 2015, Amsterdam, Netherlands. ⟨10.1109/HPCSim.2015.7237067⟩. ⟨hal-01248335⟩

Share

Metrics

Les métriques sont temporairement indisponibles