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

Olivier Beaumont 1 Arnaud Legrand 1 Loris Marchal 1 Yves Robert 1
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).
Type de document :
[Research Report] RR-5196, INRIA. 2004, pp.28
Liste complète des métadonnées

Littérature citée [31 références]  Voir  Masquer  Télécharger
Contributeur : Rapport de Recherche Inria <>
Soumis le : vendredi 19 mai 2006 - 21:40:02
Dernière modification le : vendredi 20 avril 2018 - 15:44:24
Document(s) archivé(s) le : dimanche 4 avril 2010 - 21:56:10



  • 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, INRIA. 2004, pp.28. 〈inria-00070796〉



Consultations de la notice


Téléchargements de fichiers