MAPPING LINEAR RECURRENCE EQUATIONS ONTO SYSTOLIC ARCHITECTURES

In this paper, we describe a methodology for mapping normal linear rec urrence equations onto a spectrum of systolic architectures. First, we provide a method for mapping a system of directed recurrence equation s, a subclass of linear recurrence equations, onto a very general arch itecture referred to as basic systolic architecture and establish corr ectness of the implementation. We also show how efficient transformati ons/implementations of programs for different systolic architectures c an be obtained through transformations such as projections and transla tions. Next, we show that the method can be applied for the class of n ormal linear recurrence equations using the method for the class of di rected recurrence equations. Finally, we provide a completely automate d procedure called cubization to achieve better performance while mapp ing such equations. The method is illustrated with examples and a comp arative evaluation is made with other works.