You must add a |reason= parameter to this Cleanup template – replace it with {{Cleanup|December 2006|reason=<Fill reason here>}}, or remove the Cleanup template.
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 units (DPUs, similar to central processing units (CPU)s, but without a Program counter, since operation is transport-triggered, i.e., by the arrival of a data object (also used in Transport triggered architectures), in an array (often rectangular) where data flows across the array between neighbours, usually with different data flowing in different directions. The Data streams entering and leaving the ports of the array are generated by auto-sequencing memory units (ASMs). Each ASM includes a Data counter. In Embedded Systems 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.
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 Mark II in 1944.
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 across the array.
Because the classical synthesis methods (algebraic, i.e., projection-based synthesis), yielding only uniform 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 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 limited to regular data dependencies.
See also
- SISAL
- KressArray - Reconfigurable version of Super systolic array
External links
- Instruction Systolic Array (ISA)
- KressArray
- Generalization of the systolic array (Super systolic array)
This article is based on material taken from the Free On-line Dictionary of Computing prior to 1 November 2008 and incorporated under the "relicensing" terms of the GFDL, version 1.3 or later.