Worked examples — GPU memory bandwidth optimization

This is the worked-examples companion to the parent topic. The parent gave you the tools: coalescing, transactions, efficiency $\eta$, bank conflicts, and arithmetic intensity $I$. Here we hit every case those tools can produce — perfect access, worst access, degenerate one-thread cases, the AoS scattering case, and the roofline boundary — with the numbers checked at the bottom.

Before we start, one plain-words refresher so no symbol is unearned:

$\eta =\frac{w\cdot b}{\text{(transactions)}\times T_{tx}},\text{transactions}=\lceil \frac{\text{address span}}{T_{tx}}\rceil$

Here $b$ is the bytes each thread wants (a float is $b=4$). The symbol $\lceil \rceil$ means round up — you can't make half a fetch; even one leftover byte forces a whole extra transaction.

---

The scenario matrix

Every memory-access problem in this topic falls into one of these cells. The worked examples below are labelled with the cell they cover, and together they fill the whole table.

Cell	Access pattern	What's special about it	Example
A	Consecutive (stride 1)	Best case, $\eta =100\%$	Ex 1
B	Strided (stride $s>1$)	Wasted bandwidth grows with $s$	Ex 2
C	Extreme stride ($s\ge 32$)	Full serialization, $\eta$ floor	Ex 2b (inside Ex 2)
D	Degenerate: 1 active thread	Warp with 31 threads masked off	Ex 3
E	Broadcast: all same address	Zero-stride, special hardware path	Ex 4
F	AoS scatter (struct span $S$)	Partial coalescing	Ex 5
G	Shared-memory bank conflict	$k$-way conflict → $k$ cycles	Ex 6
H	Word problem (real workload)	Choose a layout, predict speedup	Ex 7
I	Roofline boundary (limiting case)	Bandwidth- vs compute-bound crossover	Ex 8
J	Exam twist (misaligned base)	Alignment offset forces extra transaction	Ex 9

Prerequisites worth a click if a step feels fast: GPU-Warp-Scheduling, Cache-Hierarchy, CUDA-Shared-Memory, Roofline-Model.

The figure above is the whole matrix in pictures — each colored strip is one warp's 32 requests, and the black boxes are the 128-byte fetches that actually get hauled. Keep glancing back at it.

---

Ex 1 — Cell A: perfectly consecutive

Forecast: guess the transaction count before reading on. (One? Thirty-two?)

1. Find the address span. Thread 0 is at offset $0$, thread 31 at offset $4\times 31=124$. Span $=124-0+4=128$ bytes (the $+4$ because thread 31 still wants its own 4 bytes). Why this step? Transactions depend only on how far apart the first and last bytes are, not on how many threads — the fetch carries a contiguous block.
2. Round up to transactions. $\lceil 128/128\rceil =1$. Why this step? One 128-byte block covers the whole span exactly.
3. Compute efficiency. Useful bytes $=32\times 4=128$. Hauled $=1\times 128=128$. $\eta =\frac{128}{128}=1=100\%.$

Verify: Look at strip A in the figure — the colored requests tile the single black box with no gaps and no overflow. Units: bytes/bytes = dimensionless, correct for an efficiency. ✓

---

Ex 2 — Cells B & C: strided access

Forecast: which one collapses all the way down to the 3.125% floor?

Part (a), $s=2$:

1. Span. Last thread at offset $4\cdot 2\cdot 31=248$; span $=248+4=252$ bytes. Why? Doubling the stride doubles the address spread.
2. Transactions. $\lceil 252/128\rceil =\lceil 1.97\rceil =2$. Why round up here matters: 252 bytes needs the block $[0,127]$ plus the block $[128,255]$ — the data ends at byte 251, still inside the second block, so two transactions cover it (not three).
3. Efficiency. $\eta =\frac{128}{2\times 128}=\frac{1}{2}=50\%$.

Part (b), $s=32$:

1. Span. Offset of last thread $=4\cdot 32\cdot 31=3968$; span $=3968+4=3972$ bytes.
2. Transactions. $\lceil 3972/128\rceil =\lceil 31.03\rceil =32$. Why exactly 32? With stride $\ge 32$ floats, each thread lands in its own 128-byte block — no two share a fetch. This is the worst case = Cell C.
3. Efficiency. $\eta =\frac{128}{32\times 128}=\frac{1}{32}=3.125\%$.

Verify: matches the parent note's worst-case $3.125\%$. In the figure, strip C's requests scatter one-per-box — 32 boxes, 31/32 of each wasted. Sanity: $\eta$ dropped monotonically as $s$ grew (100% → 50% → 3.1%), which is what "more spread = more waste" demands. ✓

---

Ex 3 — Cell D: degenerate, one active thread

Forecast: does one lonely thread still pay for a whole 128-byte fetch?

1. Span. Only one active address, so span $=4$ bytes. Why this step? Masked threads issue no request; the span is just the live one.
2. Transactions. $\lceil 4/128\rceil =1$. Why it can't be zero: the block is quantized at 128 bytes — you cannot fetch fewer.
3. Efficiency. Useful $=4$, hauled $=128$: $\eta =4/128=3.125\%$.

