Systolic array: Difference between revisions

Revision as of 19:41, 21 March 2019

Revision as of 09:54, 6 May 2019

Line 4:

==Applications==

Systolic arrays are often hard-wired for specific operations, such as "multiply and accumulate", to perform massively [[parallel computing|parallel]] integration, [[convolution]], [[correlation]], [[matrix multiplication]] or data sorting tasks. They are also used for [[dynamic programming]] algorithms, used in DNA and protein [[sequence analysis]].

==Architecture==

Line 26:

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|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

between each node.

Line 35:

An example of a systolic [[algorithm]] might be designed for [[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.<ref>[http://web.cecs.pdx.edu/~mperkows/temp/May22/0020.Matrix-multiplication-systolic.pdf Systolic Array Matrix Multiplication]</ref>

Systolic arrays are arrays of [[data processing unit|DPU]]s 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.