Synthesizing fully efficient systolic arrays

It is shown that in arrays derived by the conventional integral linear transformation, there always exists a basic direction ν such that one and only one out of δ consecutive processors is active at any time unit along any line parallel to ν. Therefore, one can merge δ neighboring processors along lines parallel to ν and derive a new array which is fully efficient. The new array has only 1/δ processors and has the same computation time complexity. The method is constructive: once the user has chosen the timing function and allocation function, the required ν can be generated automatically. After choosing ν, the appropriate quasi-affine allocation function can also be automatically derived, as can the additional registers, wires, and control for the processors. This indicates that it is always possible to synthesize a fully efficient systolic array in a practical system