Coalesced memory access: Visual walkthrough — Hardware deep dive

Step 1 — One thread asks for one number

WHAT. Picture the GPU's main memory (called global memory, the big off-chip DRAM) as one enormously long ruler of bytes. A byte is one storage slot holding 8 bits. Each slot has an address — its position number on the ruler. We write addresses in hexadecimal (base-16, marked with 0x), but you can read them as "slot 0, slot 4, slot 8…". A float (a decimal number) takes 4 bytes, so data[0] lives at address 0x000, data[1] at 0x004, and so on.

WHY hexadecimal / why bytes. The hardware never counts in "elements" — it counts in bytes, because a byte is the smallest thing memory can address. To predict what the hardware does, we must think in its units, not ours. That is the whole reason coalescing is subtle: we think "array index", it thinks "byte address".

PICTURE. The ruler below shows one thread (call it thread 0, a single worker executing your code) reaching for the 4-byte float at address 0x000.

Step 2 — The hardware never fetches one byte: the transaction

WHAT. When thread 0 asks for its 4 bytes, the memory controller does not hand back only those 4 bytes. It grabs a whole fixed-size chunk — a transaction — that contains the requested address. We call its size $T$ . In our model architecture (a Volta-style GPU) a transaction is a 32-byte sector: an aligned block $[0 x 000, 0 x 01 F]$ , then $[0 x 020, 0 x 03 F]$ , and so on. "Aligned" means every sector begins at an address that is a whole multiple of $T$ — sector boundaries sit at $0, 32, 64, \dots$ and never in between.

WHY a fixed chunk and not exactly 4 bytes. DRAM is built as a grid of rows. Opening a row is the expensive part; once open, streaming out 32 bytes costs almost the same as streaming out 4. So the controller is designed to always deliver a burst. This single hardware fact is the seed of everything: you pay per transaction, not per byte. The tool we need to reason about cost is therefore counting transactions, not counting bytes — that is the "why this tool" for the whole derivation.

PICTURE. Thread 0 wants 4 orange bytes; the hardware returns the entire 32-byte teal sector around them. The other 28 bytes came along for free — useful only if some other thread wanted them.

Step 3 — Threads travel in packs: the warp

WHAT. GPUs never run one thread alone. They run threads in fixed groups called warps of $W = 32$ threads, and — this is the key rule — all 32 execute the same instruction at the same time (this is the SIMT model from 6.2.01-GPU-execution-model). So when the instruction is "load a float", the hardware suddenly has 32 addresses in hand at the same instant.

WHY this matters. Because the 32 requests arrive together, the controller can be clever: it looks at all 32 addresses, then issues the fewest transactions that cover them. If the 32 addresses cluster tightly, few transactions suffice. If they scatter, it needs many. Coalescing is exactly this "how many transactions cover this warp's 32 addresses?" question.

PICTURE. The warp scheduler gathers 32 address-arrows before deciding how many teal buckets to fill.

Step 4 — The best case: consecutive addresses

WHAT. Suppose thread $i$ reads data[i]. Then:

$address (i) = i \times E = i \times 4 bytes$

$i$ ::: the thread's index, $0, 1, 2, \dots, 31$ .
$E = 4$ ::: bytes per float — so consecutive threads land exactly $4$ bytes apart.

Thread 0 → 0x000, thread 1 → 0x004, … thread 31 → 0x07C. Together they span $32 \times 4 = 128$ bytes, the block $[0 x 000, 0 x 07 F]$ — perfectly packed, no gaps.

WHY it's optimal. 128 useful bytes is exactly what the warp wants. Divided into 32-byte sectors, that's $128/32 = 4$ transactions — and every byte fetched is used. You cannot read 128 useful bytes in fewer than 4 sector-transactions, so this is the floor. That is what "coalesced" means: minimum transactions, zero waste. (This clean count secretly assumes the array starts on a sector boundary — we cash that assumption in Step 8.)

PICTURE. 32 arrows tile 4 back-to-back teal sectors with no wasted slot.

