Improved lower bounds on time and processors for scheduling precedence graphs on multicomputer systems

Abstract

This paper improves lower bounds on the minimum number of processors and minimum time to execute a given directed acyclic task graph with communication delays. The given task graph is partitioned into a number of independent task graphs to arrive at sharper bounds. A drawback of the earlier best method is pointed out and corrected. The time taken to calculate the bounds is also less in comparison to the corrected method. These bounds are useful in comparing heuristic algorithms used for scheduling directed acyclic task graphs and as compiler tools in static scheduling-on parallel computers.