Institute of Embedded Systems

[BibTex]

Note: khzimmermann, AEG

Abstract: We propose two methods for the synthesis of systolic arrays from uniform recurrence equations. First, we discuss a synthesis method for mappingn-dimensional uniform recurrence equations ontok-dimensional systolic arrays with a two-dimensional system clock. In this method we are led by the idea that all space-time conflicts caused by a scalar valued causal timing function and an allocation function can be rule out by a second scalar valued timing function. Stacking both timing functions yields a two-dimensional clock. Second, we develop a method to synthesizek-dimensional arrays with a scalar valued clock from a large subclass ofn-dimensional uniform recurrence equations containing important algorithms from signal and image processing. This method is based on a decomposition of the domain of the uniform recurrence equations into subdomains according to a given procesor allocation which allows the construction of a timing function for the whole domain from timing functions for the subdomains. In this way, the problem of finding optimal timing functions is reduced to finding optimal functions for the subdomains which are usually easier to establish. This synthesis method exhibits simplicity but its drawback lies in its limited applicability.