Output- and input-stationary

The same matrix multiply in three dataflows side by side: what stays put, what moves, and what that costs in memory reads, link hops and register writes.

Loading the animation…

Concept

Chapter 2 held the weights still. That is one of three choices for a matrix multiply, each named after the operand that stays put in each PE (the names come from Chen, Emer and Sze's taxonomy for the Eyeriss accelerator, which adds row-stationary for convolutions; SCALE-Sim, a systolic-array simulator, uses these three for matrix multiplies):

Weight-stationary (WS): $B$ stays; $A$ streams in from the left; partial sums move down. A $K \times N$ block of PEs.
Output-stationary (OS): $C$ stays. $a_{mk}$ enters row $m$ from the left and $b_{kn}$ enters column $n$ from the top, both skewed, and they meet in PE $(m, n)$ at cycle $k + m + n$ , which adds their product to its own accumulator. Nothing but 8-bit operands moves until the end, when the finished results drain out. An $M \times N$ block.
Input-stationary (IS): $A$ stays (PE $(k, m)$ holds $a_{mk}$ ); the columns of $B$ stream in from the left; partial sums move down. It is weight-stationary on the transposed problem $C^\top = B^\top A^\top$ . A $K \times M$ block.

The animation runs all three on the same 3 × 3 by 3 × 3 problem on one clock, and counts what each moves. When the problem fits the array, all three read every element of $A$ and $B$ from the buffers exactly once (18 reads) and write each result once (9), and all three make the same number of PE-to-PE hops (45). The difference is what hops. WS and IS pass a partial sum down at every hop between rows: 18 partial-sum hops here. OS keeps its sums in place and moves them only when draining: 9. That matters because partial sums are wide: 8-bit operands accumulate into 32-bit sums. At 128 × 128 × 128, WS moves 91,553,792 bits between PEs and OS 66,584,576, though OS writes its accumulator registers more often (7,331,840 register writes against 5,251,072).

The bigger difference shows when the problem does not fit, which is the normal case: the stationary matrix is the one that gets reused across a whole stream, and the dataflow decides which matrix is tiled, which is re-read, and where partial sums of a split $K$ go (chapter 5).

Loading the animation…

Concept

Here is output-stationary with the numbers (switch to input-stationary to watch $A$ held and $B$ streamed). Every PE's sky "c" is its accumulator: it gains one term per cycle as the blue $a$ from the left and the vermillion $b$ from above pass through. After the last product the results drain down the columns, one row per cycle.

This animation is checked against RTL. The author's Interview RTL challenge is a parameterised SystemVerilog output-stationary array with internal skew registers. This site's rtl/check_rtl.py runs it in Verilator 5.020 on 3 problems (including full-range signed INT8) and compares every accumulator after every clock edge with this model: 613 values over 44 edges, 0 mismatches. (The RTL reads its results out in parallel rather than draining them, so after the last product the check requires it to hold $C$ .) The model page has the details.

Maths

Output-stationary timing. Row $m$ of $A$ is delayed $m$ cycles and column $n$ of $B$ is delayed $n$ cycles, so $a_{mk}$ enters at cycle $k + m$ and reaches PE $(m, n)$ after $n$ more hops, at $k + m + n$ ; $b_{kn}$ enters at $k + n$ and reaches PE $(m, n)$ after $m$ hops, at the same cycle. The last product, $k = K-1$ in PE $(M-1, N-1)$ , happens at cycle $K + M + N - 3$ , so with an $M$ -cycle drain

T_{\text{OS}} = (K + M + N - 2) + M .

Counting the movement. Reads: every $a_{mk}$ and $b_{kn}$ enters once, $MK + KN$ . Operand hops: $a_{mk}$ crosses $N - 1$ links, $b_{kn}$ crosses $M - 1$ : $MK(N-1) + KN(M-1)$ . Draining moves $c_{mn}$ down $M - 1 - m$ rows: $\tfrac12 N M(M-1)$ . For weight-stationary the activation hops are $MK(N-1)$ , each $c_{mn}$ 's partial sum makes $K - 1$ hops, $MN(K-1)$ , and loading moves $w_{kn}$ down $k$ rows, $\tfrac12 NK(K-1)$ . With $M = K = N$ both totals are $\tfrac52 N^2 (N-1)$ hops. The model counts every hop in every frame, and the tests check the counts against these closed forms for every dataflow and shape.

Code

Output-stationary's PE, cut from src/lib/sa/model.ts: both operands arrive from neighbours (or the edges), and only the accumulator stays.

cell[1] = hIn;
cell[2] = vIn;
let acc = prev[mm]![nn]![3]!;
if (hIn !== null && vIn !== null) {
  /* c8 ignore next */
  if (hIn[2] !== vIn[1]) throw new Error("operands out of step");
  cell[4] = [hIn[0], vIn[0]];
  cnt.macs += 1;
  cnt.regWrites += 1;
  acc = [acc[0] + hIn[0] * vIn[0], mm, nn, acc[3] + 1];
}
cell[3] = acc;

The check that the two operands belong to the same $k$ never fires: the skew guarantees it, and the tests run every shape.