3.4–3.4.1Research: Warp Compaction

(§3.4 draws on Wilson Fung’s Ph.D. dissertation.) The baseline SIMT stack is correct for nearly all GPU code — and the research community has spent a decade attacking its four weak spots:

1. Lower SIMD efficiencySIMD efficiencyFraction of SIMD lanes doing useful work; divergence's main casualty.Glossary → — serialized paths idle lanes;
2. Needless serialization — interleaving divergent paths is functionally fine (threads only communicate explicitly), the stack just forbids it;
3. Inadequate MIMD abstraction — implicit reconvergence sync collides with locks (SIMT deadlock) and with exceptions/ interrupts;
4. Area — 32×64 bits per warp (or 6×64 optimized) scaling with every in-flight warp, mostly unused when divergence is rare.

The proposals fall into four families — warp compactionwarp compactionResearch family merging threads scattered across diverged static warps into denser dynamic warps (DWF, TBC, LWM, CAPRI…).Glossary → (this page), intra-warp path management (§3.4.2), MIMD capability (§3.4.3), and complexity-effective designs (§3.4.4).

3.4.1 Warp Compaction

The observation: a core runs hundreds to thousands of threads from the same kernel, so when one warp diverges at a data-dependent branch, its neighbors probably diverge at the same branch — each branch target is executed by plenty of threads, just scattered across static warps (the hardware’s arbitrary, program-invisible grouping at launch). Why not regroup?

Dynamic Warp Formationdynamic warp formation (DWF)Compacting same-PC threads from different warps into new warps at divergence; sensitive to scheduling, breaks implicit warp sync.Glossary → (Fung et al.) does exactly that — at a divergent branch, same-PC threads from different warps are compacted into new dynamic warps:

A significant slice of MIMD’s benefit on SIMD hardware — with strings attached. DWF needs warps to reach the branch within a short window (scheduler-sensitive); a greedy scheduler can starve threads; regrouping threads scrambles memory coalescing and shared-memory bank behavior; and code relying on implicit intra-warp synchronization simply breaks. The follow-up insight: split the kernel into divergent and coherent regions, compacting in the former and restoring static warps in the latter — which matured into:

• Thread Block Compactionthread block compaction (TBC)Block-wide SIMT stack: compaction only at divergence/reconvergence, warps of other blocks keep the core busy.Glossary → (Fung & Aamodt): continuous regrouping is pointless — compact only at divergent branches and reconvergence points, tracked by a block-wide SIMT stack. Synchronizing a whole thread block at each divergent branch costs TLP, so TBC’s compromise is scope (one block, while other resident blocks keep the core busy). Robust where DWF was fragile.
• Large Warp Microarchitecture (Narasiman et al.): gang warps into large lockstep groups and compact every instruction (even predicated ones) — more compaction, less TLP, plus a thread-granularity scoreboard letting some warps run slightly ahead.
• CAPRI (Rhu & Erez): TBC + a compaction-adequacy predictor — a simple history-based predictor (think single-level branch predictor) that skips the stall-and-compact dance at branches where compaction wouldn’t pay.
• Cycle compression (Vaidya et al.): when the SIMD datapath is narrower than the warp (e.g. 16-wide hardware, 32-wide warps → 2 cycles/warp), skip fully-masked sub-groups; the swizzled variant re-arranges lanes to manufacture skippable sub-groups.
• SBI/SWI (Brunie et al.): widen the warp, issue two different instructions per cycle, and fill divergence gaps with the sibling path (SBI) or another diverged warp (SWI).

The lane constraint. Compaction has a physical limit: a thread’s registers live in its lane’s register-file slice, so a dynamic warp can only merge threads whose lanes don’t collide (our animation chose masks that interleave perfectly — reality is less kind). Program structure biases paths to particular lanes; Rhu & Erez’s SIMD lane permutation picks thread→lane mappings that break the bias and substantially improve compaction rates. Alternatively, a more flexible register file (more, narrower banks — Fung et al.) lets compaction ignore lanes; and dynamic micro-kernels (Steffen & Zambreno) migrate thread state outright through the scratchpad for ray tracing loops.

Software compaction gets the same effect without new hardware, paying in memory traffic: conditional streams for stream processors (Kapasi et al.), prefix-sum stream compaction on the scratchpad (Billeter et al.), deferred shading grouping rays by material (Hoberock et al.), CPU-side runtime remapping (Zhang et al.), and CCC (Khorasani et al.) — a compiler transform where each warp parks divergent tasks on a shared-memory stack and refills idle threads from it.