TL;DR: Divergence occurs when threads within a warp need different control-flow paths. Different active masks can waste lane capacity, but instruction counts alone do not give runtime. In a toy case, grouping 32 expensive items among 1,024 items reduces modeled issued path slots from 3,360 to 255. Sorting, memory access and dependencies decide whether the real kernel improves.
How to approach it
A warp groups 32 threads; its active mask identifies which lanes participate in an instruction. Compare the same items under two assignments to those lanes. Separate lane efficiency from wall-clock speed. Find the costly source region in a profile and include any regrouping operation in the proposed fix.
A strong answer
A branch handles a rare expensive case. Only one item in 32 needs it, yet every warp contains one such item. The rare case is rare across data but common across warps. GPU Execution Model explains the 32-thread grouping behind this distinction.
When different lanes need different instructions, the hardware executes work for the relevant active lanes. Masked lanes contribute no useful result to that instruction. Modern independent thread scheduling changes execution details and synchronization requirements; it does not turn one warp into 32 independent full-width issue resources. See the CUDA SIMT model.
Use a deliberately simplified issue-work model: path A costs 100 equal-cost instruction slots, path B costs five, and both are nonempty in every mixed warp. Ignore memory stalls, branch overhead and all compiler transformations.
one mixed warp: 1 lane takes A; 31 take B
issued path slots = 100 + 5 = 105
useful lane-instructions = 1×100 + 31×5 = 255
available lane slots = 32×105 = 3,360
lane efficiency = 255/3360 = 7.59%
sanity: this is lane-work utilization, not measured GPU utilization.
Across 32 warps there are 32 expensive and 992 cheap items. Grouping the expensive items into one full warp leaves 31 full cheap warps. Useful lane work stays 32×100 + 992×5 = 8,160; issued path slots become 100 + 31×5 = 255 rather than 32×105 = 3,360. The ideal issue-work ratio is about 13.18. It is not a promised 13.18× kernel speedup.
Grouping may require a histogram, prefix sum, permutation and later restoration of original order. It can also improve or damage memory coalescing. If a cheap branch sits inside an otherwise bandwidth-limited kernel, that extra movement may cost more than the saved issue work. Memory-Bound vs Compute-Bound Kernels gives a useful first boundary check, but a profile still has to identify the exposed cost.
| Candidate change | What can reverse the benefit? |
|---|---|
| Bucket items by branch key | Permutation and restoration cost exceed saved work |
| Separate an expensive tail | Extra launch or tiny underfilled kernels |
| Predicate a short branch | Both expressions are costly or unsafe to evaluate |
| Make work warp-uniform | New mapping harms locality or load balance |
Nsight Compute's source-level instruction and active-thread information can locate partially active work. Distinguish valid-lane tails and predication from expensive control-flow divergence. Metric names depend on the tool/device; do not infer branch cost from one global activity threshold. Compare correctness and end-to-end kernel-chain time for the same inputs, including pathological distributions.
I would keep the existing mapping if it is faster after those costs are included. A warp-uniform branch can skip unnecessary work efficiently; removing every conditional is not the goal. A uniform warp may still have different work from its neighbors, causing block or grid imbalance even without within-warp divergence.
What interviewers probe next
- “Do variable-length loops diverge?” Lanes that finish early stop contributing while longer lanes continue. Grouping similar lengths can help, subject to the same movement costs.
- “Did independent thread scheduling fix synchronization?” It enables different execution behavior; it does not validate arbitrary lock-free code or replace required warp synchronization.
- “What if no lane takes A?” The mixed-path sum no longer applies. That warp need not perform the expensive path's useful computation.
Common mistakes
- Calling modeled issue slots measured cycles.
- Comparing different numbers of items before and after grouping.
- Assuming sorting is free or every branch is harmful.
Key takeaways
- The toy mixed warp uses 7.59% of its modeled lane slots.
- Regrouping the same 1,024 items changes 3,360 path slots to 255 before overhead.
- Correctness, locality and complete runtime decide whether to keep the change.