Mutual Inclusivity of the Critical Path and its Partial Schedule on Heterogeneous Systems

The critical path of a group of tasks is an important measure that is commonly used to guide task allocation and scheduling on parallel computers. The critical path is the longest chain of dependencies in an acyclic task dependence graph. A problem arises on heterogeneous parallel machines where computation and communication costs can vary between different types of processor. Existing solutions for heterogeneous machines attempt to estimate the critical path using average values of computation and communication costs. However, this ignores opportunities to match specific tasks to specific classes of processor and communication links, and can result in quite misleading paths being identified as critical. We argue that an accurate critical path must consider the mapping of tasks to classes of processor and communication links. We formulate a polynomial time algorithm to find such a critical path. Our Critical Earliest Finish Time (CEFT) algorithm finds both the length of the critical path and an allocation of tasks to processors on that path. We compared CEFT experimentally to existing approaches such as averaging execution times across processors. The latter approach fails to accurately model the execution cost of tasks, and as a result fails to identify a correct critical path in 83.99% of cases in our experiments. We also adapted a critical path-oriented scheduling algorithm (CPOP) to use our critical path algorithm and found that the resulting schedules are faster.