Warp divergence penalties: Question bank — Hardware deep dive

This is a self-test page. Each line hides its answer after the :::. Cover the right side, commit to a guess out loud, then reveal. Every answer gives you the reasoning, not just a verdict — that reasoning is the thing you must be able to reproduce.

If a word here feels unfamiliar (warp, mask, predication, reconverge), pause and rebuild it from the parent note Warp divergence penalties before continuing. This bank assumes you already own those definitions and only tests whether you can use them under pressure.

Definition

The symbols used on this page Throughout, a path means one branch of a conditional (e.g. the if body, or one case). For a path labelled $i$ :

$T_{i}$ = the latency of path $i$ measured in cycles for a single serialized pass of the warp through that path — i.e. how long the warp takes to run that path's instructions once, with the lanes on that path active and the rest masked. It is a per-warp-pass time, not a per-thread time and not multiplied by how many threads took it.
$T_{A}$ , $T_{B}$ = the same quantity for a two-way branch, the if path and the else path respectively.
$b$ = the fixed branch/mask-stack overhead a real conditional pays even before any path body runs: the cycles spent evaluating the condition, building the active mask, pushing/popping the divergence stack, and jumping. Predication has no $b$ (there is no branch), but always runs both bodies.

Every cost claim below is built from these. Read the derivation box before the questions.

Intuition

Why the cost is the SUM of the path times (the core claim, derived) Under SIMT, all 32 lanes of a warp share one program counter and one instruction decoder. The hardware cannot run two different instructions at once for one warp. So when lanes disagree at a branch, it does this:

Build an active mask (a 32-bit flag: 1 = execute, 0 = masked-off) for path A.
Run path A's instructions with that mask. Cost so far: $T_{A}$ .
Flip the mask to path B and run path B's instructions. Cost: another $T_{B}$ .
Reconverge (restore the full mask) and continue.

Because steps 2 and 3 happen one after the other on the same shared program counter, the times add: total $= T_{A} + T_{B}$ . Nothing here depends on how many threads took each path — the count only decides which mask bits are set, not how long the pass takes. Generalising to $k$ paths gives $\sum_{i = 1}^{k} T_{i}$ . That single fact is what almost every trap below secretly violates by trying to average instead of add.

This is exactly what figure s01 draws: a blue mask for pass A stacked above a pink mask for pass B, the yellow "serial in time" arrow between them, and the full yellow mask at reconvergence. Trace that vertical stack and you have literally watched $T_{A} + T_{B}$ happen.

Figure s01 — the mask stack. The number of coloured (active) squares in each row is irrelevant to the row's length; only the fact that the two rows run one-below-the-other (serial) makes the times add. Refer back to this whenever a question tempts you to average by thread count (every "Spot the error" averaging trap is answered by this picture).

Figure s02 — divergent execution timeline for the 4-path example. Every "Why questions" item about $max (T_{i})$ in the numerator and $\sum T_{i}$ in the denominator maps directly onto the top bar versus the row of bottom bars here.

Definition

What "warp-aligned condition" means A branch condition is warp-aligned when every one of the 32 threads in a warp is guaranteed to evaluate it the same way, so the warp never splits. Example: if ((idx / 32) % 2 == 0) — since idx / 32 is the warp id, all 32 lanes of a warp share it, so all 32 agree. Contrast if (idx % 2 == 0), where lanes disagree every other thread. Anything derived only from blockIdx, warpId = idx/32, or a compile-time constant is warp-aligned; anything derived from threadIdx at sub-warp granularity generally is not.

Figure s03 is the whole mitigation story in one picture: on the left, idx % 2 == 0 paints the lanes alternately blue/pink — a split mask, cost $T_{A} + T_{B}$ . On the right, (idx / 32) % 2 == 0 paints every lane the same colour — one full mask, cost $T_{A}$ only. Any "Spot the error" or "Why" item about moving the decision to blockIdx/warpId is answered by comparing these two panels.

Figure s03 — sub-warp condition (diverges, left) versus warp-aligned condition (no split, right). This is the visual you should picture whenever you read the words "warp-aligned" below.

