Mesh-Connected Arrays
Björn Lisper · 1990
We present square systolic arrays for per- forming a class of matrix permutations. This class can be described by the composition of two basic operations, namely (clockwise) rotation by 90°, and horizontal reflec- tion about the middle column. Four different arrays are presented: in-place reflection, in-place rotation, and on-the- fly versions of these that permute the matrix as it is being loaded into the array. These operations can be implemented very efficiently with local only control. The time bounds for each of the operations is optimal. We anticipate thzt such transformations will have practical applications in fast ma- nipulation of frame buffers and in image processing, as well as in interfacing diferent systolic arrays.