$N_{coalesced} = \frac{W \times E}{T} = \frac{32 \times 4}{32} = 4 transactions$

$W \times E$ ::: total useful bytes the warp requests ( $= 128$ ).
Divided by $T$ ::: how many $T$ -byte buckets those bytes fill.

Step 5 — The worst case: a big stride scatters the warp

WHAT. Now let thread $i$ read data[i * S], where $S$ is the stride — the gap in elements between what neighbouring threads grab. Take a large stride so the byte gap $S \times E$ is at least $T$ :

$address (i) = i \times S \times E$

If $S \times E \geq T$ , then every thread's address lands in a different sector. With $S = 8$ floats: gap $= 8 \times 4 = 32 = T$ bytes — thread 0 in sector 0, thread 1 in sector 1, … thread 31 in sector 31.

WHY it collapses. No two threads share a sector, so the controller must issue one transaction per thread: $N = 32$ . Each transaction still drags in a full 32-byte sector, but only $4$ of those bytes are used. So the warp touches $32 \times 32 = 1024$ bytes to use just $32 \times 4 = 128$ .

PICTURE. 32 arrows, each stabbing a separate teal sector; the plum shading marks the 28 wasted bytes per sector.

$N_{strided} = W = 32 transactions (when S \cdot E \geq T)$

Step 6 — Turning transaction-count into time

WHAT. Each transaction carries a latency $L$ — the fixed wait before data starts arriving — of about $L = 300$ ns. For scattered accesses that must be paid per transaction. So:

$t \approx N \times L$

$N$ ::: number of transactions the warp needs.
$L$ ::: latency per transaction (the dominant cost for scattered loads).

Coalesced: the 4 back-to-back transactions overlap and behave like one effective wait, $t_{coalesced} \approx 300$ ns. Strided: $t_{strided} = 32 \times 300 = 9600$ ns.

WHY do 4 bursts cost only one wait? The latency $L$ is mostly the cost of opening a DRAM row — activating a whole page of the memory array into a fast row buffer. The 4 coalesced sectors are 128 adjacent bytes, so they sit in the same open row. You pay the row-open cost once; the second, third and fourth 32-byte bursts are read straight out of the already-open row buffer at streaming speed (that near-zero $0.14$ ns transfer). The 32 strided sectors, by contrast, sit in 32 far-apart rows — each forces its own row-open, so its $L$ cannot be hidden. This "same row = one latency" is exactly the row-buffer locality that also underlies 5.1.05-Cache-coherence-protocols.

PICTURE. A timeline: one short coalesced wait beside 32 stacked strided waits.

$Speedup = \frac{t _{strided}}{t _{coalesced}} = \frac{9600}{300} = 32 \times$

Step 7 — The whole spectrum of stride, including odd ones

WHAT. Real code is rarely "perfect" or "worst". For any stride $S$ where the byte gap is at least one element but less than a sector, the threads pack a fixed number into each sector. In general, one sector of $T$ bytes holds

$threads per sector = \frac{T}{S \times E} (when S \cdot E \leq T),$

so the number of transactions the warp needs is

$N (S) = ⌈ \frac{W}{⌊ T / ( S \cdot E )⌋} ⌉ (aligned, S \cdot E \leq T), N (S) = W (S \cdot E \geq T) .$

$⌊ T / (S \cdot E)⌋$ ::: how many threads' addresses fit inside one $T$ -byte sector (floor, because a partial thread can't share a sector).
$⌈ W / \dots ⌉$ ::: round up — a leftover handful of threads still needs a whole extra transaction.

Worked odd case, $S = 3$ (not a power of two): byte gap $= 3 \times 4 = 12$ ; threads per sector $= ⌊ 32/12 ⌋ = 2$ ; so $N = ⌈ 32/2 ⌉ = 16$ transactions, efficiency $128/ (16 \times 32) = 25%$ .

