TRANSFORMATION OF NESTED LOOPS INTO UNIFORM RECURRENCES AND THEIR MAPPING TO REGULAR PROCESSOR ARRAYS

A methodology for transforming a class of iterative algorithms, expres sed in nested loops, into Uniform Recurrent Equation (URE) forms and t heir mapping into regular processor array architectures is presented. The propagation space of the variables of the original nested loop is specified by a system of linear equations formed by their index functi ons. The data Row within the index space, is then localized by the der ivation of a set of parametric dependence vectors, which eventually ca n be used to transform the initial algorithm into a set of UREs. The m apping of the UREs is accomplished by decomposition of the index space into independent subsets of variable instances using the derived depe ndence vectors. The dependence graphs of the subsets are normalized an d subsequently, are mapped on the processor array architecture. The ex ploitation of the independent subsets leads to significant improvement of the efficiency of the processor array compared to architectures de rived by using linear transformations of the entire index space. Under certain conditions, only local interconnections in the processor arra y are required. The proposed methodology is illustrated by the design of alternative processor arrays implementing the convolution algorithm .