Divergence Amplification in Nested Control Flow

Two independent two-way branches in sequence cost at most four serialized phases between them, two per branch, and if their conditions are independent the warp’s lanes end up spread across four groups. The cost of executing all four groups is not four times the cost of one branch. It is the sum of the four paths’ lengths plus the overhead of the branch instructions, and the fraction of the warp’s lane capacity that each group represents shrinks as the groups multiply. This is the arithmetic that makes nested and sequential conditionals cost more than their instruction counts suggest, and it is worth stating precisely because intuition tends to underestimate it.

The mechanism is the same mask stack as always. What changes with depth is the number of distinct masks the warp carries and the fact that the stack must hold them simultaneously.

Path count as a product

Let a region contain n two-way branches, each independently divergent. In the worst case the warp’s lanes distribute across all 2^n combinations of outcomes, and the hardware executes 2^n paths in sequence. The instruction count of the region becomes the sum over all paths of the path length, which for equal-length paths of L instructions is 2^n · L rather than n · L. A region with three independent branches and five instructions after each executes at most eight paths of up to five instructions, or forty issues where a converged warp would need eighteen.

Efficiency, in the accounting of active-mask accounting, falls toward 1/2^n in the worst case, because each path carries roughly a 1/2^n share of the lanes. The bound is not reached in practice for two reasons: not all combinations occur, since conditions are often correlated with each other and with the data, and paths that are empty contribute nothing. But the growth is exponential in the number of independent branch points, and it does not require deep nesting: sequential conditionals compose just as badly as nested ones.

case: three sequential guards, each 50/50, region of 4 instructions after each
paths            4-8 depending on correlation
issues           up to 8 * 4 + 3 compare + 3 join = 38
converged cost   3 * (4 + 1) = 15
efficiency       ~0.26 at the worst case

The important qualitative point is that the cost is superlinear in the number of branch points while the useful work is linear in it. Adding one more independent condition to a region doubles the serialized path count without doubling the work. That is the amplification, and it is why flattening a chain of tests into a single computed classification is often the largest single improvement available to a divergent kernel.

Why the stack depth matters

The reconvergence stack holds one entry per live divergence point, and its depth is a hardware constant: small, and not part of the programming model’s contract. Source nesting depth is a poor guide to how many entries are live, because what the hardware counts is distinct reconvergence points outstanding at an instruction, not braces.

Compilers therefore lower deeply nested or irregular control flow into shapes that keep few points live at once, and the shapes have a characteristic form: the divergence is hoisted to a single point and the decision is encoded in data rather than in the program counter. A switch with many cases becomes a jump table indexed by a computed value, or a sequence of predicated selects that compute all candidates and choose per lane. Both keep the stack shallow and move the cost to instruction count and register pressure.

This is a case where the compiler’s transformation is visible in the machine code and invisible in the source. Two kernels with identical source structure can compile to different control-flow shapes depending on the compiler’s estimation of the branch probabilities, and the shapes have different divergence costs. The estimation is a heuristic; the source does not record it.

Correlated conditions are the exception that matters

The exponential bound assumes independence. Conditions in real kernels are usually correlated, and the correlation is often a property of the data layout rather than of the computation.

If all lanes in a warp have the same value of the first condition, that branch never diverges and the path count does not double. The second condition then splits the surviving group, and the effective branching factor is one branch point rather than two. Kernels whose tests are ordered by how strongly they correlate with the lane index (testing a block-level or warp-level property first, then a per-lane one) therefore pay far less than the worst case.

The ordering is a source-level decision with a measurable consequence. Testing the cheapest, most uniform condition first means the warp either exits or continues as a group, and the expensive per-lane conditions are evaluated only for the group that survives. Testing the per-lane condition first splits the warp immediately, and every subsequent test is evaluated with a partial mask for each group.

This is also why the two-dimensional case is asymmetric: one condition depends on threadIdx, the other on data. The threadIdx condition is a function of the lane index, so whether it diverges is known at compile time for a given launch configuration. The data condition is not, and the compiler cannot order around it with certainty.

Collapsing the product by construction

Three rearrangements collapse the amplification, and they differ in what they spend.

The first is classification before execution. Rather than a chain of tests inside the divergent region, compute a category index per lane with branchless arithmetic, then dispatch on the index. The dispatch is one divergent point with k paths, so the cost is k serialized regions rather than 2^n. Computing the index branchlessly usually costs a handful of selects and comparisons, executed at full mask. The trade is k paths of predicated arithmetic against 2^n paths of branchy control flow, and it wins whenever k is small and the tests are cheap.

The second is sorting or binning upstream so that lanes within a warp share a category. If every lane in a warp has the same category, the dispatch is uniform and no path is serialized. The sorting cost is paid once per element and is itself a divergent operation if written naively, which is why the binning is usually done with a scan-based compaction that is branchless by design. The result is a kernel whose inner region has no data-dependent divergence at all, at the cost of a permutation of the data and the memory traffic to apply it.

The third is to move the per-lane decision out of the warp entirely by changing the work assignment: instead of one lane per work item, assign one work item per warp for the expensive heterogeneous case, so each warp runs with a full mask on one path. The cost is that the warp’s thirty-two lanes must be used for something, so the technique applies to work items with internal parallelism, such as a per-item loop over lanes. This is a form of warp specialization applied per item rather than per role.

The memory-side amplification

Divergence amplification has a second cost that the issue-slot accounting misses: the transaction count. When the warp’s lanes follow 2^n paths, the addresses issued at each path are a subset of the warp’s addresses, and the subsets are not necessarily contiguous. A load that would have been one coalesced transaction when the full warp reached it becomes m transactions when the warp reaches it in m phases with scattered active lanes.

The effect is bounded by the number of distinct cache lines the warp’s addresses touch, which does not change with divergence: the same total addresses are issued, just in more phases. So the transaction count can rise, but not above the line count. What rises without bound is the number of memory instructions issued, because each phase issues its own load instruction. That is the same issue-slot cost already counted, now visible from the memory side.

The practical implication is that a divergent region containing loads is worse than one containing only arithmetic, because the loads’ cost is paid per phase and their transactions may not coalesce. Restructuring the region so the loads happen before the divergence, with the whole warp active, and only the arithmetic is predicated, is a standard rearrangement and it removes both effects at once.

What remains after the fixes

After classification, binning, and hoisting the memory accesses, the residual divergence is the part that is genuinely data-dependent and genuinely unavoidable: lanes whose work depends on their own data in a way that cannot be grouped. That residue costs what it costs, and the accounting says it is bounded by the ratio of the serialized path sum to the converged instruction count.

Two properties of the residue are worth keeping in view. It does not compound across kernels, so a pipeline of stages each with modest divergence does not multiply its cost: each stage’s warps diverge independently, and the serialization is per warp per stage. And it is not improved by occupancy beyond the point where the scheduler has another ready warp, which is the criterion derived in the warp-count arithmetic. Divergence and occupancy are both issue-slot effects, and the second can mask the first only up to the point where the SM has spare warps to select from.

The model’s overall statement is therefore narrow and useful: divergence costs the sum of distinct path lengths per warp, the number of distinct paths multiplies with independent branch points, and the multiplier is what restructuring attacks. The lanes that share a program counter are the unit of that cost, and nothing about per-lane scheduling or warp specialization changes the arithmetic. They change which lanes share a path, which is the same thing as changing the number of paths.