Systolic array: Difference between revisions

Revision as of 13:47, 11 April 2007

Revision as of 09:26, 25 April 2007

Line 12:

An example of a systolic [[algorithm]] might be [[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.

Systolic Arrays

==Super systolic array==

Systolic arrays are arrays of processors which are connected to a small number of nearest neighbours in a mesh-like topology. Processors perform a sequence of operations on data that flows between them. Generally the operations will be the same in each processor, with each processor performing an operation (or small number of operations) on a data item and them passing it on to its neighbour. Like SIMD machines, systolic arrays compute in "lock-step" with each processor undertaking alternate

The '''[[super systolic array]]''' is a generalization of the systolic array.

compute | communicate

phases.

One well-known systolic array is CMU's iWarp processor, which has been manufactured by Intel. An iWarp system has a linear array processors connected by data buses going in both directions.

Because the classical synthesis methods (algebraic, i.e., projection-based synthesis), yielding only uniform [[Data Path Unit|DPU]] arrays permitting only linear pipes, systolic arrays could be used only to implement applications with regular data dependencies. By using [[simulated annealing]] instead, [[Rainer Kress]] came up with the SSA, a generalization of the systolic array not being restricted to regular data dependencies.

An Example - Poynomial Evaluation

Horner's rule for evaluating a polynomial is:

y = ((((anx + an-1)*x + an-2)*x + an-3)*x .... a1)*x + a0

A linear systolic array in which the processors are arranged in pairs:

one multiplies its input by x and passes the result to the right,

the next adds aj and passes the result to the right:

==See also==