ON TIME-OPTIMAL IMPLEMENTATION OF UNIFORM RECURRENCES ONTO ARRAY PROCESSORS VIA QUADRATIC-PROGRAMMING

Many important algorithms can be described by n-dimensional uniform re currences. The computations are then indexed by integral vectors of le ngth n and the data dependencies between computations can be described by the difference vector of the corresponding indexes which are indep endent 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 arra y processor embedded in k-space (1 less than or equal to k less than o r equal to n). Find an optimal linear function for the computation ind exes. We study a continuous approximation of this problem by passing f rom linear to quasi-linear timing functions. The resultant problem for mulation is then a quadratic programming problem which can be solved b y standard algorithms for quadratic or general nonlinear optimization problems. We demonstrate the effectiveness of our approach by several nontrivial test examples.