A Methodology for Mapping and Partitioning Arbitrary N-Dimensional Nested Loops into 2-Dimensional VLSI Arrays

A new methodology is proposed for mapping and partitioning arbitrary n-dimensional nested loop algorithms into 2-dimensional fixed size systolic arrays.Since planar VLSI arrays are easy to im- plement,our approach has good feasibility and applicability.In the transformation process of an algorithm,we take into account not only data dependencies imposed by the original algorithm but also space dependencies dictated by the algorithm transformation.Thus,any VLSI algorithm generated by our methodology has optimal parallel execution time and yet remains space-time conflict free. Moreover,a theory of the least complete set of interconnection matrices is proposed to reduce the computational complexity for finding all possible space transformations for a given algorithm.