Parallel Branch-and-Bound using private IVM-based work stealing on Xeon Phi MIC coprocessor - Archive ouverte HAL Access content directly
Conference Papers Year :

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

(1) , (1) , (2) , (2)
1
2

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.
Not file

Dates and versions

hal-01248335 , version 1 (25-12-2015)

Identifiers

Cite

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⟩
62 View
0 Download

Altmetric

Share

Gmail Facebook Twitter LinkedIn More