Hierarchical Work-Stealing

Abstract : In this paper, we study the problem of dynamic load-balancing on heterogeneous hierarchical platforms. In particular, we consider here applications involving heavy communications on a distributed platform. The work-stealing algorithm introduced by Blumofe and Leiserson is a commonly used technique to distribute load in a distributed environment but it suffers from poor performances in some cases of communications-intensive applications. We present here several variants of this algorithm found in the literature and 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 performances by taking the networking structure into account within the scheduling. We conduct a theoretical analysis of HWS in the case of fork-join task graphs and 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 standard algorithm. Moreover in some case, the standard algorithm reaches worse performances on the distributed platform than on a single machine while PWS and HWS achieve some speedup.
Type de document :
[Research Report] INRIA. 2009, pp.24
Liste complète des métadonnées

Littérature citée [10 références]  Voir  Masquer  Télécharger

Contributeur : Jean-Noel Quintin <>
Soumis le : jeudi 5 novembre 2009 - 08:59:48
Dernière modification le : vendredi 12 octobre 2018 - 01:18:08
Document(s) archivé(s) le : samedi 26 novembre 2016 - 14:28:04


Fichiers produits par l'(les) auteur(s)


  • HAL Id : inria-00429624, version 2


Jean-Noel Quintin, Frédéric Wagner. Hierarchical Work-Stealing. [Research Report] INRIA. 2009, pp.24. 〈inria-00429624v2〉



Consultations de la notice


Téléchargements de fichiers