Memory Coalescing

Thirty-two addresses walk into a memory system. That is not the setup for a joke — it is what happens every time a warp executes one load instruction. Each lane computes its own address, so a single ld arrives at the memory pipeline as a bundle of 32 requests, and what happens next decides more GPU performance than any other single mechanism in this module. You already know from divergence that a warp's lanes can waste the compute engine by disagreeing about control flow; this lesson is the memory-side twin: lanes can waste the memory engine by disagreeing about where their addresses point. The referee is a piece of hardware called the coalescer, and its rules are simple enough to fit on a napkin — yet ignoring them routinely costs software a factor of ten to thirty.

The coalescer's napkin rules

DRAM does not sell individual bytes. As you saw when the memory wall first loomed, memory systems move data in fixed-size chunks — on a GPU, 32-byte sectors, grouped into 128-byte cache lines (four sectors). The coalescer looks at a warp's 32 addresses and asks one question: how few sectors cover all of them? It merges every request landing in the same sector into a single fetch, and issues one memory transaction per distinct sector touched.

one warp load/store = 32 addresses at once; the coalescer merges them into the minimum set of 32-byte sectors;
cost is counted in sectors fetched, not elements requested — efficiency = useful bytes ÷ fetched bytes;
the golden pattern: consecutive lanes read consecutive words — 32 four-byte loads collapse into 4 sectors (one 128-byte line), 100% efficiency;
scattered addresses fetch scattered sectors: worst case one transaction per lane, 32× the traffic for the same useful data.

Work the golden case once by hand. Lane t reads the 4-byte float at address 4t: lanes 0–7 land in sector 0 (bytes 0–31), lanes 8–15 in sector 1, and so on — 4 sectors, 128 bytes fetched, 128 bytes used. The whole warp's load is one cache-line fill. Now stretch the same warp out with a stride: lane t reads address 4st for stride s elements, and the requests spread across \min(32,\,4s) sectors:

Access pattern (4-byte floats)	Sectors fetched	Bytes fetched	Efficiency
Unit stride, aligned	4	128	100%
Unit stride, misaligned by 4 B	5	160	80%
Stride 2	8	256	50%
Stride 8	32	1024	12.5%
Stride 32	32	1024	12.5%
Random gather	up to 32	up to 1024	as low as 12.5%

Read the misaligned row kindly: starting the warp 4 bytes off a sector boundary drags in one extra sector — an 80% day, mildly annoying. Strides are the real villain: by stride 8 every lane owns its own sector, the memory system hauls 1024 bytes to deliver 128 useful ones, and your kernel's effective bandwidth is one-eighth of the number on the spec sheet. Nothing further degrades after that — the damage saturates at one transaction per lane — which is why stride 8 and stride 32 tie for last place.

The cliff

Plotting efficiency against stride gives one of the most consequential curves in GPU programming — a cliff edge right at the origin. Efficiency is \min\!\left(1, \tfrac{32}{e\,s}\right)\cdot 100\% for element size e bytes and stride s: it halves at stride 2, halves again by stride 4, and flatlines once every lane occupies its own sector. Larger elements hit the floor sooner — and the floor itself is higher, because a fat element fills more of its sector:

Notice there is no gentle regime: the difference between stride 1 and stride 2 is already a factor of two of your memory bandwidth. Coalescing is not a tuning refinement — it is the first-order term.

AoS vs SoA: the data-layout lesson

Almost every real coalescing disaster is the same disaster: a sensible-looking array of structures (AoS). Store 3-D points as x y z x y z … and ask a warp to read everyone's x:

// AoS — array of structures: lane t reads xyz[3 * t], stride 3. interface PointAoS { x: number; y: number; z: number } // memory: x0 y0 z0 x1 y1 z1 x2 y2 z2 ... — the x's are 12 bytes apart // SoA — structure of arrays: lane t reads xs[t], stride 1. interface PointsSoA { xs: number[]; ys: number[]; zs: number[] } // memory: x0 x1 x2 ... | y0 y1 y2 ... | z0 z1 z2 ... — the x's are contiguous

The AoS read is a stride-3 access — 12 sectors instead of 4, a third of your bandwidth gone before the kernel computes anything. The structure of arrays (SoA) layout stores each field contiguously, so "everyone's x" is the golden unit-stride pattern. Same data, same bytes, same algorithm — the layout is the optimisation. This is the single most transferable lesson of the module: on a machine where 32 threads touch memory simultaneously, data layout is not a detail of style, it is the shape of your memory traffic.

The coalescer, executable

The hardware's core loop is countable in a dozen lines: bucket each lane's address into its 32-byte sector, count distinct sectors, compare against bytes actually wanted. Here it is grading the patterns from the table — plus the "CPU-style chunking" pattern you will meet in the warning below:

// The coalescer: collapse a warp's 32 lane addresses into unique 32-byte sectors. const SECTOR = 32; const lanes = [...Array(32).keys()]; function sectors(addrs: number[]): number { const seen = new Set<number>(); for (const a of addrs) seen.add(Math.floor(a / SECTOR)); return seen.size; } function report(name: string, addrs: number[]): void { const n = sectors(addrs); const useful = addrs.length * 4; // 32 four-byte loads wanted const fetched = n * SECTOR; const eff = (100 * useful / fetched).toFixed(1); console.log(`${name.padEnd(26)} ${String(n).padStart(2)} sectors ${String(fetched).padStart(4)} B fetched efficiency ${eff}%`); } report("unit stride", lanes.map((t) => t * 4)); report("misaligned by 4 B", lanes.map((t) => 4 + t * 4)); report("stride 2", lanes.map((t) => t * 8)); report("stride 32", lanes.map((t) => t * 128)); report("CPU-style chunks (N=1024)", lanes.map((t) => t * 1024 * 4)); // seeded pseudo-random gather — same "random" every run let s = 12345; const rnd = () => (s = (s * 1103515245 + 12345) % 2147483648) / 2147483648; report("random gather", lanes.map(() => Math.floor(rnd() * 4096) * 4));

Change the misalignment offset to 32 (a whole sector) and watch the penalty vanish — alignment only matters modulo the sector size. Then try stride 3, the AoS case, and check it against the \min(32, 4s) formula.

Because DRAM is a burst device. Opening a row of a DRAM chip is slow and expensive, but once open, the chip streams a burst of consecutive bytes at full interface speed — modern GDDR delivers data in bursts that map naturally onto 32-byte sectors. Requesting one byte costs essentially the same time and energy as requesting the whole burst, so the memory system rounds every request up. CPUs made the same choice decades ago (64-byte cache lines) for the same reason. The GPU twist is scale: a CPU miss fetches one line for one core's load, while a GPU warp can legitimately need 32 different lines at once — so the hardware was given a coalescer to catch the cases where those 32 requests were secretly one.

A seasoned CPU programmer parallelising a loop over N items gives each thread a contiguous chunk: thread t takes elements [tN/T,\;(t{+}1)N/T). On a CPU that is perfect — each core streams its own cache lines. Port it to a GPU and it is a catastrophe, because the lanes of a warp execute the same load simultaneously: on iteration 0, lane 0 reads element 0, lane 1 reads element N/T, lane 2 reads 2N/T… — a giant stride, one transaction per lane, every iteration. The GPU-right pattern is interleaved: thread t takes elements t,\;t{+}T,\;t{+}2T,\dots — then on every iteration consecutive lanes read consecutive elements, the golden pattern. Each individual thread's accesses look scattered, and that is fine: coalescing is about what a warp does in one instant, not what one thread does over time. This inversion is the number-one performance bug in code ported from CPUs.