Efficient Scheduling of Task Graph Collections on Heterogeneous Resources

Matthieu Gallet 1, 2, * Loris Marchal 1, 2, * Frédéric Vivien 1, 2, *
* Corresponding author
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.
Document type :
Conference papers
Complete list of metadatas

https://hal.inria.fr/hal-00786257
Contributor : Equipe Roma <>
Submitted on : Friday, February 8, 2013 - 11:12:13 AM
Last modification on : Tuesday, December 11, 2018 - 10:58:05 AM

Links full text

Identifiers

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. ⟨10.1109/IPDPS.2009.5161045⟩. ⟨hal-00786257⟩

Share

Metrics

Record views

107