Hierarchical work-stealing

Abstract : dynamic load-balancing on hierarchical platforms. In particular, we consider applications involving heavy communications on a distributed platform. The work-stealing algorithm introduced by Blumofe and Leiserson is a commonly used technique to balance load in a distributed environment but it suffers from poor performance with some communication-intensive applications. We describe here several variants of this algorithm found in the literature and in different grid middlewares like Satin and Kaapi. In addition, we propose two new variations of the work-stealing algorithm : HWS and PWS. These algorithms improve performance by considering the network structure. We conduct a theoretical analysis of HWS in the case of fork-join task graphs and prove that HWS reduces communication overhead. In addition, we present experimental results comparing the most relevant algorithms. Experiments on Grid'5000 show that HWS and PWS allow us to obtain performance gains of up to twenty per cent when compared to the classical workstealing algorithm. Moreover in some cases, PWS and HWS achieve speedup while classical work-stealing policies result in speed-down.
Type de document :
Communication dans un congrès
Proceedings of the 16th international Euro-Par conference on Parallel processing: Part I, 2010, Berlin, Heidelberg, Germany. Springer-Verlag, pp.217―229, 2010, EuroPar'10. 〈10.1007/978-3-642-15277-1_21〉
Liste complète des métadonnées

https://hal.inria.fr/hal-00798447
Contributeur : Grégory Mounié <>
Soumis le : vendredi 8 mars 2013 - 15:31:55
Dernière modification le : mercredi 11 avril 2018 - 01:54:52

Lien texte intégral

Identifiants

Collections

Citation

Jean-Noël Quintin, Frédéric Wagner. Hierarchical work-stealing. Proceedings of the 16th international Euro-Par conference on Parallel processing: Part I, 2010, Berlin, Heidelberg, Germany. Springer-Verlag, pp.217―229, 2010, EuroPar'10. 〈10.1007/978-3-642-15277-1_21〉. 〈hal-00798447〉

Partager

Métriques

Consultations de la notice

173