Worked examples — Warp divergence penalties

This page is the worked-examples floor for the parent topic. The parent showed you what divergence is; here we grind through every kind of case a warp can throw at you, one number at a time. If a symbol shows up, we define it before using it.

Recall The two numbers that decide everything

Read this first — every example below is just these two lines applied.

• Let $T_i$ be the number of cycles (one "cycle" = one instruction issued to the hardware) that path $i$ needs.
• Ideal time (no divergence) $=\max (T_1,\dots ,T_k)$ — all paths overlap, the slowest sets the pace.
• Diverged time $=T_1+T_2+\cdots +T_k$ — paths run one after another.
• Efficiency $=\frac{\text{ideal}}{\text{diverged}}=\frac{{\max }_i{T}_i}{{\sum }_i{T}_i}$.

A "path" is a distinct straight-line route through the code that at least one thread in the warp actually takes. Threads that take the same route share a path — they cost nothing extra.

Before the matrix, one picture of the whole idea so every later example has a home.

Look at the figure: the horizontal axis is time in cycles. In the top bar all 32 threads march together (one path). In the bottom bar the warp split into two groups — notice the second group can only start after the first group finishes. That waiting gap is the penalty. Nothing else on this page is more complicated than that gap.

---

The scenario matrix

Every problem about warp divergence falls into one of these cells. We will hit each one with at least one worked example.

Cell	Case class	What is special about it
C1	Even 2-way split (if/else, half–half)	baseline; two paths, both non-trivial
C2	Uneven split (1 thread vs 31)	tests the "few threads = cheap?" trap
C3	Zero divergence (all threads same path)	the degenerate good case, efficiency = 1
C4	Full divergence (every thread its own path)	the worst case, the $1/32$ limit
C5	Multi-way else if chain	$k>2$ paths, unequal lengths
C6	Loop / while divergence	trip-count varies per thread
C7	Predication decision (branch or predicate?)	limiting comparison $T_A+T_B$ vs $2\max$
C8	Nested ifs → orthogonal paths	path count multiplies
C9	Real-world word problem (ray tracing materials)	applies C4/C5 to data
C10	Exam twist (warp-boundary re-alignment)	restructure to reach C3

Cross-links you may want while reading: 6.2.8-SIMT-execution-model (why one instruction drives 32 lanes), 6.2.9-Warp-scheduling (how idle warps hide latency), 8.4.2-Branch-prediction (the CPU cousin), 10.1.3-CUDA-optimization-patterns (the fixes at scale).

---

Worked examples

Example 1 — Cell C1 (even 2-way split)

Forecast: Guess the efficiency before reading on. Most people say "50% because half go each way." Hold that thought.

1. Identify the distinct paths. Two paths are actually taken: A ($T_A=12$) and B ($T_B=9$). Why this step? Cost depends on paths taken, never on how many threads take each — that is the whole lesson of 6.2.8-SIMT-execution-model.
2. Diverged time $=T_A+T_B=12+9=21$ cycles. Why this step? The else-group waits while the if-group runs, then runs after (see the gap in figure s01).
3. Ideal time $=\max (12,9)=12$ cycles. Why this step? If nobody had diverged, all 32 lanes overlap; the slower path alone sets the clock.
4. Efficiency $=12/21=0.5714=57.1\%$. Why this step? Ratio of what we could have taken to what we did take.

Verify: Efficiency must satisfy $\max /\sum \le 1$ and $\ge \max /(k\cdot \max )=1/k=1/2$. We got $0.571$, which sits in $[0.5,1]$. Note it is not 50% — the "half–half" intuition was wrong because the two paths have different lengths. ✔

---

Example 2 — Cell C2 (uneven split, the "few threads" trap)

Forecast: The tempting wrong answer is $50+\frac{100}{32}\approx 53$ cycles — "only one thread does the expensive thing, so amortise it." Guess whether that is right.

1. Distinct paths taken: two — a 100-cycle path (1 thread) and a 50-cycle path (31 threads). Why this step? Even a single diverging thread creates a full second path.
2. True diverged cost $=100+50=150$ cycles. Why this step? The hardware runs the 100-cycle path for the whole warp (31 lanes masked off but still idle-waiting), then the 50-cycle path. Thread count never divides the cost.
3. Naive (wrong) estimate $=50+100/32=53.125$ cycles. Why this step? We compute it only to expose it as a myth.
4. Ideal $=\max (100,50)=100$; efficiency $=100/150=0.6667=66.7\%$.

