Work Stealing with Private Integer-Vector-Matrix Data Structure for Multi-core Branch-and-Bound Algorithms

Jan Gmys 1, 2 Rudi Leroy 1 Mohand Mezmaz 2 Nouredine Melab 1 Daniel Tuyttens 2
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 paper, the focus is put on multi-core Branch-and-Bound algorithms for solving large scale permutation-based optimization problems. We investigate five work stealing (WS) strategies with a new data structure called Integer-Vector-Matrix (IVM). In these strategies, each thread has a private IVM allowing the local management of a set of subproblems enumerated using a factorial system. The WS strategies differ in the way the victim thread is selected and the granularity of stolen work units (intervals of factoradics). To assess the efficiency of the private IVM-based WS approach, the five WS strategies have been extensively experimented on the flowshop scheduling permutation problem and compared to their conventional linked-list-based counterparts. The obtained results demonstrate that the IVM-based WS outperforms the linked-list-based one in terms of CPU time, memory usage and number of performed WS operations.
Type de document :
Article dans une revue
Concurrency and Computation: Practice and Experience, Wiley, 2016, 〈10.1002/cpe.3771〉
Liste complète des métadonnées

https://hal.inria.fr/hal-01248336
Contributeur : Nouredine Melab <>
Soumis le : vendredi 25 décembre 2015 - 11:03:29
Dernière modification le : jeudi 11 janvier 2018 - 06:27:32

Identifiants

Citation

Jan Gmys, Rudi Leroy, Mohand Mezmaz, Nouredine Melab, Daniel Tuyttens. Work Stealing with Private Integer-Vector-Matrix Data Structure for Multi-core Branch-and-Bound Algorithms. Concurrency and Computation: Practice and Experience, Wiley, 2016, 〈10.1002/cpe.3771〉. 〈hal-01248336〉

Partager

Métriques

Consultations de la notice

238