A Scalable Clustering-based Task Scheduler For Homogeneous Processors Using Dag Partitioning

General information

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 three new list-based scheduling (meta-)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 (dagP, more on this here). 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.

If you use dagPscheduler, please cite:

• M. Yusuf Özkaya, Anne Benoit, Bora Uçar, Julien Herrmann, Ümit V. Çatalyürek
  "A scalable clustering-based task scheduler for homogeneous processors using DAG partitioning",
  IEEE International Parallel and Distributed Processing Symposium (IPDPS), 2019, p. 155-165.
  https://doi.org/10.1109/IPDPS.2019.00026

Download

Latest release: dagPschedule (Latest 04/13/2022)

Changelog

• April 2022
  • Fixed a small but important bug in dagP core implementation. Update applied to this release as well.
• July 2020
  • SConstruct updated for parallel compilation.
  • Updated command-line interface and texts in command-line help.
  • Initial release published.

If you have any questions or comments, please contact TDALab.