Recall

Step-through the mask yourself (do this before the questions) Reveal one line at a time and mentally colour figure s01's rows as you go — this is the "animation" done by hand. Step 1 — all 32 lanes hit the branch, one shared PC, full mask. What does the mask look like? ::: All 32 squares lit; no split yet — this is the top of figure s01 before it forks. Step 2 — lanes evaluate the condition and disagree. What happens to the mask? ::: It splits into the blue (path A) row and the pink (path B) row of s01; the hardware pushes one onto the divergence stack. Step 3 — path A runs. Which lanes burn cycles, which idle? ::: Blue lanes active for $T_{A}$ cycles, pink lanes idle-but-still-waiting; the warp's clock advances by $T_{A}$ . Step 4 — path B runs. What is the running total now? ::: Pink lanes active for $T_{B}$ more cycles; running total $T_{A} + T_{B}$ — the two stacked rows of s01. Step 5 — reconverge at the IPDOM. What is restored? ::: The full 32-lane mask (the bottom yellow row of s01); execution continues in lockstep.

True or false — justify

True or false: If 31 of 32 threads take path A and only 1 takes path B, the warp pays almost nothing for path B.

False. The warp executes path B fully for that lone thread while the other 31 sit masked-off; cost is

T_{A} + T_{B}

(both full path latencies), unaffected by the 31-to-1 split — exactly the two stacked rows of figure s01, regardless of how few squares are lit in one row.

True or false: A branch where all 32 threads evaluate the condition the same way causes no divergence penalty.

True. If every thread agrees, only one path is taken and the other is never entered — there is nothing to serialize, so the mask stays full the whole time (the right panel of figure s03).

True or false: Divergence can happen across two different warps in the same block.

False. Divergence is defined within a single warp. Two warps taking different paths just run as two independent warps — that is normal scheduling, not divergence.

True or false: The masked-off threads during a divergent path consume ALU issue slots exactly like active threads.

False — this is the nuance. Masked lanes do not retire useful work and on many architectures do not occupy the ALU pipeline the same way (some can even skip issue for whole-mask-off cases). But the warp still spends the full

T_{A}

then

T_{B}

of time on the shared PC, so wall-clock cost adds and power is still burned. It is the serialized time, not the per-lane slot accounting, that hurts.

True or false: An if with no else cannot cause divergence because there is only one body.

False. The "else" is implicitly "do nothing and skip to the merge point." Threads that fail the condition are masked while the body runs, so you still serialize the taken body against the skip.

True or false: Using ? : (ternary) instead of if/else always removes the divergence penalty.

False. It only helps when the compiler turns it into predication for short bodies. For long or side-effect-heavy bodies it still compiles to a real branch, and both sides still run.

True or false: A switch statement with 4 cases can, in the worst case, cost the sum of all 4 case bodies in one warp.

True. If the warp's threads scatter across all 4 cases, the hardware serializes all four masked passes —

\sum_{i = 1}^{4} T_{i}

— exactly like a 4-way if/else-if chain (the four end-to-end bars of figure s02).

True or false: Loop divergence is bounded by the average trip count across the warp.

False. It is bounded by the maximum trip count. The warp keeps iterating (with a shrinking mask) until the last thread's loop condition fails.

True or false: Two warps that each internally diverge the same way waste the same fraction of their peak throughput.

True. Efficiency is a per-warp ratio

\frac{max ( T _{i} )}{\sum T _{i}}

; identical path distributions give identical efficiency regardless of which warp you look at.

True or false: If a branch is data-dependent (depends on values loaded from memory), the compiler can predict it and avoid divergence.

False. That is CPU-style branch prediction (see 8.4.2-Branch-prediction). GPUs have no such speculation for divergent lanes; data-dependent branches diverge at runtime whenever the loaded values disagree.

True or false: Reconvergence for a clean if/else always happens at the instruction right after the else block.

