Systolic array: Difference between revisions

Revision as of 13:32, 22 April 2006

Revision as of 11:53, 7 May 2006

Line 1:

ByIn analogy with the regular pumping of blood[[computer by the heartarchitecture]], a '''systolic array''' is an arrangement of [[central processing unit|processors]] s in an [[array]] (often rectangular) where data flows synchronously across the [[array]] between neighbours, usually with different data flowing in different directions. The name derives from analogy with the regular pumping of blood by the heart.

[[H. T. Kung]] and [[Charles E. Leiserson]] published the first paper describing systolic arrays in [[1978]]; however, the first machine known to have used the technique was the Mark II [[Colossus computer]].

Each [[central processing unit|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|matrix multiplication]]. One [[matrix (math)|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 across the array.