Skip to Main content Skip to Navigation
New interface
Conference papers

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 metadata
Contributor : Equipe Roma Connect in order to contact the contributor
Submitted on : Friday, February 8, 2013 - 11:12:13 AM
Last modification on : Tuesday, October 25, 2022 - 4:16:41 PM

Links full text



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⟩



Record views