Visual walkthrough — Domain-specific accelerators

Here is the entire journey before we start walking it:

---

Step 1 — The atom: one multiply-accumulate

WHAT. The smallest thing our chip does is take two numbers, multiply them, and add the result onto a running total. We call this a multiply-accumulate, written MAC. In symbols:

$$\underset{\text{running sum}}{\underbrace{s}}\leftarrow \underset{\text{old sum}}{\underbrace{s}}+\underset{\text{one number}}{\underbrace{a}}\times \underset{\text{another number}}{\underbrace{b}}$$

Read the arrow "$\leftarrow$" as "becomes" — the box on the left is updated to the value on the right. So $s$ eats one more product $a\times b$ each time. Each of $a$, $b$, $s$ is one machine word.

WHY a MAC and not a plain multiply? Because matrix multiplication is nothing but a huge pile of "multiply two numbers and add them to a total." If the atom of the job is multiply-then-add, build the atom of the hardware to be exactly that — no wasted step.

PICTURE. One cell: two inputs come in, a product is formed, and it drops onto the sum sitting inside.

---

Step 2 — Stacking MACs into a matrix multiply

WHAT. A matrix is just a grid of numbers. To "multiply" two grids $A$ and $B$ into a result grid $C$, each entry of $C$ is built by sliding a row of $A$ across a column of $B$, MAC-ing pair by pair. We use $N$ for the side length of a square grid — so an $N\times N$ grid has $N$ rows and $N$ columns. (We keep matrices square only to keep the counting clean; Step 8 shows the general rectangular case behaves the same way.)

For one output entry $C_{ij}$ (row $i$, column $j$):

$$C_{ij}=\sum _{k=1}^N\underset{\text{row }i\text{ of }A}{\underbrace{A_{ik}}}\times \underset{\text{col }j\text{ of }B}{\underbrace{B_{kj}}}$$

• ${\sum }_{k=1}^N$ means "add up as $k$ counts $1,2,\dots ,N$" — that is $N$ MACs stacked.
• $A_{ik}$ walks along row $i$; $B_{kj}$ walks down column $j$. They meet at matching position $k$.

WHY count like this? Because to fairly compare "CPU vs accelerator" we must first know how much math the job truly contains and how much data it truly touches. That comparison is the whole story, so we count both next.

PICTURE. One row swept across one column, the pairs feeding a single MAC that grows $C_{ij}$.

Recall How many MACs does one output entry need?

Exactly $N$ ::: one for each value of $k$ from $1$ to $N$.

---

Step 3 — Counting the math: $N^3$ operations

WHAT. There are $N\times N=N^2$ entries in $C$, and each needs $N$ MACs (Step 2). Multiply:

$$\text{total MACs}=\underset{\text{entries in }C}{\underbrace{N^2}}\times \underset{\text{MACs per entry}}{\underbrace{N}}=N^3$$

WHY this number matters. $N^3$ is the unavoidable work — no clever memory trick removes a single multiply. It is the numerator of the ratio we care about. Hold it.

PICTURE. The output grid, one highlighted cell exploded to show its $N$ MACs; multiply by the number of cells.

---

Step 4 — Counting the traffic: the naive machine moves $\approx 2N^3$ words

WHAT. Now the sneaky part: where do the numbers come from? Fix the memory model from the top: a running sum $s$ for one output entry lives in a register while its $N$ MACs run, so it is read and written for free — it never touches main memory until it is finished. Only the inputs $A_{ik}$ and $B_{kj}$ are re-fetched from memory on every MAC, because a naive machine keeps no scratchpad to hold them.

Count the two input reads per MAC, then add the writing-out of the finished results:

$$Q_{\text{naive}}=\underset{\begin{array}{c}\text{read }{A}_{ik}\\ \text{read }{B}_{kj}\end{array}}{\underbrace{2}}\times \underset{\text{MACs}}{\underbrace{N^3}}+\underset{\begin{array}{c}\text{write each finished}\\ C_{ij}\text{ once}\end{array}}{\underbrace{N^2}}=2N^3+N^2\text{ words}$$

