Mapping Linear Recurrences onto Systolic Arrays 1995

Abstract:  We present an automatic method for mapping a system of linear recurrence equations onto systolic architectures. First, we show that systolic architectures can be derived from linear recurrence equations using the notion of directed recurrence equations. Next, we provide a procedure called CUBIZATION to achieve better performance while mapping such equations. The CUBIZATION procedure is completely automated and can be implemented to design systolic programs for a very general architecture referred to as Basic Systolic Architecture (BSA). Using BSA, we obtain specific target architectures. The method is illustrated using a running example of Gauss-Jordan diagonalization. 1 Introduction In [6], we proposed a method to map a system of directed recurrence equations (DRE), a subclass of linear recurrence equations (LRE), which properly includes uniform recurrence equations onto systolic architecture. Here, we extend our method to LREs where the dependency vector at a point is a linear fun...