Stride $S$ (floats)	Byte gap $S \cdot E$	Threads/sector	$N$	Efficiency
$S = 1$	4 B	8	4 (minimum)	100%
$S = 2$	8 B	4	8	50%
$S = 3$	12 B	2	16	25%
$S = 4$	16 B	2	16	25%
$S = 8$	32 B $= T$	1	32 (worst)	12.5%
$S > 8$	$> T$	—	32	$< 12.5%$
$S = 0$	0 B	all 32	1 (broadcast)	broadcast

Read the $S = 2$ row like this: each 32-byte sector holds $T / (S \cdot E) = 32/8 = 4$ float-slots that two threads (8 used bytes) actually touch, so $32/4 = 8$ sectors cover the warp — half the fetched bytes are wasted, hence 50%.

WHY the two ends flatten. Once $S \cdot E \geq T$ you already hit one transaction per thread — bigger strides can't make $N$ exceed 32, they just waste more within each sector. And the degenerate case $S = 0$ (every thread reads the same address) collapses all 32 addresses into one sector, so the hardware does a single broadcast — 1 transaction, cheapest of all. (If instead each thread writes to that one address you get a race; guard it with the tools in 6.2.04-Shared-memory-and-synchronization.)

PICTURE. Efficiency plotted against stride: a staircase falling from 100% down to 12.5%, then flat, with the lone broadcast dot at $S = 0$ .

Step 8 — The alignment wrinkle: what if the array doesn't start on a boundary?

WHAT. Everything above quietly assumed the array's base address is a multiple of $T$ (address $0 mod 32$ ), so the 128 coalesced bytes land in exactly 4 aligned sectors. What if data starts at, say, address 0x004 — a misaligned base? Then thread $i$ reads byte $[4 + 4 i, 4 + 4 i + 3]$ , and the 128-byte span becomes $[0 x 004, 0 x 083]$ : it dips into 5 sectors — a sliver of sector 0, all of sectors 1–3, and a sliver of sector 4.

WHY it costs one extra transaction. The controller can only fetch whole aligned sectors. A span that crosses a sector boundary at both ends touches $⌈ span / T ⌉ + 1$ sectors in the worst case: here $N = 5$ instead of $4$ , and efficiency drops to $128/ (5 \times 32) = 80%$ . Nothing scattered happened — the pattern is still perfectly consecutive — you simply paid a "boundary tax" for starting off-grid.

PICTURE. The consecutive 128-byte span shifted right by 4 bytes, now overlapping 5 teal sectors, the two end-slivers shaded plum as waste.

The one-picture summary

This single figure stacks the two extremes: coalesced (top) tiles 4 sectors with no waste and pays one effective latency; strided (bottom) stabs 32 sectors, wastes 87.5% of what it drags in, and pays 32 latencies. The ratio of the two timelines is the headline $32 \times$ .

Recall Feynman retelling — say it in plain words

Memory is a ruler of numbered slots. When a worker asks for a number, the machine never grabs just that number — it grabs a whole fixed-size crate (a transaction, 32 bytes here) around it, because opening the drawer is the slow part, not scooping the contents. Workers come in gangs of 32 (a warp) that ask at the exact same moment. The machine looks at all 32 requests and opens the fewest crates that cover them. If the 32 numbers sit side by side, four crates hold everything and nothing is wasted — and because those four crates are in the same DRAM "row", you pay the slow row-open only once. If the 32 numbers are spread far apart (a big stride), each needs its own crate in its own row: 32 slow row-opens, and 28 of every 32 bytes are thrown away — that's the whole $32 \times$ story. For in-between strides, count how many workers fit in one crate and divide. Two wrinkles: if your array doesn't start exactly on a crate edge (misaligned), even side-by-side numbers spill into one extra crate; and if the 128 bytes happen to straddle two rows, you pay two row-opens instead of one. Special case: if everyone asks for the same number, one crate broadcasts to all — cheapest of all.

Links: Coalesced memory access · 6.2.01-GPU-execution-model · 6.2.04-Shared-memory-and-synchronization · 6.2.09-Memory-hierarchy · 6.3.02-Roofline-model · 5.1.05-Cache-coherence-protocols · 6.2.08 Coalesced memory access (Hinglish)