Memory hierarchy (global, shared, registers): Worked examples

This page is a drill. We take the three storage levels from the parent note — registers, shared memory, global memory — and hit every kind of arithmetic question they can throw at you. Before we start, one promise: no symbol appears here without a plain-word meaning. Let us fix the vocabulary once.

The scenario matrix

Every memory question is one of these cells. The examples below are labelled with the cell they cover.

Cell	What makes it different	Example
A. Register limit	register budget is the bottleneck	Ex 1
B. Register tie / zero slack	division comes out exact, no waste	Ex 2
C. Register vs thread-cap	a different limit wins	Ex 3
D. Shared-memory limit	scratchpad is the bottleneck, not registers	Ex 4
E. Bank conflict — worst case	all threads hit one bank (serialize ×32)	Ex 5
F. Bank conflict — the padding fix	change a number, conflict vanishes	Ex 6
G. Coalescing — best case	one memory transaction	Ex 7
H. Coalescing — strided / worst case	32 transactions, degenerate access	Ex 7
I. Word problem	real speedup from tiling	Ex 8
J. Exam twist / limiting value	which resource caps occupancy? push a knob to its extreme	Ex 9

We will always compute occupancy: the fraction of the SM's maximum threads that are actually busy.

$Occupancy = \frac{N _{active}}{N _{max}}$

Why care? An idle SM cannot hide the long wait for global memory. Higher occupancy means more threads ready to run while others wait. (See Memory Latency Hiding.)

Figure — Memory hierarchy (global, shared, registers)

The bar chart above is the mental picture for every register/shared example: one SM has one register pile and one scratchpad. Every block you launch takes a bite out of both. When either bite would overflow, no more blocks fit.

Cell A — Register limit is the bottleneck

Worked example Ex 1 — registers cap the block count

An SM has $R_{total} = 65536$ registers and a thread cap of $N_{m a x} = 2048$ . A kernel launches 512 threads/block and uses 40 registers/thread. How many blocks fit, and what is occupancy?

Forecast: guess before reading — will occupancy be 100%, or less?

Step 1. Registers one block needs. $R_{block} = 512 \times 40 = 20480$ Why this step? A block's threads all live on the same SM at the same time, so their register demands add up. This is the bite the block takes.

Step 2. How many complete blocks fit in the pile. $N_{blocks} = ⌊ \frac{65536}{20480} ⌋ = ⌊ 3.2 ⌋ = 3$ Why this step? Only whole blocks run, so we floor. The leftover $65536 - 3 \times 20480 = 4096$ registers are stranded — not enough for a 4th block.

Step 3. Active threads and occupancy. $N_{active} = 3 \times 512 = 1536, Occupancy = \frac{1536}{2048} = 0.75 = 75%$

Verify: $3 \times 20480 = 61440 \leq 65536$ ✓ (fits) and $4 \times 20480 = 81920 > 65536$ ✓ (4 would overflow). The register limit, not the thread cap, decided this: $1536 < 2048$ .

Cell B — Exact division, zero slack

Worked example Ex 2 — the division comes out whole

Same SM ( $R_{total} = 65536$ , $N_{m a x} = 2048$ ). Kernel uses 256 threads/block and 32 registers/thread.

Forecast: any registers wasted this time?

Step 1. Registers per block. $R_{block} = 256 \times 32 = 8192$ Why this step? Same reasoning as always: the 256 threads of one block sit on the SM together, so we add up their register demands to find how big a bite this block takes from the pile.

Step 2. Blocks that fit. $N_{blocks} = ⌊ \frac{65536}{8192} ⌋ = ⌊ 8.0 ⌋ = 8$ Why this step? Here $65536 = 8 \times 8192$ exactly — the floor changes nothing. This is the degenerate "no-waste" case: zero stranded registers.

Step 3. Threads and occupancy. $N_{active} = 8 \times 256 = 2048, Occupancy = \frac{2048}{2048} = 100%$

Verify: $8 \times 8192 = 65536$ , exactly the budget, remainder $0$ ✓. And $2048$ hits the thread cap dead on — both limits saturate together. This is the sweet spot every tuning guide chases.

