Loading...
Please wait, while we are loading the content...
Similar Documents
Processor Lower Bounds for Array Computations with Linear Schedules
| Content Provider | Semantic Scholar |
|---|---|
| Author | Cappello, Peter R. Egecioglu, Ömer |
| Copyright Year | 1997 |
| Abstract | Using a directed acyclic graph (dag) model of algorithms, this paper treats a problem related to precedence-constrained multiprocessor schedules for array computations: Given a dag and a valid linear schedule for it, compute a lower bound on the number of processors required by the schedule. This is an important practical problem: A good schedule uses time efficiently; a good mapping of nodes to processors uses energy efficiently. The lower bounds obtained are good; we know of no case where they are not exactly tight. Actually, a harder problem is solved: Given a parametrized family of dags and a correspondingly parametrized valid linear schedule, symbolically generate a processor lower bound formula. To visualize the method for computing this formula, the nodes, representing computational tasks, are viewed as a set of lattice points in a convex polyhedron. The number of tasks that are scheduled for execution during any given time step of a linear schedule is the number of non-negative integer solutions to a set of linear Diophantine equations parametrized by the number of nodes of the dag. An algorithm, based on construction of generating functions, is presented for computing these numbers. This is the first such algorithm to be reported. Using this algorithm and a symbolic algebra package, formulas for processor lower bounds are obtained automatically. The algorithm has been implemented as a Mathematica program. Example runs for Matrix-Vector Product, and Triangular Matrix Product problems are given. While widely applicable and elegant, it has worst case exponential running time. This is not surprising however; the simpler computation: ``Are any processors scheduled for a particular time step?'''' which is equivalent to ``Is a particular coefficient of the generating function nonzero?" is already known to be an NP-complete problem. |
| File Format | PDF HTM / HTML |
| Alternate Webpage(s) | http://www.cs.ucsb.edu/TRs/Docs/TRCS97-06.ps |
| Language | English |
| Access Restriction | Open |
| Content Type | Text |
| Resource Type | Article |
