3.2–3.3Two- & Three-Loop Approximation: Scoreboard, Operand Collector, Replay

3.2 Two-Loop Approximation

The one-loop core has a blind spot: its scheduler knows only each warp’s thread IDs and next PC. It cannot know whether the next instruction depends on one still in flight — so a warp can’t issue again until its previous instruction completes, and hiding latency takes lots of warps. The fix is to fetch first, ask questions later: instructions land in a per-warp instruction bufferinstruction buffer (I-buffer)Per-warp staging storage after fetch/decode enabling a second scheduling loop and I-cache miss hiding.Glossary → after I-cache access, and a second scheduling loop picks issue-ready instructions from it. (The I-buffer also hides instruction-cache miss latency, teaming up with instruction MSHRsMSHRMiss-status holding register: tracks an outstanding cache miss so further misses to the same line merge instead of replaying to memory.Glossary →.)

Ready means no data hazards — and detecting those cheaply at GPU scale is its own puzzle. Reservation stations need associative logic (area, energy: no). A CDC-6600-style out-of-order scoreboardscoreboard (GPU)Coon et al. design: 3–4 entries/warp of pending destination registers; instructions carry a dependency bit-vector cleared on writeback, issue when all-zero.Glossary → is complex (no). Even the humble single-bit-per-register in-order CPU scoreboard explodes here: up to 128 registers × 64 warps = 8,192 bits, and if every waiting warp probed its operands each cycle you’d need up to 256 read ports. GPUs instead use Coon et al.’s design — a handful of entries per warp and a bit-vector per buffered instruction. Step through it:

w0 scoreboard entries: [ r7 ] [ -- ] [ -- ]

So the two-loop core: loop 1 picks a warp with I-buffer space and fetches; loop 2 picks a buffered instruction with a clear dependency vector and issues it.

3.3 Three-Loop Approximation

To switch warps every cycle, every warp needs its registers live in hardware — recent NVIDIA parts carry 256 KB of register file per core. SRAM area scales with port count, so the register file is built from single-ported banks that fake multi-portedness. The catch: two operands in the same bank can’t be read in the same cycle — a bank conflictregister bank conflictTwo needed operands living in the same single-ported bank, serializing their reads.Glossary →. Watch the naive design (banks → crossbar → per-instruction staging registers, Fig 3.12; naive layout where every warp’s r0 sits in bank 0, Fig 3.13) struggle with just three instructions:

i1:  mad  r2 ← r5, r4, r6     (banks: r2→2, r5→1, r4→0, r6→2)
i2:  add  r5 ← r5, r1         (banks: r5→1, r1→1  — both in bank 1!)
issue: cycle 0 w3:i1 · cycle 1 w0:i2 · cycle 4 w1:i2

Six cycles, three instructions, mostly idle banks. (The layouts, concretely: naive puts every warp’s r0 in bank 0 —

— the swizzle rotates each warp’s mapping by its warp id.)

The industry answer is the operand collectoroperand collectorCollector units buffering each instruction's source operands so an arbiter can overlap reads across banked register files; the third scheduling loop.Glossary → — the third scheduling loop. Staging registers become collector units: each issuing instruction is allocated one, with buffer space for all its source operands.

Pair that with a smarter swizzled layoutswizzled register layoutOffsetting each warp's registers across banks (w1:r0→bank1) so equal-progress warps hit different banks.Glossary → (Fig 3.16): warp w’s register r goes to bank (r + w) mod 4, so equal-progress warps (hello, round-robin scheduling) touch different banks for the same register name — and one warp’s writeback stops colliding with its neighbors’ reads:

i1:  add  r1 ← r2, r5
i2:  mad  r4 ← r3, r7, r1
issue: c0 w1:i1 · c1 w2:i1 · c2 w3:i1 · c3 w0:i2   (swizzle: wN:rK → bank (K+N) mod 4)

Same six cycles — four instructions serviced, banks working in parallel, one instruction reaching the EU per cycle.

The WAR hazard nobody ordered

The collector imposes no order between instructions leaving it. If a younger same-warp instruction writes a register an older, conflict-stalled instruction hasn’t read yet — silent corruption (write-after-read). Candidate fixes, in increasing cleverness (Mishkin et al.): force program order out of the collector; a release-on-commit warpboard (one instruction in flight per warp — up to ~2× slowdown); a release-on-read warpboard (one collecting instruction per warp — ≤10% cost); or a bloomboard — a small Bloom filter tracking outstanding reads (~few %). And recall from §2.2: Maxwell’s control instructions carry a “read dependency barrier” — NVIDIA’s production answer to the same hazard.

3.3.2 Instruction replay: structural hazards without stalls

What if an instruction hits a structural hazard — collector units exhausted, or a memory access that must be split into multiple operations? A CPU would stall younger instructions. In a GPU, distributing a stall signal across a huge register file and deep graphics pipeline hurts the critical path (or costs buffering), and a stalled instruction from one warp can block other warps that wanted an unrelated resource. GPUs choose instruction replayinstruction replayRe-executing an instruction from the I-buffer on structural hazard instead of stalling the pipeline.Glossary → instead: keep the instruction in the I-buffer until it’s known complete (or all its pieces have executed), and simply re-issue it as needed. No speculation — GPUs avoid that on principle — just retry as a throughput-friendly alternative to stalling.