Automatic Processor Lower Bound Formulas for Array Computations

In the directed acyclic graph (dag) model of algorithms, consider the following problem for precedence-constrained multiprocessor schedules for array computations: Given a sequence of dags and linear schedules parameterized byÒ, compute a lower bound on the number of processors required by the schedule as a function ofÒ. This problem is formulated so that the number of tasks that are scheduled for execution during any fixed time step is the number of non-negative integer solutions�Òto a set of parametric linear Diophantine equations. Generating function methods are then used for constructing a formula for the numbers �Ò. We implemented this algorithm as a Mathematica program. This paper is an overview of the techniques involved and their applications to well-known schedules for Matrix-Vector Product, Triangular Matrix Product, and Gaussian Elimination dags. Some example runs and automatically produced symbolic formulas for processor lower bounds by the algorithm are given