Verify: Same 3.125% floor as the strided worst case — for the opposite reason. Cell C wastes because addresses spread out; Cell D wastes because the warp is nearly empty. This is why keeping warps full matters: an under-populated warp burns bandwidth just like a scattered one. ✓

---

Ex 4 — Cell E: broadcast (zero stride)

Forecast: naïvely you might fear 32 threads fighting over one word — is it a conflict?

1. Global-memory span. All threads at offset 0, span $=4$ bytes → $\lceil 4/128\rceil =1$ transaction. Why? Every request is the same address, so the address span is just one word.
2. Efficiency by the general formula. The DRAM had to deliver only 4 distinct useful bytes (one word), hauled inside one 128-byte block: ${\eta }_{\text{DRAM}}=\frac{\text{distinct useful bytes}}{\text{transactions}\times T_{tx}}=\frac{4}{1\times 128}=3.125\%.$ Why "distinct" here? $\eta$ measures DRAM traffic waste, and DRAM only moved one word regardless of how many threads consumed it. So the fetch is cheap on trips (1 transaction) even though its DRAM efficiency is at the floor — those two facts are not in conflict.
3. Shared-memory case. The parent's broadcasting exception fires: identical address → hardware broadcasts in 1 cycle, no bank conflict. Why? A conflict needs different addresses in the same bank. Same address is the one exception.

Verify: 1 transaction, ${\eta }_{\text{DRAM}}=3.125\%$ (global), and 1 cycle (shared, broadcast). Contrast with Ex 6 where different addresses in one bank cost dearly. ✓

---

Ex 5 — Cell F: Array-of-Structures scatter

Forecast: it's not the full worst case — guess between 1 and 32.

1. Span. Thread $i$'s x is at offset $24i$. Last thread $=24\times 31=744$; span $=744+4=748$ bytes. Why? The wanted fields sit every 24 bytes — scattered, but not as far as stride-32.
2. Transactions. $\lceil 748/128\rceil =\lceil 5.84\rceil =6$. Why 6 and not 32? Six neighbouring blocks cover the 748-byte spread, so AoS partially coalesces.
3. Efficiency. $\eta =\frac{128}{6\times 128}=\frac{1}{6}\approx 16.7\%$.

Now the fix — Structure of Arrays — makes x[i] consecutive, back to Cell A (1 transaction, 100%).

4. Whole-struct speedup. All 6 fields: AoS $=6\times 6=36$ transactions; SoA $=6\times 1=6$. $\text{Reduction}=36/6=6\times .$

Verify: matches the parent's AoS-vs-SoA numbers ($16.7\%$, $6\times$). Strip F in the figure shows the 6 boxes with only one useful sliver each. See Parallel-Algorithm-Design for choosing SoA up front. ✓

---

Ex 6 — Cell G: shared-memory bank conflict

Forecast: is a column the best or worst thing to read?

1. Bank of each address. Bank $=\left(\frac{A}{4}\right)\mathrm{mod}32$. Element tile[i][0] sits at word index $32i$ (row-major, 32 columns per row). Why word index $32i$? Row $i$ starts $32$ words in from row $i-1$.
2. Reduce mod 32. $32i\mathrm{mod}32=0$ for every $i$. Why this is the disaster: all 32 threads map to bank 0, different addresses → a 32-way conflict.
3. Cycle cost. $k$-way conflict $=k$ cycles: here $k=32$, so 32 cycles instead of 1.

The padding fix: declare float tile[32][33] (one dummy column). Now tile[i][0] is at word index $33i$, and $33i\mathrm{mod}32=i$ — all distinct banks → 1 cycle. Why $+1$ works: $33\equiv 1(\mathrm{mod}32)$, so successive rows shift by exactly one bank, spreading the column across all 32.

Verify: Conflict-free result $33i\mathrm{mod}32=i$ hits banks $\mathrm{0..31}$ once each. Speedup $32\to 1$ cycles $=32\times$. See CUDA-Shared-Memory for the padding idiom. ✓

---

Ex 7 — Cell H: word problem, pick a layout

Forecast: which one lets the red-channel warp coalesce?

1. Interleaved red access. Red of pixel $i$ is at byte $12i$. Span for 32 threads $=12\times 31+4=376$; transactions $=\lceil 376/128\rceil =3$. Why? Reds are 12 bytes apart — same scatter idea as Ex 5, just $S=12$.
2. Planar red access. Reds are contiguous, 4 bytes apart. Span $=128$; transactions $=1$. Why? Planar puts all reds in one run → Cell A.
3. Ratio. $3/1=3\times$ fewer transactions for the red pass; same for green and blue passes.

Answer: choose planar (SoA) for channel-parallel work. Verify: interleaved gives $\eta =128/(3\cdot 128)=33.3\%$, planar $100\%$; ratio $3\times$ matches step 3. Units: transactions are dimensionless counts. ✓

---

Ex 8 — Cell I: the roofline boundary

