Systolic Arrays

copied from http://www.ee.latrobe.edu.au/notes/adv.micros/systolic.html
I appriciate to the author

Systolic arrays are examples of single-instruction-multiple-data machines in which each processing element is only capable of performing a single very simple operation. The power behind systolic arrays comes from the way in which the data flows between the processing elements. Typically a systolic array is capable of performing a single operation such as matrix multiplication or inversion. They are thus special purpose machines used mainly in dedicated equipment and not in general purpose computers.

The systolic array shown in figure 18 performs the multiplication of a vector and a matrix. The vector is fed in at the left of the systolic array while the matrix is fed in through the top of the elements. The resulting vector appears in a serial form at the left of the array. Each processing element is required to calculate the inner product .EQ Y ~ <- ~ Y + A times B .EN Provided that the vector and array elements are fed into the systolic array at the correct times, the resultant vector will appear at the left of the array after several clock cycles.

Figure 19 shows a different connection of the same processing elements which will compute the product of two matrices. The two matrices are fed into the array from top left and top right, with the product emerging from the top of the array.

Some of the possible two-dimensional systolic arrays

Some of the possible two-dimensional systolic arrays are shown in figure 20 although others are possible. Three and higher dimensional systolic arrays are possible, although little work has been done on them.

Another method of increasing the power of systolic arrays is to chain them together. One example is shown in figure 21 which computes the least squares fit to all the data which have arrived at any given moment.

In Computer, January 1982, Kung gives many examples of problems which can be solved using systolic arrays. These include convolution, finite impulse response and infinite impulse response filtering, discrete Fourier transform, interpolation, matrix-vector and matrix-matrix multiplication, solution of linear systems, and various non-numeric applications.

Systolic arrays may be used to solve many regular problems containing repetitive operations on large arrays of data. They are not yet suited to general purpose computers, although with the development of more general programmable processing elements, programmable systolic arrays may be possible.