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

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.