• The $2N^3$ term: each of the $N^3$ MACs pulls its two inputs fresh from memory (no reuse).
• The $N^2$ term: each of the $N^2$ output entries is written to memory once, after its register-resident sum is complete — not once per MAC.

For large $N$ the input re-fetches dominate, so $Q_{\text{naive}}=2N^3+N^2\approx 2N^3$ words. To turn this into bytes, multiply by the word width $w$: $Q_{\text{naive}}^{\text{bytes}}\approx 2N^{3}w$. $Q$ (for quantity of data) is the traffic in and out of main memory.

WHY care about $Q$ separately from $W$? Because chips have two speed limits: how fast they can compute ($W$) and how fast they can move data ($Q$). Whichever runs out first stops you. Counting $Q$ tells us which wall we hit.

PICTURE. A narrow pipe (memory) feeding a hungry MAC that re-fetches both inputs every cycle, while the sum $s$ waits safely in a register on the chip.

---

Step 5 — Arithmetic intensity: dividing math by traffic

WHAT. Define arithmetic intensity $I$ as how much math you do per unit of data you move:

$$I=\frac{W}{Q}=\frac{\text{operations}}{\text{bytes moved}}$$

For the naive machine, plug in Steps 3 and 4. Counting in bytes, $Q_{\text{naive}}^{\text{bytes}}=(2N^3+N^2)w$:

$$I_{\text{naive}}=\frac{N^3}{(2N^3+N^2)w}=\frac{1}{(2+\frac{1}{N})w}\underset{N\to \infty }{\to }\frac{1}{2w}$$

As $N$ grows the $\frac{1}{N}$ vanishes, so intensity flattens to the constant $\frac{1}{2w}$ — it does not grow with problem size. A billion-element matrix has the same wretched intensity as a large one.

WHY this ratio and not raw $W$ or raw $Q$? Because a chip's real speed is capped by the balance between compute and bandwidth, and $I$ is exactly that balance in one number. Low $I$ = "starving": lots of trips to memory for very little math. High $I$ = "well fed": each expensive word earns many cheap operations.

PICTURE. A balance scale — big pile of words on the left, tiny pile of ops on the right — tipping toward "memory-bound."

---

Step 6 — The systolic fix: load once, reuse $N$ times

WHAT. Instead of re-fetching, an $N\times N$ systolic array loads a value once and passes it hand-to-hand across a whole row (or down a whole column) of MAC cells. A number that entered the edge participates in $N$ different MACs before it leaves. So the math is unchanged ($W=N^3$) but the traffic collapses.

Derive $Q_{\text{systolic}}$ — and define the constant first. Let $c$ be the number of full matrices that must cross the memory boundary. There are exactly three: read $A$, read $B$, write $C$. So $c=3$. Each matrix is $N\times N=N^2$ words. Therefore the traffic is $c$ copies of $N^2$:

Q_{\text{systolic}} \;=\; c\,N^2 \;=\; \underbrace{N^2}_{\text{read all of }A}\; +\; \underbrace{N^2}_{\text{read all of }B}\; +\; \underbrace{N^2}_{\text{write all of }C}\; =\; 3N^2 \;\text{ words}$$ Compare this to Step 4, where the two input reads happened *per MAC* ($2N^3$). The systolic array pays each input read *per matrix* instead ($N^2$ apiece), because each input word, once loaded to the array edge, is reused across a whole row/column before it is dropped. **What about the running sums $s$?** Exactly as in the naive model, the partial sums **never go to main memory** — but now they live *inside the MAC cells* rather than a CPU register. A sum is born in a cell, accumulates its $N$ products *on-chip* as data streams past, and only the finished value $C_{ij}$ is written out — that write is already the $N^2$ for $C$. So no extra $N^3$ term for the sums ever appears in either model.

I_{\text{systolic}} ;=; \frac{W}{Q} ;=; \frac{N^3}{3N^2} ;=; \frac{N}{3} ;=; O(N)

