Systolic array

From Wikipedia, the free encyclopedia
A systolic array network in which each data processing unit (DPU) receives data from one or more input streams and/or other DPUs and sends data to one or more output streams and/or other DPUs

In computer architecture, a systolic array is a pipe network arrangement of processing units called cells. It is a specialized form of parallel computing, where cells (i.e. processors), compute data and store it independently of each other.

Description

A systolic array is composed of matrix-like rows of data processing units called cells. Data processing units (DPUs) are similar to central processing units (CPU)s, (except for the usual lack of a program counter,[1] since operation is transport-triggered, i.e., by the arrival of a data object). Each cell shares the information with its neighbours immediately after processing. The systolic array is often rectangular where data flows across the array between neighbour DPUs, often 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.

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

Systolic arrays are arrays of DPUs which are connected to a small number of nearest neighbour DPUs in a mesh-like topology. DPUs perform a sequence of operations on data that flows between them. Because the traditional systolic array synthesis methods have been practiced by algebraic algorithms, only uniform arrays with only linear pipes can be obtained, so that the architectures are the same in all DPUs. The consequence is, that only applications with regular data dependencies can be implemented on classical systolic arrays. Like SIMD machines, clocked systolic arrays compute in "lock-step" with each processor undertaking alternate compute | communicate phases. But systolic arrays with asynchronous handshake between DPUs are called wavefront arrays. One well-known systolic array is Carnegie Mellon University's iWarp processor, which has been manufactured by Intel. An iWarp system has a linear array processor connected by data buses going in both directions.

History

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. Because a systolic array usually sends and receives multiple data streams, and multiple data counters are needed to generate these data streams, it supports data parallelism. 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 a similar technique was the Colossus Mark II in 1944.

Applications

An application Example - Polynomial Evaluation

Horner's rule for evaluating a polynomial is:

y=(...(((a_{n}*x+a_{{n-1}})*x+a_{{n-2}})*x+a_{{n-3}})*x+...+a_{1})*x+a_{0}

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 a_{j} and passes the result to the right:

Advantages and Disadvantages

Pros

  • Faster
  • Scalable

Cons

  • Expensive
  • Highly specialized for particular applications
  • Difficult to build

Implementations

Cisco PXF network processor is internally organized as systolic array.[3]

See also

Notes

  1. ↑ The Paracel GeneMatcher series of systolic array processors do have a program counter. More complicated algorithms are implemented as a series of simple steps, with shifts specified in the instructions.
  2. ↑ Systolic Array Matrix Multiplication
  3. ↑ http://www.cisco.com/en/US/prod/collateral/routers/ps133/prod_white_paper09186a008008902a.html

References

  • H. T. Kung, C. E. Leiserson: Algorithms for VLSI processor arrays; in: C. Mead, L. Conway (eds.): Introduction to VLSI Systems; Addison-Wesley, 1979
  • S. Y. Kung: VLSI Array Processors; Prentice-Hall, Inc., 1988
  • N. Petkov: Systolic Parallel Processing; North Holland Publishing Co, 1992

External links

This article is issued from Wikipedia. The text is available under the Creative Commons Attribution/Share Alike; additional terms may apply for the media files.