Exercises — Occupancy and latency hiding

WHAT: Occupancy is a ratio of active to maximum warps. WHY: That is literally its definition — no resource limits to hunt for here, we are handed the active-warp count directly. $\text{Occupancy}=\frac{48}{64}=0.75=75\%$ Answer: $75\%$.

Step 1 — warps per block. A warp is $32$ threads, so $256/32=8$ warps per block. WHY divide by 32: the hardware always groups threads into fixed lanes of $32$; that is the atom of scheduling. Step 2 — total active warps. $6\text{ blocks}\times 8\text{ warps}=48$ warps. Step 3 — occupancy. $48/64=75\%$. Answer: $8$ warps/block, $75\%$ occupancy.

Step 1 — registers per warp. Each warp has $32$ threads, so it consumes $64\times 32=2048$ registers. WHY multiply by 32: every one of the $32$ lanes needs its own private copy of each register; a warp's cost is the per-thread cost times $32$. Step 2 — how many such warps fit. $W_{\text{regs}}=\lfloor \frac{65,536}{2048}\rfloor =32\text{ warps}$ WHY the floor $\lfloor \rfloor$: you cannot host a fractional warp — leftover registers that can't cover a full warp are simply wasted. Step 3 — occupancy. With no other limit, $\min (32,64)=32$. $\text{Occupancy}=\frac{32}{64}=50\%$ Answer: $32$ warps, $50\%$.

We must check each resource and take the minimum. Register limit: $W_{\text{regs}}=\lfloor \frac{65,536}{32\times 32}\rfloor =\lfloor \frac{65,536}{1024}\rfloor =64\text{ warps}$ Shared-memory limit: how many $48$ KB blocks fit in $164$ KB? $\lfloor 164/48\rfloor =3\text{ blocks}\Rightarrow 3\times 8=24\text{ warps}$ Block-count limit: $3$ blocks is well under the $32$-block max, so not binding. Step — take the minimum: $\min (64,24,64)=24$. $\text{Occupancy}=\frac{24}{64}=37.5\%$ Answer: shared memory is the bottleneck; $37.5\%$.

WHY this tool: Little's Law answers exactly "how much must be in flight to keep a pipe full given a latency and a rate". That is precisely our question — we are not shrinking latency, we are overlapping it. $\text{in flight}=L\times \text{throughput}=400\times 1=400\text{ warp-instructions}$ Answer: $400$ (single-scheduler idealisation). The parent note explains why real SMs need only $16$–$32$ warps: $4$ schedulers plus instruction-level parallelism supply the concurrency SM-wide.

(a) $W_{\text{regs}}=\lfloor 65536/(128\times 32)\rfloor =\lfloor 65536/4096\rfloor =16$ warps $\Rightarrow 16/64=25\%$. (b) $W_{\text{regs}}=\lfloor 65536/(64\times 32)\rfloor =\lfloor 65536/2048\rfloor =32$ warps $\Rightarrow 32/64=50\%$. (c) WHY 128 can still win: if the kernel is memory-bound, $16$ warps may already hide the load latency (recall $16$–$32$ warps usually suffice SM-wide). Meanwhile keeping data in registers avoids spills to local memory that cost hundreds of cycles each. So $25\%$ with no spills can beat $50\%$ with spills. Answer: (a) $25\%$; (b) $50\%$; (c) memory-bound kernels where the extra registers prevent spilling.

WHY divide by loads-per-warp: each warp now contributes $2$ outstanding requests, so it does the work of $2$ toward filling the $400$-cycle gap. $\text{warps}\gtrsim \frac{400}{2}=200\text{ (single-scheduler idealisation)}$ WHY the real number is far lower: the A100 has $4$ schedulers issuing from different warps in consecutive cycles, and the memory system services many requests in parallel (memory-level parallelism). Divide the idealised figure by the effective SM-wide issue width and you land in the empirical $16$–$32$ warp range. Answer: $\approx 200$ idealised; in practice $16$–$32$ warps due to $4$ schedulers + MLP.

WHAT limits each: A's ceiling is registers; B's ceiling is shared memory. The binding constraint is the only one worth relaxing (barrel plank logic). Kernel A: cutting register use raises $W_{\text{regs}}$, directly lifting the minimum → occupancy rises. Kernel B: more registers do nothing — shared memory is still the shortest plank; you'd raise a non-binding limit. Answer: Kernel A benefits. For B you must cut shared-memory usage instead (e.g. smaller tiles).

