Systolic array: Difference between revisions

Revision as of 13:10, 20 February 2007

Revision as of 09:07, 13 March 2007

Line 1:

{{cleanup|December 2006}}

The name derives from analogy with the regular pumping of blood by the heart. In [[computer architecture]], a '''systolic array''' is an arrangement of [[data processing unit]]s ([[DPU]]s, similar to [[central processing unit]]s ([[CPU]])s, but without a [[Programprogram counter]], since operation is transport-triggered, i.e., by the arrival of a data object (also used in [[Transporttransport triggered architecture]]s), in an [[array]] (often rectangular) where data flows across the array between neighbours, usually with different data flowing in different directions. The [[Datadata stream]]s entering and leaving the ports of the array are generated by [[auto-sequencing memory]] units (ASMs). Each ASM includes a [[Datadata counter]]. In [[Embedded System]]s a data stream may also be input from and/or output to an external source.

The systolic array paradigm, data-stream-driven by data counters, is the counterpart of the von Neumann paradigm, instruction-stream-driven by a program counter (see [[von Neumann]] or [[von Neumann architecture]]). Because a systolic array includes multiple data counters, it supports [[data parallelism]]. [[Systole|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 [[Colossus computer|Colossus Mark II]] in 1944.

Line 10:

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.

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 [[super systolic array]], a generalization of the systolic array not being restricted to regular data dependencies.

==Super systolic array==

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

Because the classical synthesis methods (algebraic, i. e., projection-based synthesis), yielding only uniform [[Reconfigurable computing|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 [[Super systolic array]]SSA, a generalization of the systolic array not limitedbeing restricted to regular data dependencies.

==See also==