  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.
