A Tighter Analysis of Work Stealing

Marc Tchiboukdjian 1 Nicolas Gast 2 Denis Trystram 1, 3 Jean-Louis Roch 1 Julien Bernard 4
1 MOAIS - PrograMming and scheduling design fOr Applications in Interactive Simulation
Inria Grenoble - Rhône-Alpes, LIG - Laboratoire d'Informatique de Grenoble
2 MESCAL - Middleware efficiently scalable
Inria Grenoble - Rhône-Alpes, LIG - Laboratoire d'Informatique de Grenoble
3 LIG - Laboratoire d'Informatique de Grenoble
4 FEMTO-ST - Franche-Comté Électronique Mécanique, Thermique et Optique - Sciences et Technologies
Abstract : Classical list scheduling is a very popular and efficient technique for scheduling jobs in parallel platforms. However, with the increasing number of processors, the cost for managing a single centralized list becomes prohibitive. The objective of this work is to study the extra cost that must be paid when the list is distributed among the processors. We present a general methodology for computing the expected makespan based on the analysis of an adequate potential function which represents the load unbalance between the local lists. A bound on the deviation from the mean is also derived. Then, we apply this technique to show that the expected makespan for scheduling W unit independent tasks on m processors is equal to W/m with an additional term in 3.65log2 W. Moreover, simulations show that our bound is very close to the exact value, approximately 50% off. This new analysis also enables to study the influence of the initial repartition of tasks and the reduction of the number of steals when several thieves can simultaneously steal work in the same processor's list.
Type de document :
Communication dans un congrès
The 21st International Symposium on Algorithms and Computation (ISAAC), 2010, Jeju Island, South Korea. Springer, pp.291-302, 2010, 〈10.1007/978-3-642-17514-5_25〉
Liste complète des métadonnées
https://hal.inria.fr/hal-00788864
Contributeur : Arnaud Legrand <>
Soumis le : vendredi 15 février 2013 - 13:09:41
Dernière modification le : mercredi 11 avril 2018 - 01:53:00

Lien texte intégral

openaccess

Identifiants

Collections

INRIA | UNIV-FCOMTE | LIG_SRCPR_MOAIS | LIG | LIG_SRCPR | UGA | UNIV-BM | UNIV-BM-THESE | FEMTO-ST | INRIA-RENGRE

Citation

Marc Tchiboukdjian, Nicolas Gast, Denis Trystram, Jean-Louis Roch, Julien Bernard. A Tighter Analysis of Work Stealing. The 21st International Symposium on Algorithms and Computation (ISAAC), 2010, Jeju Island, South Korea. Springer, pp.291-302, 2010, 〈10.1007/978-3-642-17514-5_25〉. 〈hal-00788864〉

Exporter

BibTeX TEI DC DCterms EndNote

Partager

Métriques

Consultations de la notice

181

Contact


archive-ouverte@inria.fr