GPUgpudivergencecoalescinglanessimd

Lanes, Divergence and Coalescing

Lanes execute in lockstep groups: one instruction, many lanes, different data. Two consequences follow and both are unlike anything on a CPU — a data-dependent branch makes the group execute both sides in sequence, and the memory addresses the lanes request must line up or the traffic multiplies.

Follow the mechanism

Software view, hardware view

The gap between what you wrote and what the machine does is where this whole domain lives.

The question
Why does an `if` inside a GPU kernel cost so much more than the same `if` on a CPU, and why does the access pattern matter more than the number of bytes?
What you wrote
A kernel written as if it were one thread's worth of work, with the runtime instantiating it once per element.
What the hardware does
Lanes are executed in fixed-size groups, one instruction at a time across the whole group. Lanes that should not participate in the current path are masked off and idle. Memory requests from a group are merged into as few wide transactions as the addresses allow.
These two mechanisms explain most of the gap between a kernel that achieves a fraction of peak and one that approaches it. Neither is visible in the source, and neither behaves like the CPU intuition the programmer arrived with — a CPU branch predictor makes a well-predicted branch nearly free, and a CPU handles a strided access with prefetching rather than with multiplied traffic.
Source→Compiler→Instructions→Front End→Execution→Registers→Caches→Memory→I/O→Behavior

One instruction, many lanes

GPU-SPECIFICGroup size is a hardware property that differs between vendors and generations; recent architectures also offer varying degrees of independent lane scheduling, which softens but does not remove the effect.

The kernel source reads like scalar code for a single element. The hardware does not execute it that way: it executes one instruction across a whole group of lanes simultaneously, each lane holding different data. This is the same idea as CPU SIMD: One Instruction, Many Elements, with the vector width hidden by the programming model instead of being written out as vector types.

While every lane wants the same instruction, this is ideal — the arithmetic is perfectly shared and the cost is one instruction for many elements. The model quietly assumes uniformity, and the assumption is what makes the hardware simple enough to have so many lanes in the first place.

The moment lanes want *different* instructions, the hardware has no way to satisfy them at once. It picks one path, masks off the lanes that are not on it, executes, then does the same for the other path. Both paths cost their full time and each lane was idle for one of them.

What the source says, and what the group does
1// Source: reads like one thread per element
2kernel process(x, out):
3    i = my_lane_index()
4    if x[i] > threshold:        // <-- lanes disagree here
5        out[i] = expensive(x[i])
6    else:
7        out[i] = cheap(x[i])
8 
9// Hardware, for a group where some lanes take each side:
10//   1. evaluate the condition on all lanes  -> a mask
11//   2. mask off the false lanes, run expensive()   (false lanes idle)
12//   3. mask off the true lanes,  run cheap()       (true lanes idle)
13//   4. recombine
14// Elapsed cost: expensive() + cheap(), for every group that diverges.

Divergence, and why sorting the data can fix it

The cost of divergence is not per lane, it is per group: if even one lane in a group takes a different path, the whole group pays for both paths. That gives a surprising optimisation — divergence can sometimes be removed without changing the branch at all, simply by rearranging *which elements are in which group* so that groups become internally uniform.

This is why sorting or partitioning input by the branch condition before launching a kernel can produce a large speedup with no change to the kernel body. After partitioning, most groups contain only elements that take the same path, so most groups execute only one side. The branch is still there; it just stopped diverging.

It is also why the CPU intuition misleads. On a CPU, a branch that is *consistently* taken is nearly free because the predictor learns it (Branch Prediction: Guessing Well Enough to Matter), and a branch that alternates unpredictably is the expensive case (Misprediction: What a Wrong Guess Costs). On a GPU, prediction is not the issue — *disagreement within a group* is. A perfectly predictable branch that happens to split each group in half is expensive on a GPU and nearly free on a CPU.

Interleaved data: most groups contain both cases
1// Elements alternate between the two branch outcomes.
2// Nearly every group diverges, so nearly every group
3// pays expensive() + cheap().
4launch process(x_unsorted, out)
5 
6// Effective cost per group: both paths, always.
Partitioned data: most groups are uniform
1// Partition once so like elements are adjacent.
2x_sorted = partition_by(x, e -> e > threshold)
3launch process(x_sorted, out)
4 
5// Most groups now take one path only.
6// Cost per group: one path, plus the one-off partition.

The kernel is identical and the branch is identical. What changed is which elements share a group, and therefore whether the group has to execute both sides. The partition is only worth it when it is cheaper than the divergence it removes, which is an arithmetic question you can answer before writing it.

Coalescing: the addresses have to line up

When the lanes of a group issue loads, the memory system serves them by fetching aligned blocks of device memory. If the lanes request consecutive addresses, their requests merge into a small number of wide transactions and the fetched bytes are all used. If the lanes request scattered addresses, each may require its own transaction, and each transaction still fetches a whole block of which one element is used.

The consequence is that the *traffic* generated by a kernel depends on the access pattern, not just on the number of elements read. A strided access with a large stride can move many times the bytes that the equivalent contiguous access moves, while performing identical arithmetic. This is the same underlying reason a CPU wastes a fetch when it reads one field from a scattered struct — the fetch granularity exceeds the useful data, exactly as in Memory Moves in Lines, Not Variables — but on a GPU it is multiplied across all lanes of the group at once.

