Mapping nested loop algorithms into multi-dimensional systolic arrays

This study is concerned with transforming depth p-nested for loop algorithms into q-D systolic VLSI arrays, where 1 ≤ q ≤ p - 1. Previously, there existed necessary and sufficient conditions only for the cases when q = p - 1 and q = 1. The authors fill in this gap by giving formal conditions for correct transformations of a p-nested loop algorithm into a q-D systolic array for any q, 1 ≤ q ≤ p - 1. The techniques developed contribute towards the automatic design of special-purpose systolic arrays and automatic compilation onto more general-purpose programmable arrays.