Broadcast Normalization in Systolic Design

When a sequential algorithm is directly mapped into an array of processing elements, quite likely data broadcasts are required and their source places vary during the computation. We introduce a normalization method to fix the positions of the broadcast sources so that the derived design can be further transformed by retimings into a systolic array. Our method is fully illustrated in designing systolic arrays for enumeration sort, solving simultaneous linear equations, and computing transitive closure.