- The lone $N$ that survives is the punchline: **intensity now grows with the array size.** Bigger array → each loaded number is reused more → higher $I$. - (In bytes the word width $w$ multiplies $Q$ again, giving $I=N/(3w)$ — still $O(N)$, since $w$ is a fixed constant.) **WHY does this beat Step 5?** Because the naive $\tfrac12$ never improves, but $N/3$ improves the moment you build a bigger grid. You converted a fixed, low intensity into one you can *scale up*. **PICTURE.** One value entering the left edge and being handed rightward through a whole row of MAC cells — reused at every stop, its partial sums staying on-chip, instead of re-fetched. ![[deepdives/dd-hardware-6.5.06-d2-s06.png]] > [!intuition] The "systole" mental model > Like a heartbeat pumping blood cell-to-cell, data pulses through the grid on each clock. No cell talks to main memory — only to its neighbours. The sums stay put; only inputs flow in and finished outputs flow out. That neighbour-passing *is* the reuse. > [!recall]- Why does naive give $I\to\tfrac12$ but systolic give $O(N)$? > Naive moves $\approx 2N^3$ words (re-fetch inputs $A$ and $B$ every MAC; the sum stays in a register), so the $N^3$ cancels and $I$ flattens to a constant ::: systolic moves only $3N^2$ words (read $A$, read $B$, write $C$ — each once), reusing every loaded input across a whole row, so one factor of $N$ survives. --- ## Step 7 — Reading the verdict: the Roofline model **WHAT.** A chip has two ceilings. $P_{\text{peak}}$ = its top compute rate (operations per second). $B$ = its memory bandwidth (bytes per second). The **attainable** performance is whichever ceiling you hit first:

P_{\text{attain}} ;=; \min!\Big(;\underbrace{P_{\text{peak}}}{\text{compute wall}},;; \underbrace{B\times I}{\text{memory wall}};\Big)

