3.4.2Research: Intra-Warp Divergent Path Management

Where §3.4.1 merged threads across warps, this family keeps each warp intact and improves how its own divergent paths are handled — on two axes: run the paths concurrently (multi-path parallelism), and rejoin them earlier (better convergence).

Multi-path parallelism

After a divergent branch, a warp’s threads form warp splitswarp splitSubset of a warp's threads sharing a PC after divergence; the schedulable unit in stackless/multi-path designs.Glossary → — one per target. The baseline stack runs them one-at-a-time, but nothing about correctness requires that: threads in a warp only communicate explicitly (memory, barriers), so splits may freely interleave, just as different warps do. Interleaving doesn’t put more lanes to work — it recovers thread-level parallelism to hide memory latency. Watch the same divergent kernel (both paths contain a load) run both ways:

The proposals, in escalating generality:

• Dynamic Warp Subdivision (Meng et al.): a warp-split table beside the stack; splits run concurrently. DWS even splits at memory divergence (some threads hit L1, some miss) — the hitters run ahead, effectively prefetching for the missers.
• Dual-Path Execution (Rhu & Erez): cap it at two concurrent splits (the two at the TOS entry) — one extra PC + mask, a per-path scoreboard extension, and most of DWS’s benefit at a fraction of the complexity.
• Multi-Path executionmulti-path executionLetting multiple warp-splits of one warp interleave (DWS, dual-path, MPM) to recover TLP during divergence.Glossary → (MPM, ElTantawy et al.): drop the stack entirely for a warp-split table + reconvergence table. Any split may issue until its PC equals its RPC; arrivals accumulate in the reconvergence entry, which retires into a merged split when everyone’s in. A careful scoreboard extension tracks dependences per split without duplicating the whole scoreboard per thread. (Sound familiar? Volta’s convergence barriers are an industrial cousin.)

Better convergence

The immediate post-dominator is the earliest guaranteed reconvergence point — but not always the earliest practical one. The classic case is a loop with a rare break: the IPDOM sits after the loop, yet in the common case threads meet again at the loop’s increment. (The book credits this observation for NVIDIA’s break instruction.) Likely convergence pointslikely convergence pointsExtra stack fields (LPC/LPos) capturing probable early reconvergence (e.g. before loop breaks) ahead of the IPDOM.Glossary → (Fung & Aamodt) extend each stack entry with two fields — LPC and LPos — and give divergent branches a speculative-but-safe early meeting point:

PC  RPC  LPC  LPos  Act.Thd.
F    --   --   --    1234
E    F    --   --    (empty)   ← LPC entry
B    F    E    1     1
C    F    E    1     234   ← TOS

Two stack-free alternatives round out the axis:

• Thread frontiersthread frontiersPer-thread PCs + topologically sorted code; always run the lowest-PC threads so laggards catch up — no stack needed.Glossary → (Diamos et al.): the compiler sorts basic blocks topologically so control only flows “downward”; each thread keeps its own PC in the register file; the hardware always executes the warp’s lowest-PC threads (the frontier), so everyone ahead implicitly waits. Especially strong for unstructured control flow (multi-expression conditionals, exceptions), and with no fixed budget of convergence points — where the LCP stack fields cap out.
• Opportunistic Early Reconvergence (OREC, in MPM): at a divergent branch, if a warp-split with the same PC and RPC already exists in the table, create an early reconvergence entry and merge with it — capturing unstructured-control-flow reconvergence without any compiler help.