Institute of Embedded Systems

[BibTex]

Note: khzimmermann, AEG

Abstract: Many important algorithms can be described by n-dimensional uniform recurrences. The computations are then indexed by integral vectors of length n and the data dependencies between computations can be described by the difference vector of the corresponding indexes which are independent of the indexes. This paper addresses the following optimization problem: Given an n-dimensional uniform recurrence whose computation indexes are mapped by a linear function onto the processors of an array processor embedded in k-space (1 ≤ k ≤ n). Find an optimal linear function for the computation indexes. We study a continuous approximation of this problem by passing from linear to quasi-linear timing functions. The resultant problem formulation is then a quadratic programming problem which can be solved by standard algorithms for quadratic or general nonlinear optimization problems. We demonstrate the effectiveness of our approach by several nontrivial test examples.