Systolic array: Difference between revisions

Revision as of 16:35, 21 August 2019

Revision as of 19:54, 24 October 2019

Line 1:

{{Use dmy dates|date=October 2019}}

In [[parallel computing|parallel]] [[computer architectures]], a '''systolic array''' is a homogeneous [[Graph (discrete mathematics)|network]] of tightly coupled [[data processing unit]]s (DPUs) called cells or [[Node (computer science)|node]]s. Each node or DPU independently computes a partial result as a function of the data received from its upstream neighbors, stores the result within itself and passes it downstream. Systolic arrays were invented by [[H. T. Kung]] and [[Charles Leiserson]] who described arrays for many dense linear algebra computations (matrix product, solving systems of [[linear equation]]s, [[LU decomposition]], etc.) for banded matrices. Early applications include computing [[greatest common divisor]]s of integers and polynomials.<ref>http://www.eecs.harvard.edu/~htk/publication/1984-ieeetoc-brent-kung.pdf</ref>{{notFailed in source givenverification|date=February 2017}} They are sometimes classified as [[MISD|multiple-instruction single-data]] (MISD) architectures under [[Flynn's taxonomy]], but this classification is questionable because a strong argument can be made to distinguish systolic arrays from any of Flynn's four categories: [[SISD]], [[SIMD]], [[MISD]], [[MIMD]], as discussed later in this article.

The parallel input [[data]] flows through a network of hard-wired [[Microprocessor|processor]] nodes, which combine, process, [[merge algorithm|merge]] or [[sorting algorithm|sort]] the input data into a derived result. Because the [[wave]]-like propagation of data through a systolic array resembles the [[pulse]] of the human circulatory system, the name ''systolic'' was coined from medical terminology. The name is derived from [[systole]] as an analogy to the regular pumping of blood by the heart.

Line 26 ⟶ 27:

In spite of all of the above, systolic arrays are often offered as a classic example of MISD architecture in textbooks on [[parallel computing]] and in the engineering class. If the array is viewed from the outside as [[atomic operation|atomic]] it should perhaps be classified as '''SFMuDMeR''' = Single Function, Multiple Data, Merged Result(s).

Systolic arrays use a pre-defined computational flow graph that connects their nodes. [[Kahn process networks]] use a similar flow graph, but are distinguished by the nodes working in lock-step in the systolic array: in a Kahn network, there are FIFO queues

working in lock-step in the systolic array: in a Kahn network, there are FIFO queues

between each node.

Line 43:

==Application example==

{{incompleteExpand section|date=May 2016}}

;Polynomial evaluation

Line 56:

==Advantages and disadvantages==

{{references|Unreferenced section|date=December 2016}}

Pros

* Faster than general purpose processors