True for structured code — that instruction is the immediate post-dominator, the first point every path reaches. For unstructured control flow (early goto, breaking out of nested loops) the IPDOM can be elsewhere or delayed, so you cannot assume the naive merge point.

Spot the error

Spot the error: "Only 2 of 32 threads hit the else, so cost ≈ 50 + 100/32 ≈ 53 cycles."

Wrong model — you averaged the else across 32 threads. The real cost is

T_{A} + T_{B} = 50 + 100 = 150

: both path latencies add in full, weighted by nothing (the two stacked rows of figure s01, not a thread-count average).

Spot the error: "if (idx % 2 == 0) splits work evenly, so the warp stays 50% busy the whole time."

The 50% figure is per-lane utilization, but the time doubles because both halves run serially. Even-odd splitting is a textbook non-warp-aligned condition (the left panel of figure s03): it guarantees divergence in every warp.

Spot the error: "Nesting if inside if always multiplies the penalty, so flatten everything."

Nesting inside a single already-taken path just adds to that path's

T_{i}

— no new serialization. Only nesting that creates orthogonal path splits multiplies the number of distinct paths.

Spot the error: "I sorted the data by type, so now there is zero divergence anywhere."

Only if the sort is aligned to warp size (32). If a type boundary falls in the middle of a warp, that boundary warp still diverges. Sorting must bucket in multiples of 32 to fully eliminate it.

Spot the error: "Predication only helps when

T_{A} + T_{B} > 2 max (T_{A}, T_{B})

Backwards. Predication always executes both sides, so its cost is exactly

T_{A} + T_{B}

, which can never exceed

2 max (T_{A}, T_{B})

. Predication is worth it when its fixed cost beats the expected branch cost — see the derivation in the "why" below; the useful regime is when both bodies are short, not when the inequality above holds (it never does).

Spot the error: "counts = [1,1,1,...,1,1000] — one big thread, so cost ≈ average ≈ 32 iterations."

The single count-1000 thread holds the whole warp hostage for 1000 iterations. Loop cost tracks the max, so it is ~1000 iterations of the loop body, with 31 lanes idle for almost all of it.

Spot the error: "I moved my if to depend on blockIdx instead of threadIdx, but divergence is unchanged."

A condition on blockIdx is warp-aligned — every thread in a warp shares the value → all agree → no divergence (the right panel of figure s03). Moving the decision to block or warp granularity is exactly the fix.

Why questions

Why can't the hardware just skip instructions for masked-off threads instead of issuing them?

In SIMT a single decoder broadcasts one instruction to all 32 lanes off one program counter. There is no per-lane program counter to run ahead independently, so a divergent path must be walked as its own masked pass and the passes serialize in time.

Why, precisely, is predication ever worth it if it always runs both sides at cost

T_{A} + T_{B}

A real divergent branch also costs

T_{A} + T_{B}

when the warp splits, plus the fixed branch/mask-stack overhead

b

defined in the symbols box (condition eval, mask build, stack push/pop, jump). If the branch rarely splits, its expected cost is close to

max (T_{A}, T_{B}) + b

. Predication is the win when both bodies are so short — roughly

\leq 4 - 5

instructions each, so

T_{A}, T_{B}

are tiny — that paying

T_{A} + T_{B}

every time (with no

b

) is still cheaper than the branch overhead

b

plus the risk of a full split. Long bodies make

T_{A} + T_{B}

dominate and predication loses.

Why is data-dependent branching (ray tracing, particle types) called "catastrophic" while a fixed idx < 16 split is merely bad?

A fixed split has at most 2 paths; data-dependent code can scatter threads across many paths in one warp, and worst case each of 32 threads takes a unique path — cost

\sum_{i = 1}^{32} T_{i}

, up to a full

32 \times

slowdown.

Why does aligning divergence to warp boundaries eliminate the penalty rather than just reduce it?

A warp-aligned condition makes all 32 lanes agree, so only one path is ever entered — the other is never executed at all (figure s03, right panel). There is literally nothing to serialize, so the penalty is zero, not merely smaller.

Why does the efficiency formula use

max (T_{i})

in the numerator?

