Content deleted Content added
Use consistent spelling for wavefront |
→Application example: convolution |
||
Line 42:
Systolic arrays (also known as ''wavefront processors''), were first described by [[H. T. Kung]] and [[Charles E. Leiserson]], who published the first paper describing systolic arrays in 1979. However, the first machine known to have used a similar technique was the [[Colossus computer|Colossus Mark II]] in 1944.
==Examples==
{{Expand section|date=May 2016}}
[[Horner's rule]] for evaluating a polynomial is:
Line 54 ⟶ 53:
A linear systolic array in which the processors are arranged in pairs: one multiplies its input by <math>x</math> and passes the result to the right, the next adds <math>a_j</math> and passes the result to the right.
=== Convolution ===
Consider a chain of processing elements (PEs), each performing a [[Multiply–accumulate operation|multiply-accumulate operation]]. It processes input data (<math>x_i</math>) and weights (<math>w_i</math>) systolically, meaning data flows through the array in a regular, rhythmic manner. The weights remain stationary within each PE, while the input data and partial sums (<math>y_i</math>) move in opposite directions.
Each PE performs the following operation:<math display="block">
\begin{aligned}
y_{out} &= y_{in} + w \cdot x_{in} \\
x_{out} &= x_{in}
\end{aligned}
</math>where:
* <math>x_{in}</math> is the input data.
* <math>y_{in}</math> is the incoming partial sum.
* <math>w</math> is the weight stored in the PE.
* <math>x_{out}</math> is the output data (passed to the next PE).
* <math>y_{out}</math> is the updated partial sum.
From the left, the input stream is <math>
\dots, x_3, 0, x_2, 0, x_1
</math>, and from the right, the output stream is <math>
y_1, y_2, y_3, \dots
</math>. If <math>
y_1, x_1
</math> enter the rightmost PE simultaneously, then the leftmost PE outputs<math display="block">
\begin{aligned}
y_1 &= w_1 x_1 + w_2 x_2 + w_3 x_3 + \cdots \\
y_2 &= w_1 x_2 + w_2 x_3 + w_3 x_4 + \cdots \\
&\vdots
\end{aligned}
</math>
==Implementations==
| |||