Scalable and fault tolerant hierarchical B&B algorithms for computational grids
Loading...
Date
2012-06-07
Authors
Journal Title
Journal ISSN
Volume Title
Publisher
Université Abderrahmane Mira de Béjaia : Faculté des Sciences Exactes
Abstract
La résolution exacte de problèmes d’optimisation combinatoire avec les algorithmes Branch and Bound (B&B) nécessite un nombre exorbitant de ressources de calcul. Actuellement, cette puissance est offerte par les environnements large échelle comme les grilles de calcul. Cependant, les grilles présentent de nouveaux challenges : le passage à l’échelle, l’hétérogénéité et la tolérance aux pannes. La majorité des algorithmes B&B revisités pour les grilles de calcul sont basés sur le paradigme Master-Worker, ce qui limite leur passage à l’échelle. De plus, la tolérance aux pannes est rarement adressée dans ces travaux. Dans cette thèse, nous proposons trois principales contributions : P2P-B&B, H-B&B et FTH-B&B. P2PB& B est un famework basé sur le paradigme Master-Worker traite le passage à l’échelle par la réduction de la fréquence de requêtes de tâches et en permettant les communications directes entre les workers. H-B&B traite aussi le passage à l’échelle. Contrairement aux approches proposées dans la littérature, H-B&B est complètement dynamique et adaptatif i.e. prenant en compte l’acquisition dynamique des ressources de calcul. FTH-B&B est basé sur de nouveaux mécanismes de tolérance aux pannes permettant de construire et maintenir la hiérarchie équilibrée, et de minimiser la redondance de travail quand les tâches sont sauvegardées et restaurées. Les approches proposées ont été implémentées avec la plateforme pour grille ProActive et ont été appliquées au problème d’ordonnancement de type Flow-Shop. Les expérimentations large échelle effectuées sur la grille Grid’5000 ont prouvé l’efficacité des approches proposées
Description
Keywords
B&B Parallèle, Master-Worker, Master-Worker Hiérarchique, Tolérance aux Pannes, Grilles, FSP, ProActive, Grid’5000