max (T_{i})

is what the same work would cost if all threads ran in parallel (the slowest path sets the pace) — the single top bar in figure s02. Dividing that ideal parallel time by the serialized sum

\sum T_{i}

(the row of bottom bars) gives the fraction of peak you actually keep.

Why can sorting data by type completely fix divergence in the ideal case, but branch predication cannot?

Sorting makes every thread in a warp agree (warp-aligned), so the branch is never diverged. Predication leaves the disagreement in place and just executes both sides anyway — it hides the branch, not the wasted work.

Why does reconvergence location matter for unstructured control flow?

The hardware restores the full mask at the immediate post-dominator. In clean code that is the obvious merge point, but with goto/nested break the earliest guaranteed-common instruction can be far downstream, so lanes stay diverged longer than you'd guess and utilization suffers until they finally rejoin.

Why is warp divergence relevant to occupancy tuning (6.2.12-Occupancy-optimization) even though occupancy is about resident warps, not branches?

Divergence lowers useful throughput per warp, so you may need more resident warps to hide the wasted cycles. High occupancy can partially mask divergence latency but never removes the serialized instruction count itself.

Why does coalesced memory access (6.2.10-Memory-coalescing) sometimes get destroyed by the very divergence pattern you introduced?

Once threads split onto different paths, the active lanes in each pass are a scattered subset of the warp, so their memory addresses no longer form the contiguous, aligned run that coalescing needs — you lose both parallelism and bandwidth.

Edge cases

Edge case: A warp where all threads exit the loop on iteration 0 (every count is 0).

No iterations run for anyone; the loop-entry branch is unanimously false, so there is no divergence and essentially no cost — the degenerate zero case is actually the cheapest.

Edge case: A warp is only partially filled (e.g. a block of 20 threads, last warp has 12 real threads).

The 20 "missing" lanes are inactive from the start (their mask bit is off for the whole kernel). They are not divergence, but they do waste slots — a separate under-utilization, not a per-branch penalty.

Edge case: Every thread in the warp takes the same path but that path contains an internal loop with equal trip counts.

Zero divergence: identical conditions at every branch mean the mask never fragments, and equal trip counts keep every lane exiting the loop on the same iteration. The warp stays fully converged and runs at full efficiency, reconverging cleanly at the loop's IPDOM.

Edge case: An if/else where path A is 1000 cycles and path B is 1 cycle, and exactly one thread takes A.

Cost is

T_{A} + T_{B} = 1000 + 1 = 1001

cycles. The single A-thread drags the whole warp through 1000 masked cycles; splitting count is irrelevant — this is the classic "one slow lane" trap, the extreme version of figure s01.

Edge case: Nested branches producing 4 orthogonal paths, but in one particular warp all 32 threads land in the same leaf.

That warp diverges not at all — it only ever enters one leaf path. Worst-case is 4 paths potentially, but the actual cost depends on the runtime distribution, which here is unanimous.

Edge case: A while loop whose condition is true for all lanes until a data-dependent break, and one lane breaks 100× later than the rest.

The warp runs until the last lane breaks (reconvergence at the loop's IPDOM), so ~100 extra iterations execute with a single active lane. Effective utilization collapses toward

1/32

during that tail.

Edge case: Two disjoint if blocks back-to-back, each diverging, but on the same 16/16 split.

They do not compound into 4 paths — each is an independent 2-path region that reconverges before the next. Total cost is the sum of the two regions' path sums, not their product.

Recall

One-line summary to carry away Divergence cost = ==sum of the path latencies $\sum T_{i}$ , per warp; the fix is to make a warp's 32 threads agree via a warp-aligned condition== (derived from warpId/blockIdx, or sort data to multiples of 32) or to predicate only short (≤~5-instruction) bodies. Reconvergence happens at the immediate post-dominator.

See also: 6.2.9-Warp-scheduling, 9.3.5-Parallel-algorithmsdesign, 10.1.3-CUDA-optimization-patterns, and the Hinglish walkthrough 6.2.11 Warp divergence penalties (Hinglish).