Mapping linear recurrence equations onto systolic architecture

Abstract

In this paper, we describe a methodology for mapping normal linear recurrence equations onto a spectrum of systolic architectures. First, we provide a method for mapping a system of directed recurrence equations, a subclass of linear recurrence equations, onto a very general architecture referred to as basic systolic architecture and establish correctness of the implementation. We also show how efficient transformations/implementations of programs for different systolic architectures can be obtained through transformations such as projections and translations. Next, we show that the method can be applied for the class of normal linear recurrence equations using the method for the class of directed recurrence equations. Finally, we provide a completely automated procedure called cubization to achieve better performance while mapping such equations. The method is illustrated with examples and a comparative evaluation is made with other works.