Verify: True cost 150 vs naive 53.125 — they differ by nearly $3\times$, confirming the myth is dangerous. Efficiency $0.667\in [0.5,1]$. ✔

---

Example 3 — Cell C3 (zero divergence, degenerate good case)

Forecast: Guess before reading: what is the best efficiency ever possible?

1. Distinct paths taken: just one — path B. Path A is never entered by any thread, so it does not exist for this warp. Why this step? An untaken branch is free; the hardware skips over it with the mask all-off, no cycles issued.
2. Diverged time $=9$ cycles. Ideal $=\max (9)=9$.
3. Efficiency $=9/9=1.00=100\%$.

Verify: When $k=1$, $\frac{\max }{\sum }=\frac{9}{9}=1$. This is the degenerate ceiling — you can never beat 100%. It confirms the goal of every mitigation in 10.1.3-CUDA-optimization-patterns: collapse to $k=1$. ✔

---

Example 4 — Cell C4 (full divergence, the $1/32$ limit)

Forecast: Guess the efficiency as a simple fraction.

1. Number of distinct paths $k=32$ (all different). Why this step? $k$ is the count of routes actually walked; here it maxes out at the warp size.
2. Diverged time $=32\times 7=224$ cycles. Why this step? 32 serial executions, each $n$ cycles.
3. Ideal time $=\max =7$ cycles (all equal).
4. Efficiency $=7/224=1/32=0.03125=3.125\%$. Why this step? This is the theoretical floor for a 32-thread warp — the "1/32nd of peak" quoted in the parent note.

Verify: General case: if all $k$ paths have equal length, efficiency $=\frac{L}{k\cdot L}=\frac{1}{k}$. With $k=32$: $1/32=0.03125$. ✔

---

Example 5 — Cell C5 (multi-way else if, unequal lengths)

Forecast: Which single path dominates the ideal time? Guess before step 3.

1. Paths taken: all four are present (each type has ≥1 thread), so $k=4$. Why this step? Thread counts (8,10,8,6) tell us which paths are live, not the cost.
2. Diverged time $=20+30+25+5=80$ cycles.
3. Ideal time $=\max (20,30,25,5)=30$ cycles — the exp path dominates. Why this step? If nobody diverged, the longest live path alone sets the clock.
4. Efficiency $=30/80=0.375=37.5\%$.

Verify: $0.375\in [1/4,1]$ since $k=4\Rightarrow$ floor $=1/4=0.25$. Matches the parent note's Example 2 exactly. ✔

---

Example 6 — Cell C6 (loop divergence)

Forecast: The warp finishes when the last thread finishes. Guess: does the total depend on the sum of counts or the max of counts?

1. The loop back-edge is a branch. On each iteration, threads whose $i\ge \text{counts}[idx]$ drop out (masked off) but the warp keeps looping. Why this step? Look at figure s02: the active-lane count shrinks each iteration but the loop cannot exit until the tallest bar (count = 20) is done.
2. Total cycles $=\max \text{counts}=20$ (one cycle per iteration, warp-serialized on the slowest thread). Why this step? The warp is held hostage by its longest-running thread.
3. Useful work done $=\sum \text{counts}=240$ thread-iterations.
4. Utilization $U=\frac{240}{32\times 20}=\frac{240}{640}=0.375=37.5\%$. Why this step? Of the $32\times 20=640$ lane-iterations the hardware could have done, only 240 were real work.

Verify: $U=240/640=0.375$, and $U\le 1$ always since $\sum \text{counts}\le 32\max$. The two short (count-3) threads waste $2\times (20-3)=34$ lane-iterations — a chunk of the loss. ✔

---

Example 7 — Cell C7 (branch vs predication — the limiting comparison)

Forecast: For tiny branches, guess whether predication ever loses.

