 |
 |
 |
 |
 |
 |
 |
 |
 Processor Lower Bound Formulas for Array Computations and Parametric Diophantine Systems
 |
 |
 |
 |
 |
 |

Organization: | University of California at Santa Barbara |
Department: | Department of Computer Science |
Organization: | University of California at Santa Barbara |
Department: | Department of Computer Science |
 |
 |
 |
 |
 |
 |

International Journal of Foundations of Computer Science |
 |
 |
 |
 |
 |
 |
 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 out formulation, the number of tasks that are scheduled for execution during any fixed time step is the number of non-negative integer solutions dn to a set of parametric linear Diophantine equations. We present an algorithm based on generating functions for constructing a formula for these numbers dn. The algorithm has been implemented as a Mathematica program. Example runs and the symbolic formulas for processor lower bounds automatically produced by the algorithm are presented. Our approach actually solves the following more general problem: Given an arbitrary r x s integral matrix A and r-dimensional integral vectors b and c, let dn (n=0,1,...) be the number of solutions in non-negative integers to the system Az = nb + c. Calculate the (rational) generating function En>o^dnt^n and construct a formula for dn.
 |
 |
 |
 |
 |
 |

 |
 |