Partitioning and scheduling to counteract overhead

Abstract

We introduce a scheduling model, inspired by data flow computers, in which the overhead incurred in a system as well as computation time are described explicitly. Using this model, we provide algorithms for partitioning programs so as to minimize their completion time. In the traditional data flow paradigm, every instruction is considered a 'task', and it is scheduled for execution as early as possible. Implementations of this scheme, however, involve overheads which affect the running time of the programs. We propose to partition the program into larger grains, each containing one or more instructions, such that scheduling those grains would result in minimizing the completion time. Our model accounts for both the overhead incurred when executing a program and the actual execution time of its instructions. Within this framework we derive lower and upper bounds on the execution time of programs represented as trees and DAGs. We provide algorithms for optimally partitioning such programs when there are enough execution units. The algorithms have time complexity O(| V | 2) and O(| V | 5) for trees and DAGs, respectively (where | V | is the number of nodes). In the case of a limited number of execution units, we show that the algorithm for trees approximates the best solution with a ratio of 4. Using the same proof techniques we show sufficient conditions for approximating the problem for DAGs, noting that approximation is the best that can be sought for as the problem is NP-complete. The scheduling problem solved is general, and its solution can also be used for scheduling problems which have been studied before outside the data flow paradigm. Some of the results are also applicable to existing data flow machines, and to simulations of data flow programs on other machines.