TRANSFORMATION OF NESTED LOOPS INTO UNIFORM RECURRENCES AND THEIR MAPPING TO REGULAR PROCESSOR ARRAYS
Efstathios D. Kyriakis-Bitzaros, Dimitrios Soudris, C.E. Goutis · Journal of Circuits Systems and Computers · 1996
A methodology for transforming a class of iterative algorithms, expressed in nested loops, into Uniform Recurrent Equation (URE) forms and their 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 functions. The data flow within the index space, is then localized by the derivation of a set of parametric dependence vectors, which eventually can be used to transform the initial algorithm into a set of UREs. The mapping of the UREs is accomplished by decomposition of the index space into independent subsets of variable instances using the derived dependence vectors. The dependence graphs of the subsets are normalized and subsequently, are mapped on the processor array architecture. The exploitation of the independent subsets leads to significant improvement of the efficiency of the processor array compared to architectures derived by using linear transformations of the entire index space. Under certain conditions, only local interconnections in the processor array are required. The proposed methodology is illustrated by the design of alternative processor arrays implementing the convolution algorithm.