Efficient Scheduling of Task Graph Collections on Heterogeneous Resources

Matthieu Gallet 1, 2, * Loris Marchal 1, 2, * Frédéric Vivien 1, 2, *
* Auteur correspondant
2 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 focus on scheduling jobs on computing grids. In our model, a grid job is made of a large collection of input data sets, which must all be processed by the same task graph or workflow, thus resulting in a collection of task graphs problem. We are looking for a competitive scheduling algorithm not requiring complex control. We thus only consider single-allocation strategies. In addition to a mixed linear programming approach to find an optimal allocation, we present different heuristic schemes. Then, using simulations, we compare the performance of our different heuristics to the performance of a classical scheduling policy in Grids, HEFT. The results show that some of our static-scheduling policies take advantage of their platform and application knowledge and outperform HEFT, especially under communication-intensive scenarios. In particular, one of our heuristics, DELEGATE, almost always achieves the best performance while having lower running times than HEFT.
Type de document :
Communication dans un congrès
IPDPS'2009 - International Parallel and Distributed Processing Symposium, 2009, Roma, Italy. IEEE Computer Society Press, 2009, 〈10.1109/IPDPS.2009.5161045〉
Liste complète des métadonnées

https://hal.inria.fr/hal-00786257
Contributeur : Equipe Roma <>
Soumis le : vendredi 8 février 2013 - 11:12:13
Dernière modification le : vendredi 20 avril 2018 - 15:44:24

Lien texte intégral

Identifiants

Collections

Citation

Matthieu Gallet, Loris Marchal, Frédéric Vivien. Efficient Scheduling of Task Graph Collections on Heterogeneous Resources. IPDPS'2009 - International Parallel and Distributed Processing Symposium, 2009, Roma, Italy. IEEE Computer Society Press, 2009, 〈10.1109/IPDPS.2009.5161045〉. 〈hal-00786257〉

Partager

Métriques

Consultations de la notice

81