Off-line and on-line scheduling on heterogeneous master-slave platforms

Abstract : In this paper, we deal with the problem of scheduling independent tasks on heterogeneous master-slave platforms. We target both o-line and on-line problems , with several objective functions (makespan, maximum response time, total completion time). On the theoretical side, our results are twofold: (i) For o-line scheduling, we prove several optimality results for problems with release dates; (ii) For on-line scheduling , we establish lower bounds on the competitive ratio of any deterministic algorithm. On the practical side, we have implemented several heuristics, some classical and some new ones derived in this paper, on a small but fully heterogeneous MPI platform. Our results show the superiority of those heuristics which fully take into account the relative capacity of the communication links.
Type de document :
Communication dans un congrès
PDP'2006, 14th Euromicro Workshop on Parallel, Distributed and Network-based Processing, 2006, Montbéliard-Sochaux, France. IEEE Computer Society Press, 2006
Liste complète des métadonnées

https://hal.inria.fr/hal-00804402
Contributeur : Equipe Roma <>
Soumis le : mardi 20 novembre 2018 - 17:15:25
Dernière modification le : mercredi 21 novembre 2018 - 09:20:08

Fichier

europdp.pdf
Fichiers produits par l'(les) auteur(s)

Identifiants

  • HAL Id : hal-00804402, version 1

Collections

Citation

Jean-François Pineau, Yves Robert, Frédéric Vivien. Off-line and on-line scheduling on heterogeneous master-slave platforms. PDP'2006, 14th Euromicro Workshop on Parallel, Distributed and Network-based Processing, 2006, Montbéliard-Sochaux, France. IEEE Computer Society Press, 2006. 〈hal-00804402〉

Partager

Métriques

Consultations de la notice

227

Téléchargements de fichiers

3