Time optimal linear schedules for algorithms with uniform dependencies
- 1 June 1991
- journal article
- Published by Institute of Electrical and Electronics Engineers (IEEE) in IEEE Transactions on Computers
- Vol. 40 (6) , 723-742
- https://doi.org/10.1109/12.90251
Abstract
The authors address the problem of identifying optimal linear schedules for uniform dependence algorithms so that their execution time is minimized. Procedures are proposed to solve this problem based on the mathematical solution of a nonlinear optimization problem. The complexity of these procedures is independent of the size of the algorithm. Actually, the complexity is exponential in the dimension of the index set of the algorithm, and for all practical purposes, very small due to the limited dimension of the index set of algorithms of practical interest. A particular class of algorithms for which the proposed solution is greatly simplified is considered, and the corresponding simpler organization procedure is provided.Keywords
This publication has 13 references indexed in Scilit:
- Time optimal linear schedules for algorithms with uniform dependenciesPublished by Institute of Electrical and Electronics Engineers (IEEE) ,2003
- Independent partitioning of algorithms with uniform dependenciesIEEE Transactions on Computers, 1992
- A design methodology for synthesizing parallel algorithms and architecturesJournal of Parallel and Distributed Computing, 1986
- Partitioning and Mapping Algorithms into Fixed Size Systolic ArraysIEEE Transactions on Computers, 1986
- The Design of Optimal Systolic ArraysIEEE Transactions on Computers, 1985
- Automatic synthesis of systolic arrays from uniform recurrent equationsACM SIGARCH Computer Architecture News, 1984
- The parallel execution of DO loopsCommunications of the ACM, 1974
- Convex AnalysisPublished by Walter de Gruyter GmbH ,1970
- The Organization of Computations for Uniform Recurrence EquationsJournal of the ACM, 1967
- Parallel Methods for the Numerical Integration of Ordinary Differential EquationsMathematics of Computation, 1967