Critical Path and Area Based Scheduling of Parallel Task Graphs on Heterogeneous Platforms

Tchimou N'Takpé (1) , Frédéric Suter (1)

1 ALGORILLE - Algorithms for the Grid

While most parallel task graphs scheduling research has been done in the context of single homogeneous clusters, heterogeneous platforms have become prevalent and are extremely attractive for deploying applications at un- precedented scales. In this paper we address the need for scheduling techniques for parallel task applications for heterogeneous clusters of clusters by proposing a method to adapt existing parallel task graphs scheduling heuristics that have proved to be efficient on homogeneous environments. The contributions of this paper are: (i) a novel "virtual" cluster methodology for handling platform heterogeneity; (ii) a novel task placement step, designed to determine whether the placement step of heuristics for homogeneous platforms is adapted to the heterogeneous case; (iii) an empirical evaluation in a wide range of platform and application scenarios. This study shows that the proposed heuristics achieve better performance than the original when platform are heterogeneous and we discuss a number of trends apparent in our results.

Domaines: Algorithme et structure de données [cs.DS]

Tchimou N'Takpé, Frédéric Suter. Critical Path and Area Based Scheduling of Parallel Task Graphs on Heterogeneous Platforms. 12th International Conference on Parallel and Distributed Systems - ICPADS'06, Jul 2006, Minneapolis, United States. ⟨10.1109/ICPADS.2006.32⟩. ⟨inria-00108490⟩