Forecast: will $T_{\text{tile}}=32$ tiling be enough to escape the memory wall?

1. Count the work. A full multiply does $N^3$ multiply-adds, each counting as 2 FLOPs, so total FLOPs $=2N^3$. Why this step? Arithmetic intensity $I$ = FLOPs ÷ bytes, so we need the FLOP numerator first. Each of the $N^2$ output entries is a dot product of length $N$ → $N^3$ products.
2. Count the DRAM bytes with tiling — build it up.
   • Sub-step 2a — reads per output element, un-tiled: each output entry needs a full row of $A$ and a full column of $B$, i.e. $2N$ element reads from DRAM.
   • Sub-step 2b — how tiling divides that: we sweep the shared dimension in chunks of $T_{\text{tile}}$, giving $N/T_{\text{tile}}$ tile-steps. Within each step a tile is fetched from DRAM once and then reused by every thread in the block from fast shared memory. So the DRAM reads per output element drop from $2N$ to $2N/T_{\text{tile}}$. Why this step? Reuse is the whole point of tiling: one DRAM fetch feeds $T_{\text{tile}}$ worth of arithmetic, so DRAM traffic shrinks by the factor $T_{\text{tile}}$.
   • Sub-step 2c — convert to bytes and multiply over all outputs: there are $N^2$ output elements, each a 4-byte float per read: $\text{DRAM bytes}=\underset{\text{outputs}}{\underbrace{N^2}}\times \underset{\text{reads each}}{\underbrace{\frac{2N}{T_{\text{tile}}}}}\times \underset{\text{bytes/float}}{\underbrace{4}}=\frac{8N^3}{T_{\text{tile}}}\text{ bytes}.$ Why this step? Now numerator (FLOPs) and denominator (bytes) are both in hand, so $I$ follows directly.
3. Arithmetic intensity. $I=\frac{2N^3}{8N^3/T_{\text{tile}}}=\frac{T_{\text{tile}}}{4}\text{FLOPs/byte}.$ The $N^3$ cancels — intensity depends only on tile size, not matrix size. For $T_{\text{tile}}=32$: $I=32/4=8$ FLOPs/byte.
4. Machine balance. $I_{\star }=\frac{20\times 10^{12}}{1\times 10^{12}}=20$ FLOPs/byte. Why this number? It's the FLOPs you must do per byte to keep the compute units fed exactly at bandwidth's pace. Below it → starved by memory.
5. Compare. $8<20$ → bandwidth-bound, but $32\times$ less traffic than the naive $T_{\text{tile}}=1$ case ($I=0.25$). Limiting behaviour: to cross into compute-bound you need $T_{\text{tile}}/4\ge 20\Rightarrow T_{\text{tile}}\ge 80$ (reached via register blocking, since 80×80 shared tiles won't fit).

Verify: $I_{\star }=20$, tiled $I=8$ (<20 → bandwidth), naive $I=0.25$ (≪20). Crossover $T_{\text{tile}}=80$. All consistent with Roofline-Model. ✓

---

Ex 9 — Cell J: the exam twist (misaligned base)

Forecast: Ex 1 gave 1 transaction — does a shifted start really cost you?

1. Byte range touched. Thread 0 at byte 64, thread 31 at byte $64+124=188$. Range $[64,191]$. Why include 191? Thread 31 wants bytes 188–191.
2. Which 128-blocks? Block 0 covers $[0,127]$, block 1 covers $[128,255]$. Our range $[64,191]$ straddles the boundary at 128. Why it matters: transactions are aligned to 128-byte block boundaries, not to your data.
3. Count the transactions. The range touches block 0 (bytes 64–127) and block 1 (bytes 128–191), so 2 transactions are needed — even though the data is only 128 bytes wide. Why 2 and not 1? A single fetch can only be one aligned 128-byte block; our data spills across the seam, so no single aligned block contains it all.
4. Efficiency. Useful $=32\times 4=128$ bytes; hauled $=2\times 128=256$ bytes. $\eta =\frac{128}{2\times 128}=\frac{1}{2}=50\%.$

Verify: Alignment halves efficiency here — a classic trap. The lesson: pad allocations so base is a multiple of 128. Same 128 useful bytes as Ex 1, but $2\times$ the fetches because we crossed the seam. Look at strip J in the figure — the colored run sits astride the black gridline. ✓

---

Recall Quick self-test

Stride-2 float read: how many transactions and what efficiency? ::: 2 transactions, 50% (span 252 → ⌈252/128⌉ = 2) Stride-32 float read: how many transactions? ::: 32 (each thread its own 128-byte block) A warp with only thread 0 active reads 1 float — efficiency? ::: 3.125% (4 useful / 128 hauled) All 32 threads read the same shared word — how many cycles? ::: 1 (broadcast exception) AoS with 24-byte struct, one field per thread — transactions? ::: 6 (span 748 → ⌈748/128⌉) Consecutive reads but base=64 — transactions? ::: 2 (range straddles the 128-byte boundary) Tiled matmul T_tile=32 on a 20:1 machine — bound by? ::: bandwidth (I=8 < I* = 20)