Issue-Limited Kernels and the Cost of Divergence

Above the ridge point of the roofline the memory system has slack and the instruction stream is the limit. In that regime the runtime is the number of issued warp-instructions divided by the rate at which the schedulers can issue them, and the only ways to go faster are to issue fewer instructions or to issue them from more schedulers. Divergence is the mechanism that silently multiplies the instruction count.

The issue ceiling

A multiprocessor has a fixed number of warp schedulers, each able to issue one warp-instruction per cycle. With $S$ schedulers and a clock of $f$, the ceiling is $S \cdot f$ warp-instructions per second. Each warp-instruction executes for up to 32 threads, so the thread-level ceiling is $32 \cdot S \cdot f$ thread-instructions per second, but only if all 32 threads are doing the same thing.

This ceiling is independent of the memory system and independent of occupancy, provided enough warps are resident to keep the schedulers fed. A kernel at this ceiling has an IPC of one per scheduler, and adding warps changes nothing. The relevant question becomes what fraction of issued instructions do useful work.

Divergence is where that fraction falls. When threads within a warp take different paths through a branch, the hardware cannot issue different instructions to different threads in the same cycle. It executes the paths serially, with the inactive threads masked off, and reconverges afterwards. A branch with two sides each taken by half the warp therefore costs the sum of both sides’ instruction counts, not the average.

Quantifying the multiplication

Let a divergent region have $k$ paths with instruction counts $c_1 \ldots c_k$ and thread fractions $p_1 \ldots p_k$ summing to one. The warp executes $\sum c_i$ instructions. The useful work, measured as thread-instructions, is $\sum p_i c_i \cdot 32$. The efficiency of the region is

$$ E = \frac{\sum p_i c_i}{\sum c_i} $$

For the even two-way split with equal path lengths, $E = 0.5$. For an eight-way split, $E = 0.125$. For a branch where 31 of 32 threads take a short path and one takes a long one, the efficiency depends on the path lengths: if the long path is ten times the short one, the warp spends most of its instructions on one thread.

The efficiency is the fraction of issue slots doing work that some thread needed. It is not the fraction of threads active, which is a different and less useful figure: 31 of 32 threads active on an instruction is fine, while one of 32 threads active on a long path is not.

A common special case is the boundary branch. A loop with if (i < n) where only the last warp is partially in range diverges once per launch, and the cost is the loop body executed for the warp with most threads masked. That is a fixed cost proportional to one iteration per boundary warp, which for a large array is negligible. Divergence matters when it occurs inside the hot loop, not at the edges.

What the counters show

Two counters separate the issue-limited case from the memory-limited one, and a third separates divergence from other instruction overhead.

The first is the issued instruction count per thread, often reported as instructions per warp or as a ratio to the source-level operation count. A kernel issuing several times the instructions its arithmetic requires is either unrolled with overhead, running a loop with poor induction-variable handling, or divergent.

The second is the achieved IPC against the scheduler ceiling. At the ceiling, the kernel is issue limited. Below it, the schedulers are idle and the stall histogram from warp stall attribution explains why.

The third is the ratio of executed warp-instructions to the number of warp-instructions that would have been issued with no divergence, sometimes called the branch efficiency or predication efficiency. It is the $E$ above, measured rather than computed, and it isolates the divergence contribution from the rest of the instruction overhead.

// Divergent: half the warp idles through each side.
if (x[i] > 0.0f) {
    y[i] = sqrtf(x[i]);
} else {
    y[i] = 0.0f;
}

In this shape, both sides are short, and the cost of executing both is roughly the cost of the two together. If the branch is predictable at the data level, most warps take one side uniformly and the cost vanishes. If the data are random, every warp diverges and the cost is the full sum. Whether a given kernel suffers depends on the data distribution, which is why a microbenchmark with sorted input can show no divergence cost at all.

Predication as an alternative

For short branches the compiler can avoid divergence entirely by predicating: it emits the instructions from both paths and masks the writes, so every thread executes every instruction but only the relevant results are stored. The warp does not branch, so there is no serialization, and the cost is that the instructions from the untaken path are issued anyway.

