zbMATH — the first resource for mathematics

List scheduling with and without communication delays. (English) Zbl 0797.68020
Summary: Empirical results have shown that the classical critical path (CP) list scheduling heuristic for task graphs is a fast and practical heuristic when communication cost is zero. In the first part of this paper we study the theoretical properties of the CP heuristic that lead to its near optimum performance in practice. In the second part we extend the CP analysis to the problem of ordering the task execution when the processor assignment is given and communication cost is nonzero. We propose two new list scheduling heuristics, the \(RCP\) and \(RCP^*\) that use critical path information and ready list priority scheduling. We show that the performance properties for \(RCP\) and \(RCP^*\), when communication is nonzero, are similar to CP when communication is zero. Finally we present an extensive experimental study and optimality analysis of the heuristics which verifies our theoretical results.

68M20 Performance evaluation, queueing, and scheduling in the context of computer systems
Full Text: DOI