Work Stealing Strategies For Multi-Core Parallel Branch-and-Bound Algorithm Using Factorial Number System.

Rudi Leroy 1 Mohand Mezmaz 2 Nouredine Melab 1 Daniel Tuyttens 2
1 DOLPHIN - Parallel Cooperative Multi-criteria Optimization
LIFL - Laboratoire d'Informatique Fondamentale de Lille, Inria Lille - Nord Europe
Abstract : Many real-world problems in different industrial and economic fields are permutation combinatorial optimization problems. Solving to optimality large instances of these problems, such as the flowshop problem, is a challenge for multi-core computing. This paper proposes four work stealing strategies for the multi-threaded factoradic-based branch-and-bound (B\&B) algorithm to solve permutation combinatorial problems on multi-core processors. The factoradic, called also factorial number system, is a mixed radix numeral system adapted to numbering permutations. In our new parallel strategies, the B\&B is based on a matrix of integers instead of a pool of permutations, and work units exchanged between threads are intervals of factoradics instead of sets of nodes. The experiments show that the strategy based on selecting the largest interval is better than the three other strategies in terms of the number of interval sharing events. Furthermore, the worst factoradic-based strategy spends on average $7.2$ times less time managing the pool of subproblems than a conventional pool-based parallel B\&B algorithm.
Type de document :
Communication dans un congrès
ACM PPOPP/PMAM-2014, Feb 2014, Orlando, Florioda, France. 2014
Liste complète des métadonnées

https://hal.inria.fr/hal-01095213
Contributeur : Nouredine Melab <>
Soumis le : lundi 15 décembre 2014 - 11:51:12
Dernière modification le : jeudi 11 janvier 2018 - 06:22:13

Identifiants

  • HAL Id : hal-01095213, version 1

Citation

Rudi Leroy, Mohand Mezmaz, Nouredine Melab, Daniel Tuyttens. Work Stealing Strategies For Multi-Core Parallel Branch-and-Bound Algorithm Using Factorial Number System.. ACM PPOPP/PMAM-2014, Feb 2014, Orlando, Florioda, France. 2014. 〈hal-01095213〉

Partager

Métriques

Consultations de la notice

166