Institute of Embedded Systems

[BibTex]

Note: khzimmermann, AEG

Abstract: Many important algorithms in signal and image processing can be described by uniform recurrences. A common method for the synthesis of systolic arrays from uniform recurrences is based on space-time transformations each of which consisting of two linear mappings, an allocation and a timing function. In this paper, we address the problem of finding space-time transformations which are time-optimal or at least nearly time-optimal. For a given allocation function, a continuous relaxation of this problem is studied by passing from linear to quasi-linear timing functions. A parametrized linear programming formulation is provided for finding quasi-linear timing functions. The solution of each such linear problem, however, depends on the basis representation of the null space of the allocation function. Therefore, a branching approach is proposed for finding quasi-linear timing functions which are optimal or have at least low latency. It will be demonstrated by several large test examples that branching into hundreds or even thousands of linear subproblems can be computed with reasonable effort and often leads to an optimum linear timing function.