Skip to Main content Skip to Navigation
Conference papers

A scalable clustering-based task scheduler for homogeneous processors using DAG partitioning

Abstract : When scheduling a directed acyclic graph (DAG) of tasks with communication costs on computational platforms, a good trade-off between load balance and data locality is necessary. List-based scheduling techniques are commonly-used greedy approaches for this problem. The downside of list-scheduling heuristics is that they are incapable of making short-term sacrifices for the global efficiency of the schedule. In this work, we describe new list-based scheduling heuristics based on clustering for homogeneous platforms, under the realistic duplex single-port communication model. Our approach uses an acyclic partitioner for DAGs for clustering. The clustering enhances the data locality of the scheduler with a global view of the graph. Furthermore, since the partition is acyclic, we can schedule each part completely once its input tasks are ready to be executed. We present an extensive experimental evaluation showing the trade-offs between the granularity of clustering and the parallelism, and how this affects the scheduling. Furthermore, we compare our heuristics to the best state-of-the-art list-scheduling and clustering heuristics, and obtain more than three times better makespan in cases with many communications.
Complete list of metadatas

Cited literature [30 references]  Display  Hide  Download

https://hal.inria.fr/hal-02082794
Contributor : Equipe Roma <>
Submitted on : Thursday, March 28, 2019 - 2:34:45 PM
Last modification on : Wednesday, February 26, 2020 - 11:14:18 AM
Long-term archiving on: : Saturday, June 29, 2019 - 2:16:09 PM

File

ipdps.pdf
Files produced by the author(s)

Identifiers

Collections

Citation

Yusuf Özkaya, Anne Benoit, Bora Uçar, Julien Herrmann, Umit Catalyurek. A scalable clustering-based task scheduler for homogeneous processors using DAG partitioning. IPDPS 2019 - 33rd IEEE International Parallel & Distributed Processing Symposium, May 2019, Rio de Janeiro, Brazil. pp.155-165, ⟨10.1109/IPDPS.2019.00026⟩. ⟨hal-02082794⟩

Share

Metrics

Record views

225

Files downloads

365