Active-Mask Accounting and Issue Slot Efficiency

A streaming multiprocessor’s datapath is a fixed width, and the scheduler feeds it one warp instruction per cycle per scheduler. Whether the instruction carries thirty-two useful lane results or one is not a property the datapath can change. So the quantity that limits a divergent kernel is not the number of threads launched but the number of warp instructions issued, and the efficiency of the machine is the ratio between useful lane-work and issued slots.

That ratio is computable from the masks alone, without any timing measurement. Doing the arithmetic is the fastest way to see whether a kernel’s divergence matters and, if it does, which construct is responsible.

Two counters, one ratio

Define, for a single warp over its whole execution, I as the number of warp instructions issued and A_j as the number of active lanes during instruction j. Useful lane-work is the sum of A_j, and issue slots consumed is 32·I in lane-equivalents. The efficiency of that warp is

efficiency = (Σ_j A_j) / (32 · I)

A fully converged warp that never masks a lane has efficiency 1. A warp that executes an if/else with a 16/16 split over paths of one instruction each issues the compare, the true path, the false path, and the join: four instructions, with masks 32, 16, 16, 32. The sum is 96 over 128 lane-slots, so efficiency is 0.75. If the paths are ten instructions each, the sum is 32 + 160 + 160 + 32 = 384 over 22 instructions × 32 = 704, and efficiency is about 0.55.

Two features of this arithmetic are worth extracting. First, the compare and the join instructions are paid at full mask, so short divergent regions are dominated by their own overhead: the ratio for one-instruction paths is 0.75 while the paths themselves are at 0.5. Second, efficiency falls toward 0.5, not toward 0, for a two-way split: the worst case for a binary branch is half the lane capacity, because the total work is fixed and only the serialization is added. Efficiency approaches 1/n for an n-way split, and n-way splits arise from switch statements and from nested conditionals, which is why nesting is expensive in a way that a single branch is not.

The complement is also useful. The wasted fraction 1 - efficiency is the share of datapath cycles spent on lanes that produce nothing. For a warp at 0.55, roughly 45 percent of the lane capacity that the scheduler allocated to it was discarded.

Why issue slots, not lanes, are the binding resource

The scheduler selects one warp per cycle. It cannot issue half a warp or combine the useful halves of two partially masked warps into one instruction. Not in the baseline model, at least, and the research on dynamic warp formation exists precisely because that restriction wastes capacity. When a partially masked warp is selected, the cycle’s datapath is spent and the other resident warps wait their turn.

The consequence is that a divergent kernel and a converged kernel with the same thread count can differ in throughput by a factor equal to the reciprocal of the efficiency, even though both launch the same number of warps and use the same number of registers. The divergence does not reduce the number of warps needed; it increases the number of issue slots each warp consumes, so the same work takes longer at the same occupancy.

There is a partial mitigation that the hardware provides for free: other warps. Because the scheduler picks among ready warps each cycle, a partially masked warp’s wasted capacity does not stall the machine as long as another warp is ready with a fuller mask. Divergence therefore costs throughput in proportion to how much spare warp-level parallelism exists. A kernel with high occupancy and moderate divergence can be fully hidden; a kernel at low occupancy cannot. This coupling is why the occupancy model in what occupancy actually counts and the efficiency model here must be applied together.

Computing efficiency for a real kernel

The masks are not directly observable from source, but the structure that produces them is. For each divergent construct, the efficiency contribution can be estimated from the branch probability and the path lengths.

Take a kernel that classifies input values into three categories with a chain of comparisons, then does a different amount of work in each. Suppose the categories split the lanes 40/40/20 and the work is 2, 6, and 20 instructions respectively. The warp executes all three regions, each with its own mask:

region        mask   instructions   lane-work
compare 1      32          1             32
cat A           13         2             26
compare 2      19          1             19
cat B           13         6             78
cat C            6        20            120
join           32          1             32
total                      31            307
efficiency = 307 / (31 * 32) = 0.31

