An Efficient Load Balancing Strategy for Grid-based Branch and Bound Algorithm

Abstract : The most popular parallelization approach of the branch and bound algorithm consists in building and exploring in parallel the search tree representing the problem being tackled. The deployment of such parallel model on a grid rises the crucial issue of dynamic load balancing. The major question is how to efficiently distribute the nodes of an irregular search tree among a large set of heterogeneous and volatile processors. In this paper, we propose a new dynamic load balancing approach for the parallel branch and bound algorithm on the computational grid. The approach is based on a particular numbering of the tree nodes allowing a very simple description of the work units distributed during the exploration. Such description optimizes the communications involved by the huge amount of load balancing operations. The approach has been applied to one instance of the bi-objective flow-shop scheduling problem. The application has been experimented on a computational pool of more than 1000 processors belonging to seven Nation-wide clusters. The optimal solution has been generated within almost 6 days with a parallel efficiency of 98%.
Type de document :
Article dans une revue
Parallel Computing, Elsevier, 2007, 33 (4-5), pp.302-313. 〈10.1016/j.parco.2007.02.004〉
Liste complète des métadonnées

https://hal.inria.fr/hal-00684607
Contributeur : Ist Rennes <>
Soumis le : lundi 2 avril 2012 - 15:59:26
Dernière modification le : mardi 24 avril 2018 - 13:51:37

Identifiants

Collections

Citation

Mohand Mezmaz, N. Melab, E.-G. Talbi. An Efficient Load Balancing Strategy for Grid-based Branch and Bound Algorithm. Parallel Computing, Elsevier, 2007, 33 (4-5), pp.302-313. 〈10.1016/j.parco.2007.02.004〉. 〈hal-00684607〉

Partager

Métriques

Consultations de la notice

136