Warp divergence penalties: Visual walkthrough — Hardware deep dive

This page builds the central result of Warp divergence penalties from absolute zero. By the end you will see why a warp that splits into different paths pays the sum of those paths instead of the max — and you will have earned every symbol along the way.

We only lean on three ideas from elsewhere: the SIMT execution model (one instruction, many threads), warp scheduling (how warps take turns), and later a nod to CPU-style branch prediction to show what GPUs don't do.

Step 1 — What a warp actually is: 32 puppets on one string

WHAT. A warp is a bundle of 32 threads that share a single instruction pointer. There is one instruction decoder; whatever it reads, all 32 threads are handed the same instruction on the same clock tick.

WHY start here. Every later penalty comes from one fact: the 32 threads cannot read different instructions at the same time. If you don't feel this, nothing after makes sense. So we picture it first.

PICTURE. Look at the figure: one decoder (the puppeteer) pulls one string, and all 32 puppets raise the same arm. There is no way for puppet 5 to raise a different arm this tick — the string is shared.

Step 2 — Time is measured in instruction cycles

WHAT. We measure cost in instruction cycles: one cycle = the decoder issuing one instruction to the warp. If a code path is a straight list of $n$ instructions with no branches, it costs $n$ cycles for the whole warp — all 32 lanes finish together.

WHY this unit. We need a currency to add up costs. Cycles are perfect because in SIMT one issued instruction serves all 32 lanes at once, so "cost" doesn't depend on how many lanes are active — only on how many instructions get issued.

PICTURE. A straight blue pipe of $n$ boxes; 32 parallel lanes flow through it side by side, entering and leaving together. Cost is the length of the pipe, not the number of lanes.

Step 3 — The fork: what happens when lanes disagree

WHAT. A branch (if, while, for) asks each lane a yes/no question. When some lanes answer true and others false, we have warp divergence. The lanes want to run two different instruction streams — but Step 1 forbids that on one tick.

WHY this is the crisis. This is the exact moment the shared string breaks the illusion of parallelism. We must now decide how the hardware copes, because it physically cannot do both streams at once.

PICTURE. One incoming warp hits a diamond (the branch). The active mask splits: some lanes lit green (condition true), the rest greyed out. Two pipes leave the diamond — but only one can be fed by the decoder at a time.

Step 4 — Running path A: half the warp works, half burns idle

WHAT. The hardware picks path A. It sets the active mask so only the true lanes keep results; the false lanes are masked off. It issues all of path A's instructions. The masked lanes still receive every instruction — they just discard the output.

WHY it must issue to idle lanes. There is one decoder (Step 1). To feed path A's true-lanes, the decoder issues path A's instructions to the entire warp; the false-lanes have no choice but to sit through them with a zero mask. You cannot decode "for some lanes only."

PICTURE. Path A's pipe (length $T_{A}$ ) with green lanes flowing and grey lanes parked beside it, wasting time. The clock on the side ticks off $T_{A}$ cycles.

Step 5 — Running path B, then adding: the sum appears

WHAT. The stack is popped. Now the mask flips: the false lanes (path B) light up, the true lanes go grey. The decoder issues all of path B's instructions, costing $T_{B}$ cycles. Only after both are done do we reconverge.

WHY the two costs add. Path A and path B ran on the same decoder at different times. There was never a tick where A's instructions and B's instructions were both issued. So the wall-clock time is A's cycles followed by B's cycles — an addition, not a max.

PICTURE. The A-pipe and B-pipe drawn end-to-end on a single timeline. The total length is clearly $T_{A} + T_{B}$ , with a reconverge marker where the full green mask returns.

Step 6 — What it should have cost: the max, and the efficiency ratio

WHAT. Imagine no divergence — all 32 lanes took the same path. Then only one pipe is issued, and its cost is just that pipe's length. The best-case cost when several paths could exist is the longest single one, $max (T_{1}, \dots, T_{k})$ , because in an ideal parallel machine the paths would overlap in time.

WHY compare to max. To measure the penalty we need a yardstick: "how fast could this have gone if the lanes overlapped perfectly?" That ideal overlaps all pipes, so the finish time is set by the slowest one — the max. Dividing gives a clean efficiency fraction.

PICTURE. Left: the ideal — all pipes stacked in parallel, finishing at $max$ . Right: reality — the same pipes laid end-to-end, finishing at the sum. The ratio of the two bar lengths is the efficiency.

Step 7 — Edge case: worst case is 32 distinct paths ( $k = 32$ )

WHAT. Push the branch to its cruelest limit: every one of the 32 lanes takes a different path, each path $n$ instructions long. Then $k = 32$ and every $T_{i} = n$ .

WHY cover this. The reader must never hit an unexplained scenario. The famous "GPUs can lose up to $32 \times$ " number lives exactly here — and it drops straight out of our sum formula.

PICTURE. Thirty-two identical pipes, each length $n$ , stacked end-to-end into one long chain of length $32 n$ . Beside it, the ideal single pipe of length $n$ .

Step 8 — Degenerate cases: no divergence, and lopsided divergence

WHAT. Two boundary scenarios that surprise people.

(a) No divergence ( $k = 1$ ). All 32 lanes agree. One pipe, full mask the whole time. $T_{diverged} = T_{1} = max$ , efficiency $= 100%$ . This is the goal of every mitigation in the parent note (align branches to warp boundaries).

(b) Lopsided divergence — "only 1 lane is different". One lonely lane takes a 100-instruction path; the other 31 take a 50-instruction path. Intuition screams "31/32 agree, so it's basically free!" — but our formula ignores lane counts entirely.

WHY it matters. This is the #1 mistake in the parent note. The sum formula has no term for how many lanes took a path — only how many distinct paths exist and how long each is. One dissenting lane still forces its whole pipe to be issued.

PICTURE. Left panel: full-green single pipe, 100% efficient. Right panel: a fat 31-lane pipe (50 long) and a thin 1-lane pipe (100 long), still laid end-to-end for $150$ cycles — the thin pipe costs the same clock time as if all 32 lanes used it.

The one-picture summary

Everything collapses into one image: a warp enters, the mask splits into $k$ pipes, the pipes are issued one after another (sum), and we compare that end-to-end length against the ideal overlapped length (max).

Recall

Feynman retelling — say it to a 12-year-old Thirty-two friends are chained together and can only take one step at a time, all the same step, because one leader calls out the moves. They reach a fork. Some want to go left, some right — but the chain can only be walked one way at a time. So the leader marches the whole chain down the left path while the right-wanters get dragged along doing nothing, then marches everyone down the right path while the left-wanters get dragged doing nothing. The total time is the left walk plus the right walk — added, not overlapped. If instead everyone had wanted the same direction, they'd walk it once: that's the ideal. The slowdown is (both-walks-added) divided by (the-longer-single-walk). In the worst case all 32 want different forks, and you walk 32 separate paths one after another — 32 times slower. And it never helps that only one kid wanted a weird path: the whole chain still has to walk that path once, because you can't decode a move for just one link of the chain.

Ready to fix this? See CUDA optimization patterns and occupancy optimization; the data-layout cure connects to memory coalescing and parallel algorithm design.

Recall Quick self-test

A warp splits into 3 paths of length 12, 40, 8 cycles. Diverged cost? ::: $12 + 40 + 8 = 60$ cycles. Same warp, ideal cost? ::: $max (12, 40, 8) = 40$ cycles. Efficiency? ::: $40/60 \approx 66.7%$ . If only 1 lane takes the length-40 path and 31 take length-8, does the 40-pipe get cheaper? ::: No — cost is per distinct path, not per lane; it still costs its full 40 cycles worth of issued instructions.