Independent and Divisible Task Scheduling on Heterogeneous Star-shaped Platforms with Limited Memory

Abstract : In this paper, we consider the problem of allocating and scheduling a collection of independent, equal-sized tasks on heterogeneous star-shaped platforms. We also address the same problem for divisible tasks. For both cases, we take memory constraints into account. We prove strong NP-completeness results for different objective functions, namely makespan minimization and throughput maximization, on simple star-shaped platforms. We propose an approximation algorithm based on the unconstrained version (with unlimited memory) of the problem. We introduce several heuristics, which are evaluated and compared through extensive simulations. An unexpected conclusion drawn from these experiments is that classical scheduling heuristics that try to greedily minimize the completion time of each task are outperformed by the simple heuristic that consists in assigning the task to the available processor that has the smallest communication time, regardless of computation power (hence a "bandwidth-centric" distribution).
Document type :
Reports
Complete list of metadatas

Cited literature [31 references]  Display  Hide  Download

https://hal.inria.fr/inria-00070796
Contributor : Rapport de Recherche Inria <>
Submitted on : Friday, May 19, 2006 - 9:40:02 PM
Last modification on : Friday, May 17, 2019 - 5:27:46 PM

Identifiers

  • HAL Id : inria-00070796, version 1

Collections

Citation

Olivier Beaumont, Arnaud Legrand, Loris Marchal, Yves Robert. Independent and Divisible Task Scheduling on Heterogeneous Star-shaped Platforms with Limited Memory. [Research Report] RR-5196, LIP RR-2004-22, INRIA, LIP. 2004, pp.28. ⟨inria-00070796⟩

Share

Metrics

Record views

329

Files downloads

414