PARTITIONING AND SCHEDULING TO COUNTERACT OVERHEAD

We introduce a scheduling model, inspired by data flow computers, in w hich the overhead incurred in a system as well as computation time are described explicitly. Using this model, we provide algorithms for par titioning programs so as to minimize their completion time. In the tra ditional data flow paradigm, every instruction is considered a 'task', and it is scheduled for execution as early as possible. Implementatio ns 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 schedulin g those grains would result in minimizing the completion time. Our mod el accounts for both the overhead incurred when executing a program an d the actual execution time of its instructions. Within this framework we derive lower and upper bounds on the execution time of programs re presented as trees and DAGs. We provide algorithms for optimally parti tioning such programs when there are enough execution units. The algor ithms 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 lim ited number of execution units, we show that the algorithm for trees a pproximates 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 fo r as the problem is NP-complete. The scheduling problem solved is gene ral, and its solution can also be used for scheduling problems which h ave been studied before outside the data flow paradigm. Some of the re sults are also applicable to existing data flow machines, and to simul ations of data flow programs on other machines.