Why is the memory wall the product $B\times I$? Because in one second you move $B$ bytes, and each byte earns $I$ operations, so you get $B\times I$ operations — that is your speed *if memory is the limit*. - If $B\times I < P_{\text{peak}}$: **memory-bound.** You are on the sloped part of the roof. More MACs do nothing. - If $B\times I > P_{\text{peak}}$: **compute-bound.** You are on the flat part. Now more MACs help. **WHY does the systolic array change the answer?** Naive $I\to\tfrac12$ pins you far down the slope (memory-bound). Raising $I$ to $O(N)$ slides you rightward until you hit the flat compute ceiling — exactly where the MACs are worth having. **PICTURE.** The roofline: sloped memory line, flat compute line, a dot at low-$I$ (naive, memory-bound) sliding right to the corner (systolic, compute-bound). ![[deepdives/dd-hardware-6.5.06-d2-s07.png]] > [!example] Putting numbers on the roof > Chip: $P_{\text{peak}} = 90$ TOPS, $B = 300$ GB/s. (Here $I$ is quoted in ops **per byte**.) > - Naive kernel, $I = \tfrac13$: memory ceiling $= 300\times10^{9}\times\tfrac13 = 100\times10^{9} = 0.1$ TOPS. Verdict $\min(90,\,0.1) = \mathbf{0.1}$ **TOPS** — you use about $0.11\%$ of the chip. > - Systolic, $I = 50$: memory ceiling $= 300\times10^{9}\times 50 = 15\times10^{12} = 15$ TOPS. Verdict $\min(90,\,15) = \mathbf{15}$ **TOPS** — 150× more real work from the *same* silicon, purely by raising reuse. --- ## Step 8 — Edge, degenerate & non-square cases (never leave a gap) **WHAT & WHY — the cases a smart reader will ask about:** 1. **$N=1$ (a single number "matrix").** Then $W=1$, and $I_{\text{systolic}}=N/3=1/3=O(1)$. No reuse is possible — there is nothing to hand to a neighbour. **A systolic array gives zero advantage for scalar work.** This is *why* a DSA is narrow and pairs with a [[Heterogeneous computing|CPU]] for the odd bits. 2. **$N$ smaller than the array width.** If your matrix is $8\times8$ but the grid is $128\times128$, most cells are idle — reuse is capped at $8$, not $128$. **Under-filling wastes the array;** real compilers tile and pad to keep it full. 3. **Non-square matrices ($M\times K$ times $K\times N$).** The exact same accounting holds: work is $W = M\,K\,N$ MACs, and traffic is the three matrices read/written once, $Q = MK + KN + MN$ words. The intensity is then $I = \dfrac{MKN}{MK+KN+MN}$. When all three dimensions are comparable and large enough to *fill the grid*, this is again $O(\text{dimension})$ — the same win. If one dimension is tiny (e.g. $K=1$, an outer product), the denominator no longer shrinks relative to the numerator and reuse collapses. **The $O(N)$ scaling is a promise only when you can fill the array in every direction.** 4. **Bandwidth $B\to\infty$ (imagined infinite memory).** Then $B\times I$ is always huge, so $P_{\text{attain}}=P_{\text{peak}}$ for *any* $I$. Reuse would not matter — proving reuse only matters *because* real memory is slow. It is a cure for a real disease. 5. **$P_{\text{peak}}\to\infty$ (imagined infinite MACs).** Then $P_{\text{attain}}=B\times I$, fixed entirely by intensity. Buying MACs is pure waste unless $I$ rises — the exact trap the [[Roofline model]] warns against. **PICTURE.** The roofline redrawn for the degenerate corners: the $N=1$ dot stuck on the slope, and the "infinite bandwidth" flat-everywhere roof. ![[deepdives/dd-hardware-6.5.06-d2-s08.png]] > [!mistake] "Build a bigger array and any workload flies." > **Why it feels right:** bigger grid = higher peak $I$ ceiling. **The fix:** cases 2–3 — if the *matrix* is small or thin in some dimension, the reuse is set by the matrix, not the grid. The array only helps when the problem is big enough to fill it in every direction. --- ## The one-picture summary Everything above, compressed: the two counts ($W=N^3$, and $Q\approx 2N^3$ naive vs $3N^2$ systolic) become an intensity $I$, and $I$ decides where you land on the roofline — naive stuck memory-bound at a constant, systolic pushed to compute-bound as $O(N)$. ![[deepdives/dd-hardware-6.5.06-d2-s09.png]] > [!recall]- Feynman retelling — say it like you'd explain to a friend > Matrix multiply is a mountain of "multiply two numbers, add to a total" — that mountain of math, $N^3$ tall, never shrinks. The only question is: for each multiply, do you make a fresh trip to slow memory for the two *inputs*? (The running total isn't the problem — it sits in a register or inside a cell and only gets written out once.) The dumb machine re-fetches both inputs every multiply — about $2N^3$ trips — so it spends all day fetching and barely computes; its "math-per-word" score flattens to about one-half no matter how big the job. The clever trick is a grid of tiny adders where an input, once loaded, gets *handed along the row* and reused by every cell it passes. So you touch memory only three times *per matrix* — read $A$, read $B$, write $C$, that's $3N^2$ words — not per multiply. Now math-per-word grows with the grid size, $N/3$. Plot that on the roofline — a chart whose slanted line is your memory speed and whose flat line is your raw compute speed — and the dumb machine sits way down the slope (starved), while the systolic machine slides right until it touches the flat top, finally using the MACs it paid for. The catch: if the matrix is tiny ($N=1$) or thin in some direction, there is nothing to hand to a neighbour and the whole trick evaporates — which is exactly why these chips are specialists, not replacements for a CPU. --- **Prerequisites & neighbours:** [[Domain-specific accelerators (index 6.5.6)]] · [[Systolic arrays]] · [[Roofline model]] · [[TPU (Tensor Processing Unit)]] · [[Dennard scaling]] · [[Dark silicon]] · [[Amdahl's Law]] · [[Pollack's Rule]] · [[Heterogeneous computing]] · [[Quantization]] · [[GPU vs TPU]] · [[Mixed precision training]]