systolic array

architecture, parallel (By analogy with the regular pumping

of blood by the heart) An arrangement of processors in an

array (often rectangular) where data flows synchronously

across the array between neighbours, usually with different

data flowing in different directions. H. T. Kung and Charles

Leiserson publish the first paper describing systolic arrays

in 1978 [reference?].

Each processor at each step takes in data from one or more

neighbours (e.g. North and West), processes it and, in the

next step, outputs results in the opposite direction (South

and East).

An example of a systolic algorithm might be matrix

multiplication. One matrix is fed in a row at a time from the

top of the array and is passed down the array, the other

matrix is fed in a column at a time from the left hand side of

the array and passes from left to right. Dummy values are

then passed in until each processor has seen one whole row and

one whole column. At this point, the result of the

multiplication is stored in the array and can now be output a

row or a column at a time, flowing down or accross the array.

See also Ruby, SISAL.

(1998-07-01)