Skip to Main content Skip to Navigation
New interface
Reports (Research report)

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

Olivier Beaumont 1, 2 Arnaud Legrand 1 Loris Marchal 1 Yves Robert 1, 2 
1 GRAAL - Algorithms and Scheduling for Distributed Heterogeneous Platforms
Inria Grenoble - Rhône-Alpes, LIP - Laboratoire de l'Informatique du Parallélisme
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 (Research report)
Complete list of metadata

Cited literature [31 references]  Display  Hide  Download
Contributor : Rapport De Recherche Inria Connect in order to contact the contributor
Submitted on : Friday, May 19, 2006 - 9:40:02 PM
Last modification on : Wednesday, October 26, 2022 - 8:14:49 AM


  • HAL Id : inria-00070796, version 1



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⟩



Record views


Files downloads