Visual walkthrough — Memory hierarchy (global, shared, registers)

The parent note told you the punchline: keep hot data close, and matrix multiply gets ~15× less global traffic. This page derives that number from zero. We will not assume you know what a "thread", a "warp", or a "cycle" is. We build every symbol on a picture, step by step, and count the memory trips ourselves.

Step 0 — The words we are allowed to use

Before any formula, three plain-word ideas, each pinned to the picture below.

And three storage places, ordered by how far the worker must reach:

A cycle is just one tick of the GPU's clock — our unit of "how long". Saying global is "400 cycles" means one walk to the pantry costs as much as ~400 ticks of arithmetic.

What / Why / Picture. What: we named workers and shelves. Why: every later symbol ($N$, $r$, tiles, transactions) is built only from these. Picture: the three shelves stacked by distance — the higher you climb, the longer the arrow (the walk). This distance-ladder is the whole reason a hierarchy exists.

Step 1 — The problem, drawn as arrows to the pantry

Our worked example: multiply two $N\times N$ matrices, $C=A\times B$, with $N=1024$.

So one thread reads $2N=2048$ numbers from the pantry — one $A$ and one $B$ per loop trip. See Matrix Multiplication Optimization for the algorithm itself; here we only count the walks.

What / Why / Picture. What: we counted 2048 global reads per thread. Why: this is our baseline "walk count" — everything after is measured against it. Picture: one thread firing 2048 long arrows into the far pantry. The wall of arrows is the problem.

Step 2 — The naïve total, counted honestly

There is one thread per output cell, so $N^2=1024^2\approx 1,048,576$ threads (call it "1M").

What / Why / Picture. What: multiplied per-thread walks by number of threads. Why: to see the true traffic, and to expose the waste. Picture: the same row of $A$ (highlighted coral) is fetched by every thread in that row — the exact same 1024 numbers, walked to the pantry over and over. That repetition is the leak we plug next.

Step 3 — The idea: fetch once, reuse many (tiling)

Split each matrix into small square tiles of size $T\times T$. We use $T=16$.

What / Why / Picture. What: introduced a $16\times 16$ tile parked in shared memory. Why: shared memory is ~10× closer than global, and cooperative loading removes the duplicate walks of Step 2. Picture: 256 threads (lavender box) each grab one element from the pantry (long arrows), drop it on the shared counter, then draw short arrows from the counter during the compute — many short arrows per one long arrow.

Step 4 — Count the tiled walks, term by term

Slide the tile across the $k$-dimension. Number of tiles along a row/column: $\frac{N}{T}=\frac{1024}{16}=64\text{ tiles.}$

With $N=1024,T=16$: $\frac{2\cdot 1024^3}{16}=134,217,728\approx 134\text{ million reads.}$

What / Why / Picture. What: recounted total walks with sharing. Why: to get the honest new number. Picture: one loaded $A$-tile row (mint) feeds $T=16$ separate output cells — one walk, sixteen uses.

Step 5 — The speedup, and where the $T$ comes from

The parent's "~15×" is this same number, softened by loading edge/boundary tiles in practice. The clean law is: reuse each fetched value $T$ times → traffic drops by $T$. This is the arithmetic-intensity lever behind the Roofline Model and Memory Bandwidth Optimization.

What / Why / Picture. What: divided the two counts. Why: to isolate what causes the speedup — it is $T$, nothing else. Picture: a bar chart, 2.15B shrinking to 134M, with the factor $T=16$ labelling the gap.

Step 6 — Edge case: the shared counter has 32 lanes (bank conflicts)

We assumed shared memory is uniformly fast. It has a catch. Shared memory is split into banks: 32 lanes, each serving one request per cycle.

The transpose case shows the trap and the fix: a $32\times 32$ shared tile makes column access tile[i][i] hit lane $i\cdot 32\mathrm{mod}32=0$ for every thread → $S=32$, a 32× slowdown. Padding to $32\times 33$ shifts each row by one lane, so a column spreads across all 32 lanes → $S=1$.

What / Why / Picture. What: modelled shared memory as 32 lanes. Why: the counter is only fast if the team doesn't crowd one lane. Picture: left, a column jammed into lane 0 (coral, serialized); right, the same column fanned across all lanes after [32][33] padding (mint, parallel).

Step 7 — Degenerate cases: when tiling doesn't help

What / Why / Picture. What: swept the boundary values of $T$ and the no-reuse case. Why: the contract says every case must be shown — including when the trick fails. Picture: the $T$-vs-speedup curve, flat at 1 for $T=1$, rising, then a red "won't fit" wall past the shared-memory limit.

The one-picture summary

One thread's 2048 far-pantry walks (Step 1) × 1M threads = 2.15 B walks (Step 2, full of duplicates). Park a $T\times T$ tile on the shared counter (Step 3), reuse each fetched value $T$ times (Step 4), and total walks fall to $2N^3/T$ — a clean $T$× win (Step 5) — provided the counter's 32 lanes aren't jammed (Step 6) and the tile fits with real reuse to exploit (Step 7).

Reveal-check:

Related: Memory Latency Hiding · Cache Architecture · GPU Thread Hierarchy · CUDA Memory Types