Skip to Main content Skip to Navigation

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.
Complete list of metadata

Cited literature [24 references]  Display  Hide  Download
Contributor : Marc Tchiboukdjian Connect in order to contact the contributor
Submitted on : Friday, February 19, 2010 - 1:56:39 PM
Last modification on : Thursday, January 13, 2022 - 12:00:13 PM
Long-term archiving on: : Thursday, October 18, 2012 - 3:30:24 PM


Files produced by the author(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⟩



Les métriques sont temporairement indisponibles