That makes layout a first-class GPU concern, and it is the strongest reason GPU code so often uses struct-of-arrays. With separate arrays per field, lanes processing consecutive elements read consecutive addresses and coalesce perfectly; with an array of structs, lanes stride by the struct size and each pulls a mostly-unused block. Array of Structs, or Struct of Arrays? works through the same trade on a CPU, where it matters; here it frequently dominates.

Eight lanes reading one float field. Contiguous versus strided by a 32-byte struct.
usedSIMPLIFIED
lane0 xlane1 xlane2 xlane3 xlane4 xlane5 xlane6 xlane7 x
line 0
32 bytes total1 cache line touched

Struct-of-arrays: one 32-byte transaction serves all eight lanes and every byte is used. With an array-of-structs holding x, y, z and velocity, the same eight lanes would touch eight separate 32-byte blocks and use 4 bytes of each — eight times the traffic for identical arithmetic.

Key points

  • Lanes execute in lockstep groups: one instruction across many lanes, with non-participating lanes masked off and idle.
  • Divergence costs per group, not per lane — one disagreeing lane makes the whole group execute both paths.
  • Partitioning data so groups are internally uniform can remove divergence without touching the branch.
  • CPU intuition inverts here: predictability is what matters on a CPU, agreement within a group is what matters on a GPU.
  • Coalescing makes traffic depend on the access pattern, which is why struct-of-arrays so often wins on a GPU.

Follow the mechanism

The path through the machine, hop by hop — and the conclusions it invites that are wrong.

  1. 1
    Kernel → scheduler: elements are grouped into fixed-size lane groups, and the grouping is what decides divergence.
  2. 2
    Group → lanes: one instruction issues across all lanes; a condition produces a mask rather than a branch decision.
  3. 3
    Divergent branch → both paths: the group executes each side in turn with the other side's lanes masked off.
  4. 4
    Lanes → memory system: the group's addresses are merged into as few aligned wide transactions as they permit.
  5. 5
    Memory → lanes: whole blocks return regardless of how much of each block any lane actually needed.
What people conclude from this — wrongly
  • • "The branch is predictable, so it is cheap" — predictability is a CPU property. A perfectly predictable branch that splits every group in half is expensive here.
  • • "It reads the same number of bytes, so the memory cost is the same" — the transaction, not the element, is the unit of traffic.
  • • "Only a few lanes take the slow path, so the cost is small" — the group pays for the slow path in full regardless of how many of its lanes needed it.
  • • "Sorting the input costs more than it saves" — sometimes true, but it is an arithmetic question, and on strongly divergent kernels the partition usually wins.

Consequences, controls and cost

What it causes
  • • A kernel with data-dependent branching can approach the sum of all its paths rather than the cost of one.
  • • An identical kernel can run several times faster on sorted input than on shuffled input.
  • • Strided or scattered access multiplies memory traffic while the arithmetic stays constant.
  • • Array-of-structs layouts that are merely suboptimal on a CPU can be severely limiting on a GPU.
What you can do
  • • Lay data out so lanes in a group read consecutive addresses — usually struct-of-arrays for the fields a kernel touches.
  • • Partition or sort input by branch condition so groups become internally uniform, when the partition is cheaper than the divergence.
  • • Replace short divergent branches with arithmetic or a select, so both sides are cheap and neither dominates.
  • • Move divergence up: decide once on the host, launch separate uniform kernels, rather than branching per element.
How to see it
  • • Read branch efficiency or divergence metrics from the vendor profiler — they report the fraction of lanes active per issued instruction.
  • • Compare achieved memory throughput against bytes the algorithm actually needs; a large gap indicates poor coalescing.
  • • Run the same kernel on sorted and shuffled input; a large difference with identical arithmetic isolates divergence.
  • • Change only the layout (array-of-structs to struct-of-arrays) and re-measure to isolate the coalescing effect.
What it costs
  • • Struct-of-arrays complicates code that wants a whole logical record at once, and can hurt kernels that touch every field.
  • • Sorting or partitioning costs a pass over the data and extra memory, which must be paid back by the divergence removed.
  • • Branchless rewrites execute both sides unconditionally, which is a loss when one side was genuinely rare and expensive.

Scope

§224 — what these claims are specific to.

What these claims are specific to
  • GPU-SPECIFICLane-group size and the exact coalescing rules are hardware properties that differ by vendor and generation; some recent architectures schedule lanes more independently, which reduces but does not eliminate divergence cost.
  • SIMPLIFIEDThe layout illustration uses a 32-byte transaction and 4-byte elements for clarity; real transaction sizes and alignment rules differ, and the profiler is the authority for any specific device.

Misconceptions

Claim
“Branches are as cheap on a GPU as on a CPU with a good predictor.”
Reality
There is no predictor doing the work here. A divergent group executes both paths in sequence, so the cost is additive rather than probabilistic, and it does not improve with repetition the way a learned branch does.
Claim
“If only one lane takes the rare path, only that lane pays.”
Reality
The whole group pays. One lane entering an expensive path drags its entire group through that path with the other lanes masked off and idle.
Claim
“Memory cost is proportional to bytes requested.”
Reality
It is proportional to transactions issued. Eight lanes reading 4 bytes each from eight different blocks move eight blocks, not 32 bytes.

Where the rest of this lives

Concurrency & Parallelism
Lockstep execution versus independent threads

A lane group is not a set of independent threads and reasoning about it as though it were produces incorrect conclusions about both progress and interleaving.

← What Is Actually Inside a GPUThe Transfer You Forgot to Count →