List Scheduling: The Price of Distribution

Abstract : Classical list scheduling is a very popular and efficient technique for scheduling jobs in parallel and distributed platforms. It is inherently centralized. However, with the increasing number of processors in new parallel platforms, the cost for managing a single centralized list becomes too prohibitive. A suitable approach to reduce the contention is to distribute the list among the computational units. Thus each processor has only a local view of the work to execute. The objective of this work is to study the extra cost that must be paid when the list is distributed among the computational units. 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. It is applied to several scheduling problems, namely, for arbitrary divisible load, for unit independent tasks, for weighted independent tasks and for tasks with dependencies. It is presented in detail for the simplest case of divisible load, and then extended to the other cases.
Type de document :
[Research Report] RR-7208, INRIA. 2010, pp.20
Liste complète des métadonnées

Littérature citée [24 références]  Voir  Masquer  Télécharger
Contributeur : Marc Tchiboukdjian <>
Soumis le : vendredi 19 février 2010 - 13:56:39
Dernière modification le : jeudi 11 janvier 2018 - 06:22:01
Document(s) archivé(s) le : jeudi 18 octobre 2012 - 15:30:24


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


  • HAL Id : inria-00458133, version 1


Marc Tchiboukdjian, Denis Trystram, Jean-Louis Roch, Julien Bernard. List Scheduling: The Price of Distribution. [Research Report] RR-7208, INRIA. 2010, pp.20. 〈inria-00458133〉



Consultations de la notice


Téléchargements de fichiers