Int. J. of Foundations of Computer Sci. 9 (4), 1998, pp. 351-375.
Ö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 present an algorithm based on generating functions
for constructing a formula for these numbers $d_n$.
The algorithm has been implemented as a Mathematica program.
Example runs
and the symbolic formulas for processor lower bounds automatically
produced by the algorithm
for {\em Matrix-Vector Product\/},
{\em Triangular Matrix Product\/}, and {\em Gaussian Elimination\/}
problems are presented.
Our approach actually solves the following more general problem:
Given an arbitrary $ r \times s $
integral matrix ${\bf A}$ and $r$-dimensional integral vectors
${\bf b}$ and ${\bf c}$,
let $d_n$ ($ n= 0, 1, \ldots $)
be the number of solutions in non-negative integers to the system
${\bf A z} = n \/ \/ {\bf b } + {\bf c} $.
Calculate the (rational)
generating function $\sum_{n \geq 0 } d_n t^n \/$ and construct a
formula for $d_n$.
omer@cs.ucsb.edu