1. Predicated cost. Both a and b are computed for every thread, unconditionally: $T_{\text{pred}}=T_A+T_B=4+3=7$ cycles, with no branch/mask-stack overhead. Why this step? Predication removes the branch entirely — no divergence stack push/pop.
2. Branch (diverged) cost. Since it diverges half–half: $T_{\text{branch}}=T_A+T_B+O=7+O$, where $O$ is the branch/reconverge overhead ($O>0$). Why this step? Same serialized path sum, plus the cost of managing the divergence stack.
3. Compare. $T_{\text{pred}}=7<7+O=T_{\text{branch}}$. Predication wins by exactly $O$. Why this step? When both paths are short and both would run anyway under divergence, skipping the branch machinery is pure profit.
4. Where predication loses: if one path is long and often not taken (e.g. Example 3's C3 case), branching lets the hardware skip the untaken path entirely; predication would force it to run. Predicate only for short, both-usually-needed paths.

Verify: $T_{\text{pred}}=7$, $T_{\text{branch}}=7+O$ with $O>0\Rightarrow T_{\text{pred}}<T_{\text{branch}}$. For the short-branch case the inequality is strict. ✔ (See 6.2.12-Occupancy-optimization for why removing branches also frees the divergence stack.)

---

Example 8 — Cell C8 (nested ifs → orthogonal paths multiply)

Forecast: How many distinct paths, worst case? 2? 3? 4?

1. Count distinct paths. The outer test splits into 2 groups; each group's inner test splits again. Worst case: $2\times 2=4$ live paths. Why this step? Orthogonal (independent) conditions multiply the path count — nesting is not additive.
2. Diverged time $=p_1+p_2+p_3+p_4=6+8+5+7=26$ cycles. Why this step? Four serialized paths, one after another.
3. Ideal time $=\max (6,8,5,7)=8$ cycles.
4. Efficiency $=8/26=0.3077=30.8\%$.

Verify: With $k=4$, floor $=1/4=0.25$; $0.3077\in [0.25,1]$. The naive "one extra branch → 3 paths" undercounts; the real $k=4$ makes it worse. ✔

---

Example 9 — Cell C9 (real-world: ray-tracing materials)

Forecast: Guess whether sorting can get us to 100%.

1. As-is, paths live: $k=4$, costs $\{12,40,60,4\}$. Why this step? Every material present ⇒ every path serialized.
2. Diverged time $=12+40+60+4=116$ cycles; ideal $=\max =60$.
3. Efficiency (a) $=60/116=0.5172=51.7\%$.
4. After sorting: a warp now holds one material only ⇒ $k=1$ ⇒ diverged $=$ ideal. Efficiency (b) $=60/60=1.00=100\%$ for the all-glass warp (and 100% for every uniform warp). Why this step? Sorting is the C4→C3 collapse: bucket similar work to warp size, exactly the fix in 9.3.5-Parallel-algorithmsdesign and 10.1.3-CUDA-optimization-patterns.

Verify: (a) $60/116=0.51724\dots$; (b) any single-path warp gives $\max /\sum =1$. Sorting nearly doubles throughput here ($0.517\to 1.0$). ✔

---

Example 10 — Cell C10 (exam twist: re-align to warp boundary)

Forecast: idx % 2 splits inside every warp. Guess (a) before computing.

1. As-is: in any warp, even and odd lanes are both present ⇒ both paths live, $k=2$. Why this step? idx % 2 alternates within the warp — guaranteed divergence.
2. Diverged $=10+14=24$; ideal $=\max (10,14)=14$. Efficiency (a) $=14/24=0.5833=58.3\%$.
3. Rewrite: (idx/32)%2 is constant across all 32 lanes of a warp (they share the same idx/32). So a warp is entirely X or entirely Y ⇒ $k=1$. Why this step? Aligning the branch key to the warp granularity kills intra-warp divergence — the core mitigation from 6.2.10-Memory-coalescing's sibling idea (group by 32).
4. Efficiency (b): a pure-X warp $=10/10=100\%$; a pure-Y warp $=14/14=100\%$.

Verify: (a) $14/24=0.58333\dots \in [0.5,1]$. (b) single-path ⇒ 1.0. Re-alignment lifts efficiency from 58.3% to 100%. ✔

---

Recall Quick self-test (reveal answers)

Two paths, 5 and 5 cycles, half–half. Diverged time? ::: $5+5=10$ cycles. …and its efficiency? ::: $\max /\sum =5/10=50\%$. One thread on a 90-cyc path, 31 on a 10-cyc path — cost? ::: $90+10=100$ cycles (not amortised). All 32 threads take the same 8-cyc path — efficiency? ::: $8/8=100\%$ ($k=1$). Worst-case efficiency for a 32-thread warp with equal paths? ::: $1/32\approx 3.125\%$. Loop with $\sum \text{counts}=240,\max =20$ — utilization? ::: $240/(32\cdot 20)=37.5\%$.