Cell C — A different limit wins (thread cap)

Worked example Ex 3 — registers say "more," but the thread cap says "no"

Same SM. Kernel uses 256 threads/block but only 16 registers/thread (a very light kernel).

Forecast: registers are cheap now — does occupancy break 100%? (Trick: it cannot.)

Step 1. Register-limited block count. $R_{block} = 256 \times 16 = 4096, ⌊ \frac{65536}{4096} ⌋ = 16 blocks$ Why this step? By registers alone, 16 blocks fit.

Step 2. Thread-cap block count. $⌊ \frac{N _{m a x}}{threads/block} ⌋ = ⌊ \frac{2048}{256} ⌋ = 8 blocks$ Why this step? The SM can never hold more than $2048$ live threads, no matter how many registers are free. This is a separate ceiling.

Step 3. The real answer is the smaller limit. $N_{blocks} = min (16, 8) = 8, N_{active} = 2048, Occupancy = 100%$ Why this step? Both ceilings must hold at the same time — the hardware obeys every rule at once, so it can only fit as many blocks as the strictest rule permits. That is exactly what "minimum" means: the tightest limit wins, and any looser limit is left with room to spare.

Verify: $8 \times 4096 = 32768 \leq 65536$ (registers to spare) but $8 \times 256 = 2048 = N_{m a x}$ (thread cap full). Lesson: always take the min across all resource limits. Spare registers do not buy you extra threads.

Cell D — Shared memory is the bottleneck

Worked example Ex 4 — the scratchpad runs out first

An SM has 48 KB of shared memory, $R_{total} = 65536$ registers, $N_{m a x} = 2048$ . Each block launches 256 threads, uses 32 registers/thread, and allocates 20 KB of shared memory.

Forecast: three limits now — registers, threads, shared memory. Which one bites first?

Step 1. Register limit (blocks). $256 \times 32 = 8192$ , so $⌊ 65536/8192 ⌋ = 8$ blocks. Why this step? First of three separate ceilings — we ask how many blocks the register pile alone allows, exactly as in Ex 1.

Step 2. Thread-cap limit. $⌊ 2048/256 ⌋ = 8$ blocks. Why this step? Second ceiling — the SM's hard cap on live threads, independent of memory, exactly as in Ex 3.

Step 3. Shared-memory limit. $⌊ \frac{48 KB}{20 KB} ⌋ = ⌊ 2.4 ⌋ = 2 blocks$ Why this step? Each block reserves its own private 20 KB slice of the scratchpad — blocks do not share each other's shared memory. Two blocks use 40 KB; a third would need 60 KB > 48 KB.

Step 4. Take the min. $N_{blocks} = min (8, 8, 2) = 2, N_{active} = 512, Occupancy = \frac{512}{2048} = 25%$ Why this step? As in Ex 3, all three ceilings must hold simultaneously, so the true block count is the smallest of them. Here shared memory is by far the tightest, so it alone decides the answer.

Verify: $2 \times 20 = 40 KB \leq 48$ ✓, $3 \times 20 = 60 > 48$ ✓. Registers and threads had lots of room, yet shared memory dragged occupancy to $25%$ . This is why you budget all three resources.

Cell E — Bank conflict, the worst case

The figure below draws exactly this idea: the row of 32 boxes across the top are the 32 bank-doors, the orange arrows show the worst case of Ex 5 (all arrows crashing into one door), and the teal arrows show the fixed case of Ex 6 (one arrow per door). Keep it in view while reading both examples.

Worked example Ex 5 — a column read of a 32×32 tile

A warp reads column 0 of float tile[32][32]: thread $t$ reads tile[t][0], whose byte address is $a_{t} = t \times 32 \times 4 = 128 t$ . In the figure, this is the fan of orange arrows all pointing at door 0.

Forecast: how many banks get hit — 32 or 1?

Step 1. Which bank does thread $t$ hit? $bank (128 t) = (\frac{128 t}{4}) mod 32 = (32 t) mod 32 = 0.$ Why this step? Because a full row is 32 words wide, stepping down one row moves you a whole multiple of 32 words — right back to bank 0. Every thread lands on bank 0.

