Proc. IEEE 1998 IPPS/SPDP Symposium, Orlando, March 1998, pp. 105-109.
Ömer Egecioglu and Peter Cappello
Processor Lower Bound Formulas for
Array Computations and Parametric Diophantine Systems
Abstract.
Using a directed acyclic graph (dag) model of algorithms,
we solve a problem related to precedence-constrained multiprocessor
schedules for array computations:
Given a sequence of dags and linear schedules parametrized by $n$,
compute a lower bound on the
number of processors required by the schedule as a function of $n$.
In our formulation, the number of tasks that are scheduled for execution
during any fixed time step is the number of
non-negative integer solutions $d_n$ to a set of parametric linear Diophantine
equations. We illustrate an algorithm based on generating functions
for constructing a formula for these numbers $d_n$.
The algorithm has been implemented as a Mathematica program.
An example run and the symbolic formula for processor lower bounds automatically
produced by the algorithm for Gaussian Elimination is presented.
omer@cs.ucsb.edu