Mathematica 9 is now available

Wolfram Library Archive


Courseware Demos MathSource Technical Notes
All Collections Articles Books Conference Proceedings
Title

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

P. Cappello
Organization: University of California at Santa Barbara
Department: Department of Computer Science
O. Egecioglu
Organization: University of California at Santa Barbara
Department: Department of Computer Science
Journal / Anthology

International Journal of Foundations of Computer Science
Year: 1998
Volume: 9
Issue: 4
Page range: 351-375
Description

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.
Subject

*Applied Mathematics > Computer Science