Institute of Embedded Systems

[BibTex]

Note: khzimmermann, AEG

Abstract: Various methods for the synthesis of systolic arrays from signal and image processing algorithms have been developed in the past few years. In this paper, we propose a technique for the partitioning problem, the problem to synthesize systolic arrays whose size does not match the problem size. Our technique generalizes most of the known lattice-based approaches to the partitioning problem and combines the multiprojection method for the synthesis of systolic arrays with the locally sequential-globally parallel (LSGP) and locally parallel-globally sequential (LPGS) partitioning schemes. Starting from (1) a k-dimensional large-size systolic array obtained from a system of n-dimensional uniform recurrences by a space-time transformation and (2) an arbitrary lattice in k-space inducing a partitioning of the array into subarrays, a small-size systolic array with a scalar-valued system clock is constructed via the LSGP or LPGS paradigm. In particular, the allocation function for the small-size array can be written in closed form and the timing function is obtained from timing functions for the subdomains, the set of operations performed by the subarrays, by simple greedy algorithms. In this way, the problem of finding optimal timing functions can in various cases be reduced to finding optimal timing functions for the subdomains. For problems of large size, these greedy algorithms seem to be preferable when compared with existing integer or non-convex programming formulations for finding (sub-)optimal timing functions. We also provide some new results, a necessary and sufficient condition for the existence of counter data flow, a formal relationship between partitionings of processor space and index space of the uniform recurrences in terms of counter data flow, and the structural equivalence between the lattice-based LSGP and LPGS schemes applied to the partitioning of index and processor space.