The trade between predication and branching is a trade between issuing both paths always and issuing them serially when the warp diverges. If the paths are short and divergence is common, predication is better. If the paths are long and divergence is rare, branching is better because most warps skip the untaken path entirely. The compiler chooses based on a threshold on the path length, and the choice is not always the right one; a #pragma unroll or a restructure can change it, but the reliable method is to measure the instruction count both ways.

The important observation is that predication does not reduce the instruction count for a divergent warp. It reduces the serialization. The issue slots consumed are the same or worse, but the latency is lower because the paths are not serialized. A kernel that is issue limited gains nothing from predication; a kernel that is latency limited by serialization gains.

Restructuring to remove divergence

When the divergent region is expensive, the fix is usually to make the data uniform per warp rather than to make the code branchless.

Sort or partition the data so that threads in a warp share the same path. A compaction pass that groups elements by which branch they take converts random divergence into uniform execution. The cost is the pass itself, which is a memory-bound operation, so the trade is worthwhile only if the divergent region is expensive enough.

Assign work by index arithmetic rather than by branching. A kernel that computes two outputs per thread and branches on whether the second is needed can instead launch a grid sized to the exact output count, eliminating the branch. This is the same observation as the boundary-branch case: a branch that only separates in-range from out-of-range work is better replaced by a grid that contains no out-of-range work.

Hoist the branch out of the loop. If a branch condition is loop-invariant, executing the whole loop under the branch costs the sum of both loops; executing the branch inside costs the sum per iteration. Neither is free, but the hoisted version at least allows warps that agree to skip entirely.

Use warp-level primitives to reduce divergence in reductions. A block reduction with a tree in shared memory has all threads executing the same code with index-dependent participation, which the hardware handles with predication and which costs one instruction per level regardless. A shuffle-based reduction does the same in registers with no shared-memory traffic.

The instruction mix beyond divergence

An issue-limited kernel can also be slow because its instructions are of an expensive kind. Special-function units, which compute reciprocals, square roots, and transcendental functions, run at a fraction of the rate of the main arithmetic pipes. A kernel whose loop body is dominated by such operations is limited by that unit’s throughput, not by the schedulers’ issue rate, and the counter to look at is the dispatch stall category.

The mitigations are algorithmic. A reciprocal square root can be replaced by an approximation refined with one Newton step, trading instructions on the fast pipe for instructions on the slow one. A division by a loop-invariant value can be turned into a multiply by its reciprocal, computed once. A transcendental evaluated per element can sometimes be evaluated per tile with interpolation, trading accuracy for throughput. Each is a trade of accuracy or code complexity for issue slots, and the acceptable point is set by the application’s error tolerance, not by the hardware.

There is also the instruction-level question of dual issue. Some architectures can issue more than one instruction per scheduler per cycle when the instructions are of different kinds and independent. A kernel with a long dependency chain cannot use that capability regardless of its mix, because the second instruction has nothing to pair with. This is the same dependency problem as in memory-level parallelism, appearing on the arithmetic side rather than the memory side.

Deciding which regime applies

The decision procedure is short and should be run before any tuning.

Compute the kernel’s arithmetic intensity from counter bytes and compare it to the ridge point of the roofline. Below the ridge, the memory system is the constraint and instruction-level work is wasted effort. Above the ridge, the instruction stream is the constraint.

For kernels above the ridge, check whether the schedulers are issuing every cycle. If they are, the kernel is at the issue ceiling and the only lever is fewer or cheaper instructions, which is where divergence accounting and the special-function trade apply. If they are not, the kernel is issue limited only in the sense that it could issue more, and the stall histogram says what is preventing it.

For kernels below the ridge, the divergence analysis is still worth doing if the divergent region also generates memory traffic, since the two effects compound: a warp that executes both paths may issue twice the loads. But the fix priority is memory first, and the instruction-count reductions are a secondary gain.