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 metadatas

Cited literature [24 references]  Display  Hide  Download

https://hal.inria.fr/inria-00458133
Contributor : Marc Tchiboukdjian <>
Submitted on : Friday, February 19, 2010 - 1:56:39 PM
Last modification on : Wednesday, March 13, 2019 - 3:02:06 PM
Long-term archiving on : Thursday, October 18, 2012 - 3:30:24 PM

File

RR-7208.pdf
Files produced by the author(s)

Identifiers

  • HAL Id : inria-00458133, version 1

Citation

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⟩

Share

Metrics

Record views

460

Files downloads

164