Loading...
Please wait, while we are loading the content...
Similar Documents
Automatic Processor Lower Bound Formulas for Array Computations (1998)
| Content Provider | CiteSeerX |
|---|---|
| Author | Cappello, Peter Egecioglu, Ömer |
| Abstract | 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 n, compute a lower bound on the number of processors required by the schedule as a function of n. 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 dn to a set of parametric linear Diophantine equations. Generating function methods are then used for constructing a formula for the numbers dn . 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 MatrixVector 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. |
| File Format | |
| Volume Number | 9 |
| Journal | International Journal of Foundations of Computer Science |
| Language | English |
| Publisher Date | 1998-01-01 |
| Access Restriction | Open |
| Subject Keyword | Array Computation Automatic Processor Lower Bound Formula Parametric Linear Diophantine Equation Triangular Matrix Product Non-negative Integer Solution Following Problem Symbolic Formula Mathematica Program Function Method Directed Acyclic Graph Matrixvector Product Example Run Gaussian Elimination Dag Well-known Schedule Linear Schedule Fixed Time Step Precedence-constrained Multiprocessor Schedule |
| Content Type | Text |
| Resource Type | Article |
