Uniform recurrence equations

R. Karp, R. Miller, and S. Winograd. The organization of computations for uniform recurrence equations. Journal of the Association for Computing Machinery, 14, number 3, pages 563-590, July 1967. 

V. van Dongen and P. Quinton. Uniformization of linear recurrence equations a step towards the automatic synthesis of systolic arrays. IEEE International Conf. on Systolic Arrays, San Diego, pages 473-482, May 1988. 

In general, the extracted DG is not necessarily uniform. In order to remedy this situation, several techniques are discussed in chapters 3 and 6. This leads to uniform recurrence equations or UREs. The next design step is a linear space-time transformation [18, 16, 3]. Chapters 3, 5, and 6 discuss automated techniques to steer this step, including several extensions which are not directly essential for our demonstrator here. The space-time (S-T) transformation step is concerned with the allocation of a processor and a time slot to each node of the... 

Many design methods have been proposed to synthesize RAAs. The majority of these methods (see chapter 1 for an overview) are based on an affine transformation (first described by Quinton [15] and Moldovan [12]) to map the index space of the application description to time and processor space. The use of such a transformation method simplifies the design task considerably and requires only a few parameters to characterize a design completely. Unfortunately, most of these methods start from a relatively low level specification, using sets of UREs (uniform recurrence equations) [3] or CUREs (conditional uniform recurrence equations) [17] to describe an application. Moreover, especially in the case of real-time signal processing applications, the resulting architecture is usually unnecessarily fast or too slow. 

P. Quinton. Automatic synthesis of systolic arrays from recurrent uniform equations. 11th Int. Symp. Computer Architecture, Ann Arbor, pages 208-214, Jun 1984. 

---