The 20-instruction region carrying a 6-lane mask is the dominant cost: 120 of the 307 lane-work units and 20 of the 31 issued instructions. Rewriting that region so it is reached only by warps that are mostly in that category, or so its work is distributed across lanes, would move efficiency toward 0.6 without changing the total useful work at all.

The same arithmetic applied to a switch with many small cases shows why the compiler often converts a switch into a jump table plus predication, or into a sequence of selects: each additional case adds an issued instruction with a smaller mask, so a k-way switch approaches efficiency 1/k even when each case does a single instruction.

Mask width is not the same as memory efficiency

A natural mistake is to assume that a warp with a half-full mask generates half the memory traffic. It generates traffic in proportion to the number of distinct addresses the active lanes touch, which is usually proportional to the mask but not always, and the transaction count is what matters.

A predicated load with sixteen active lanes covering consecutive addresses produces one transaction if the addresses fall in one cache line. The same load with sixteen active lanes scattered across sixteen lines produces sixteen transactions. In the first case the mask reduction halves the bytes transferred but not the transactions; in the second it may reduce neither. Because transactions are the unit the memory system charges for, the cost of a partially masked access depends on the address distribution of the active lanes, not on how many there are.

The coalescing rules themselves belong to the memory hierarchy, but the interaction with divergence is a property of this model: divergence narrows masks, narrowed masks change which addresses are grouped, and grouping determines transactions. A branch that splits a warp’s addresses into two distant regions can double the transaction count for the same total bytes, which is the memory-side analogue of the issue-slot loss.

The masks that never diverge and the ones that always do

Some masks are known at compile time and some are not, and the distinction determines whether the cost is structural or data-dependent.

A mask determined by threadIdx alone (a guard on the last warp of a block, a lane predicate for a warp-level primitive, a boundary check against a constant) is fixed for the launch. The compiler can reason about it, and the hardware will see the same pattern in every warp. These are cheap because they are predictable and because they are usually all-ones or all-zeros for most warps.

A mask determined by loaded data is unpredictable and potentially different in every warp. It is also the case where efficiency can be improved by changing the data layout: sorting, binning, or partitioning inputs so that lanes within a warp share a category converts a data-dependent mask into a nearly uniform one. This is the mechanism behind compaction and work-queue designs, where each lane pulls the next work item rather than processing a fixed index, so the amount of work per lane is balanced by construction rather than by luck. The cost moves to the queue itself, which must be contended for.

The costliest mask, and the one most often avoidable, is the one produced by a loop whose trip count varies per lane. A warp that runs for its longest lane’s count, with the short lanes masked off, has efficiency equal to the mean trip count divided by the maximum, a ratio that degrades without bound as the variance grows. Equalizing trip counts, by padding, by tiling, or by flattening the variable work into a shared queue, is the highest-leverage change available in this model.

Where the model stops

The efficiency ratio above assumes every issued instruction costs the same and that the scheduler always has another ready warp. Neither holds in general. Instructions differ in latency and in which functional unit they occupy, so a partially masked instruction on a full-throughput ALU path costs less in opportunity than one on a scarce special-function unit. And when no other warp is ready, the wasted capacity is genuinely lost rather than displaced.

The ratio also ignores the reconvergence overhead, which on architectures with per-lane program counters can be larger than the strict serialization model suggests, because lanes may need explicit synchronization before warp-level primitives. That is a property of the scheduling model treated in independent thread scheduling, and it is the main reason the simple mask arithmetic underestimates the cost of divergence on those architectures.

Used within those limits, the accounting is still the right first calculation: it converts a vague concern about divergence into a number that can be compared against the cost of the restructuring that would remove it. Warp specialization, described in warp specialization and producer-consumer warps, is one restructuring that changes the masks by changing which warps run which code, and it is worth evaluating in exactly these terms.