Step 2. Serialization factor. $S = 32 (all 32 threads on bank 0)$ Why this step? One door, 32 knocks → they queue one at a time.

Verify: effective latency $= 32 \times$ base. A column read of a square tile is the textbook worst case — a 32-way conflict. See CUDA Memory Types for why this bites in transpose kernels.

Cell F — The one-number padding fix

Worked example Ex 6 — pad to 33 columns

Same column read, but now declare float tile[32][33]. Thread $t$ reads tile[t][0], address $a_{t} = t \times 33 \times 4 = 132 t$ . In the figure, this is the teal set of arrows, each rising into its own separate door.

Forecast: does adding one unused column really untangle all 32 threads?

Step 1. New bank for thread $t$ . $bank (132 t) = (\frac{132 t}{4}) mod 32 = (33 t) mod 32 = (t) mod 32 = t .$ Why this step? $33 \equiv 1 (mod 32)$ , so stepping one row now advances the bank by exactly 1 instead of $0$ . Threads $0..31$ spread across banks $0..31$ .

Step 2. Serialization factor. $S = 1 (each thread on its own bank)$ Why this step? We compute $S$ — the largest crowd on any one door — to turn the bank map from Step 1 into an actual slowdown number. Here every door has exactly one visitor, so the worst crowd is $1$ : no queue at all, full parallel service in a single cycle.

Verify: the padding column is never read (index 32 unused), so correctness is untouched, yet $S$ dropped from $32$ to $1$ — a $32 \times$ speedup on that access. This is exactly the tile[32][33] trick from the parent's transpose example.

Cells G & H — Coalescing, best and worst

The figure below is the picture for the two cases below it: the teal band on top is the coalesced case (one crate covers the whole warp), and the orange scattered boxes below are the strided case (each thread strands in its own crate). Refer to it as you read Ex 7.

Worked example Ex 7 — same warp, best vs worst access pattern

A warp of 32 threads reads float values (4 bytes each). Compare two patterns — the teal band and the orange scatter in the figure.

Forecast: how big is the gap between the good and bad pattern?

Case G (coalesced). Thread $t$ reads address $a + 4 t$ , so addresses run $a, a + 4, \dots, a + 124$ .

Step 1. Total span of bytes touched. $32 \times 4 = 128 bytes.$ Why this step? If a warp's whole footprint is one 128-byte crate (and aligned), it fits in a single fetch. $N_{transactions} = ⌈ \frac{128}{128} ⌉ = 1.$

Case H (strided, degenerate). Thread $t$ reads $a + 256 t$ — one float grabbed out of every 64.

Step 2. Each thread lands in a different crate. $stride 256 bytes > 128 byte segment \Rightarrow N_{transactions} = 32.$ Why this step? Consecutive threads are 256 bytes apart, wider than a crate, so each needs its own crate. We fetch 32 crates but use only 4 useful bytes from each.

Step 3. Bandwidth ratio. $\frac{N _{worst}}{N _{best}} = \frac{32}{1} = 32.$

Verify: useful bytes are $128$ in both cases, but bytes moved are $128$ (coalesced) vs $32 \times 128 = 4096$ (strided). Efficiency $128/4096 = 1/32 \approx 3.1%$ . A $32 \times$ penalty — the same factor as the worst bank conflict, by the same "one lane, many requests" logic.

Cell I — The real-world word problem

Worked example Ex 8 — how much does tiling actually save?

Multiply two $1024 \times 1024$ matrices with $16 \times 16$ tiles (256 threads/block). Compare global reads for the naive version vs the tiled version. (Background: Matrix Multiplication Optimization.)

Forecast: guess the speedup — 2×? 15×? 100×?

Step 1. Naive traffic. Each output element $C_{ij}$ needs a full row of $A$ and column of $B$ : $2 \times 1024$ reads. One thread per output element, $102 4^{2}$ elements. $T_{naive} = 2 \times 1024 \times 102 4^{2} = 2, 147, 483, 648 \approx 2.15 billion reads.$ Why this step? Nothing is reused; every multiply-add re-fetches from slow global memory.

