Time optimal linear schedules for algorithms with uniform dependencies
- 6 January 2003
- conference paper
- Published by Institute of Electrical and Electronics Engineers (IEEE)
- Vol. c 34, 393-402
- https://doi.org/10.1109/arrays.1988.18079
Abstract
The problem of identifying the time-optimal linear schedules for uniform dependence algorithms with any convex-polyhedron index set is addressed. Optimization procedures are proposed, and the class of algorithms is identified for which the total execution times by the optimal linear schedule and the free schedule that schedules the computation to execute as soon as its operands are available are equal. This method is useful in mapping algorithms onto systolic/MIMD (multiple-instruction, multiple-instruction stream) systems.Keywords
This publication has 7 references indexed in Scilit:
- Time optimal linear schedules for algorithms with uniform dependenciesPublished by Institute of Electrical and Electronics Engineers (IEEE) ,2003
- 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
- The Organization of Computations for Uniform Recurrence EquationsJournal of the ACM, 1967