Some Space Considerations of Space-Time Mappings into Systolic Arrays

Abstract: In this paper the space-time mapping of the dependency matrix of an algo-rithm is used to study spatial properties of a systolic array implementation of a 3-nested loop structure. Elementary expressions are developed for both the number of processing elements and the area of the array. These expressions involve only the space-time trans-formation and the lengths of the loops. As well, characterizations have been found for the form of the space-time transformation which produces a systolic array with the minimum number of processing elements, and one which has both the minimum number of processing elements and the smallest area.