Back to Search
Start Over
A scalable clustering-based task scheduler for homogeneous processors using DAG partitioning
- Source :
- [Research Report] RR-9185, Inria Grenoble Rhône-Alpes. 2018, pp.1-34
- Publication Year :
- 2018
- Publisher :
- HAL CCSD, 2018.
-
Abstract
- When scheduling a directed acyclic graph (DAG) of tasks on computationalplatforms, a good trade-off between load balance and data locality isnecessary. List-based scheduling techniques are commonly used greedy approachesfor this problem. The downside of list-scheduling heuristicsis that they are incapable of making short-term sacrifices for the globalefficiency of the schedule. In this work, we describe newlist-based scheduling heuristics based on clustering for homogeneousplatforms, 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 viewof the graph. Furthermore, since the partition is acyclic, we can scheduleeach part completely once its input tasks are ready to be executed. Wepresent an extensive experimental evaluation showing the trade-offs betweenthe 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 caseswith many communications.; Lors de l'ordonnancement d'un graphe dirigé acyclique (DAG) de tâches sur une plate-forme, un bon compromis entre équilibrage de charge et localité des données est nécessaire.Les techniques d'ordonnancement de liste sont des approches gloutonnescommunément utilisées pour ce problème. Les inconvénients de telles heuristiques de liste sont qu'ellessont incapables de faire des sacrifices à court terme pour que l'ordonnancementglobal soit plus efficace. Dans ces travaux, nous décrivons de nouvelles heuristiques d'ordonnancement de listepour des plates-formes homogènes, avec un modèle de communications duplexe un-port réaliste. Notre approche se base sur un partitionnement acycliquedu DAG, car les parties ainsi formées permettent d'avoir une bonne localité des donnéestout en conservant une vue générale du graphe. De plus, étant donné que la partition est acyclique,nous pouvons ordonnancer chaque partie entièrement une fois que ses tâches d'entrée sont prêtes à être exécutées. Nous présentons une évaluation expérimentale des algorithmes pour montrerles compromis entre la granularité des partitions et le parallélisme, et commentcela affecte l'ordonnancement. De plus, nous comparons nos heuristiques aux meilleurscompétiteurs de la littérature, et nous obtenons un temps d’exécution total plus de trois fois meilleur dans des cas avec de nombreuses communications.
- Subjects :
- Directed acyclic graphs
List scheduling
Concurrency
Partitionnement
Localité des données
[INFO.INFO-DS]Computer Science [cs]/Data Structures and Algorithms [cs.DS]
Data locality
Concurrence
Graphes dirigés acycliques
[INFO.INFO-DC]Computer Science [cs]/Distributed, Parallel, and Cluster Computing [cs.DC]
Clustering
Partitioning
Ordonnancement de liste
Subjects
Details
- Language :
- English
- Database :
- OpenAIRE
- Journal :
- [Research Report] RR-9185, Inria Grenoble Rhône-Alpes. 2018, pp.1-34
- Accession number :
- edsair.od.......212..691a6a3820e950d3f6e66062296076b1