(a) Check each limit.

• Registers: $\lfloor 65536/(80\times 32)\rfloor =\lfloor 65536/2560\rfloor =25$ warps.
• Shared mem: $\lfloor 164/32\rfloor =5$ blocks $\Rightarrow 5\times 4=20$ warps.
• Blocks: $5$ blocks $\le 32$ max, so blocks give $5\times 4=20$ warps (not extra-binding).
• $\min (25,20,20,64)=20\Rightarrow 20/64=31.25\%$. Binding constraint: shared memory (20 warps). (b) Change: halve shared memory to $16$ KB/block. Then $\lfloor 164/16\rfloor =10$ blocks $\Rightarrow 10\times 4=40$ warps for smem; registers still allow $25$; block max allows $\min (10,32)\times 4=40$. New minimum $=\min (25,40,40,64)=25$. $\text{Occupancy}=25/64=39.06\%$ WHY it stops at 25, not 40: once shared memory stops binding, registers become the new shortest plank at $25$ warps. Synthesis lesson: fixing one bottleneck exposes the next. Answer: (a) $31.25\%$, shared-memory bound. (b) $16$ KB smem → $\approx 39.06\%$, now register bound.

WHY roofline: it tells us the ceiling a kernel can reach from its intensity — compute-bound above the ridge, memory-bound below. Step — ridge-point intensity (where the two ceilings meet): $A{I}_{\text{ridge}}=\frac{19,500\text{ GFLOP/s}}{1555\text{ GB/s}}\approx 12.54\text{ FLOP/byte}$ Our $AI=0.5\ll 12.54$, so we are far below the ridge → memory-bound. (b) Implication: performance is set by feeding data, and moderate occupancy ($\sim 50\%$, i.e. $16$–$32$ warps) already hides load latency. Pushing to $100\%$ gives diminishing returns; better to improve coalescing so each transaction moves useful bytes. Answer: (a) memory-bound ($0.5\ll 12.54$); (b) ~50% occupancy suffices — chase coalescing, not occupancy.

(a) Occupancy.

• P: $\lfloor 65536/(96\times 32)\rfloor =\lfloor 65536/3072\rfloor =21$ warps $\Rightarrow 21/64=32.8\%$.
• S: $\lfloor 65536/(48\times 32)\rfloor =\lfloor 65536/1536\rfloor =42$ warps $\Rightarrow 42/64=65.6\%$. (b) Which wins. Version S doubles occupancy — tempting. But it adds $2\times 400=800$ cycles of serial spill latency on the critical path of every thread, whereas P saves $50$ cycles by keeping data resident. Because the kernel is memory-bound, P's $21$ warps ($>16$) already supply enough concurrency to hide the genuine load latency SM-wide. Extra warps in S hide nothing new but pay the spill tax. Decision: Version P is faster. Occupancy rose in S, yet per-thread critical-path latency exploded — and once latency is already hidden, more warps don't help. Answer: (a) P $\approx 32.8\%$, S $\approx 65.6\%$; (b) P wins — spills add $800$ serial cycles that no amount of occupancy recovers here.

Warp scheduling view: a scheduler picks a ready warp each cycle. A stalled warp (waiting on its load) is not ready, so if it is the only warp, the scheduler has nothing to issue → the SM idles. SM architecture view: context (registers) for many warps lives on-chip simultaneously, making a switch free — but only if other warps exist to switch to. One warp = nothing to switch to. Little's Law view: in-flight requests needed $=L\times \text{rate}$. A lone warp issues one load then must wait; it cannot keep $400$ cycles' worth of independent requests outstanding by itself, because its later instructions depend on that load's result. Rule of thumb: you need multiple independent warps — empirically $16$–$32$ on modern SMs — to keep the $4$ schedulers fed and the memory system busy while any one warp waits. Answer: latency hiding is inherently a between-warps mechanism; ILP within one warp is bounded by dependencies, so $\ge 16$–$32$ warps is the practical minimum.

Occupancy $=$ active warps divided by maximum warps per SM. The occupancy formula takes the minimum of all resource limits. Registers are billed per warp as per-thread count times 32. A single warp cannot hide its own load latency because latency hiding is a between-warps mechanism.