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 :
Rapport
[Research Report] RR-5196, INRIA. 2004, pp.28
Liste complète des métadonnées


https://hal.inria.fr/inria-00070796
Contributeur : Rapport de Recherche Inria <>
Soumis le : vendredi 19 mai 2006 - 21:40:02
Dernière modification le : samedi 17 septembre 2016 - 01:27:50
Document(s) archivé(s) le : dimanche 4 avril 2010 - 21:56:10

Fichiers

Identifiants

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

Partager

Métriques

Consultations de
la notice

289

Téléchargements du document

141