Converting sequential iterative algorithms to recurrent equations for automatic design of systolic arrays
- 6 January 2003
- conference paper
- Published by Institute of Electrical and Electronics Engineers (IEEE)
Abstract
The authors describe a procedure to transform a class of sequential iterative algorithms to systems of (uniform) recurrent equations (REs) from which systolic arrays can automatically be derived. They derive an equivalent class of systems of recurrent equations for a class of sequential iterative algorithms. First, they construct two formal models: A for the class of sequential algorithms they consider and R for the REs. Then they construct a procedure which maps an algorithm in A on a corresponding one in R. The essence of the method is to find the trace of the variables in the former algorithm. The method described is general and can be implemented in a design system for systolic arrays.Keywords
This publication has 6 references indexed in Scilit:
- Design framework for systolic-type arraysPublished by Institute of Electrical and Electronics Engineers (IEEE) ,2005
- Optimal Systolic Design for the Transitive Closure and the Shortest Path ProblemsIEEE Transactions on Computers, 1987
- 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 equationsPublished by Association for Computing Machinery (ACM) ,1984
- Why systolic architectures?Computer, 1982