Step 2. Tiled traffic. The matrix is $1024/16 = 64$ tiles wide. Each block sweeps 64 tile-steps, loading one $16 \times 16$ tile of $A$ and one of $B$ per step: $2 \times 256 = 512$ reads per step. Blocks: $(1024/16)^{2} = 6 4^{2} = 4096$ . $T_{tiled} = steps 64 \times reads/step 512 \times blocks 4096 = 134, 217, 728 \approx 134 million reads.$ Why this step? Each loaded value is reused 16 times from fast shared memory before being discarded, so global traffic drops by roughly the tile width.

Step 3. Speedup. $\frac{T _{naive}}{T _{tiled}} = \frac{2 , 147 , 483 , 648}{134 , 217 , 728} = 16.$ Why this step? We divide the two traffic totals to see the payoff. The ratio landing on exactly $16$ is no accident: every value pulled into a tile is used $16$ times (once per row/column of a $16$ -wide tile) before it leaves shared memory, so each global read now does the work of $16$ naive reads. The tile width and the speedup are the same number — that equality is our built-in sanity check.

Verify: the ratio equals the tile width $16$ — exactly the reuse factor. (The parent quoted "~15×"; that used a coarser per-block count. The clean per-value accounting gives exactly $16 \times$ .) Roofline intuition: we moved a memory-bound kernel toward compute-bound. See Roofline Model.

Cell J — The exam twist / limiting value

Worked example Ex 9 — push register usage to its extreme

An SM has $R_{total} = 65536$ registers, $N_{m a x} = 2048$ threads, blocks of 128 threads. The compiler reports 255 registers/thread (near the hardware ceiling of 256). What is occupancy? Then: what register count is needed to reach 100%?

Forecast: with registers pushed to the max, will even a single block fit?

Step 1. Registers per block at the extreme. $R_{block} = 128 \times 255 = 32640.$ Why this step? Same bite-adding rule as every register example: 128 threads each demanding 255 registers must be resident together.

Step 2. Blocks by registers. $⌊ \frac{65536}{32640} ⌋ = ⌊ 2.007 ⌋ = 2 blocks.$ Why this step? Even at near-max register greed, 2 blocks squeeze in — barely. A third needs $97920 > 65536$ , so the floor chops $2.007$ down to $2$ .

Step 3. Occupancy at the extreme. $N_{active} = 2 \times 128 = 256, Occupancy = \frac{256}{2048} = 12.5%.$ Why this step? This is the limiting behaviour: push the register knob toward its ceiling and occupancy collapses toward its floor — here down to one-eighth of the SM.

Step 4. Reverse the question — how many registers for 100%? To fill $2048$ threads we need $2048/128 = 16$ blocks. Registers per block allowed: $65536/16 = 4096$ . Per thread: $r_{m a x} = \frac{4096}{128} = 32 registers/thread.$ Why this step? We divide the whole budget evenly across the whole thread cap — this back-solves for the largest register count that still lets every one of the $2048$ thread slots fill.

Verify: at $r = 32$ : $128 \times 32 = 4096$ , $⌊ 65536/4096 ⌋ = 16$ blocks $\times 128 = 2048$ threads $= 100%$ ✓. Going from $32$ to $255$ registers/thread crushed occupancy from $100%$ to $12.5%$ — an $8 \times$ fall. That is the whole register-pressure story on one slide.

Recall Self-test — cover the answers

Ex 1 occupancy ::: 75% (register-limited to 3 blocks) Ex 2 occupancy ::: 100% (exact division, 8 blocks, 2048 threads) Ex 3 winning limit ::: the thread cap (min of 16 and 8 blocks = 8) Ex 4 occupancy ::: 25% (shared memory limits to 2 blocks) Ex 5 serialization factor ::: 32 (all threads hit bank 0) Ex 6 serialization factor after 33-padding ::: 1 (each thread own bank) Ex 7 coalesced vs strided transaction ratio ::: 32× Ex 8 tiling speedup ::: 16× fewer global reads Ex 9 registers/thread for 100% occupancy ::: 32