5.1.2–5.1.4Cycle-by-Cycle, Multi-Kernel & Sync-Aware Scheduling

5.1.2 Cycle-by-cycle scheduling research

Early characterization (Lakshminarayana & Kim, on cache-less GPUs with regular workloads): fairness-oriented warp+DRAM scheduling wins — equal progress merges requests and feeds row-buffer locality — while SMT-style ICOUNT (prioritize the fastest warp) does not help. Two-level schedulers refined this: Gebhart et al.’s active pool cuts selection energy (the RFC companion), while Narasiman et al.’s fetch groupsfetch groupSubset of warps a two-level scheduler rotates through, letting groups reach long-latency ops at different times to preserve locality.Glossary → stagger groups’ arrival at long-latency ops so one group’s misses hide behind another’s compute.

Then came the locality revolution. Rogers et al. measured that cache-sensitive kernels live and die by intra-warp localityintra-warp localityA warp reloading data it itself brought in; the dominant locality in cache-sensitive GPU kernels (vs inter-warp sharing).Glossary → — warps reloading their own data — and built CCWSCCWSCache-conscious wavefront scheduling: throttle actively-scheduled warps when victim-tag hits show intra-warp locality being lost to cache thrashing.Glossary → around a feedback loop:

The follow-up, DAWSDAWSDivergence-aware warp scheduling: predict each warp's LOOP cache footprint (shrinking as threads exit) and throttle preemptively.Glossary →, replaces reaction with prediction: most intra-warp locality lives in loops, so estimate each warp’s loop footprint (shrinking as threads diverge out of the loop — divergence-aware) and throttle before the thrashing starts. Programmability payoff: naive cache-reliant code approaches a shared-memory-optimized version of itself.

The two-level skeleton spawned more variants: prefetching-aware scheduling (Jog et al.) builds fetch groups from non-consecutive warps — consecutive warps’ addresses hit the same DRAM bank, so spacing them out buys bank-level parallelism, and cross-group prefetching restores row locality; CTA-aware scheduling (Jog et al.) groups by threadblock and adds throttling + inter-CTA page locality + prefetching. Scheduling also interacts with the divergence machinery: DWS’s cache-hit run-ahead is itself a prefetching effect, DWF ships with five candidate schedulers, and TBC’s block prioritization is two-level scheduling with CTAs for fetch groups.

MascarMascar / owner warpWhen MSHRs/miss queues saturate, one owner warp keeps memory priority while others' compute overlaps; EP↔MAP mode switch.Glossary → (Sethia et al.) attacks memory-intensive kernels, where the LSU sits stalled on back-pressure while ready data rots in the L1: in MAP mode (entered when MSHRsMSHRMiss-status holding register: tracks an outstanding cache miss so further misses to the same line merge instead of replaying to memory.Glossary →/miss queues near saturation) a single owner warp monopolizes memory issue — everyone else’s compute overlaps its accesses — and a cache-access re-executioncache access re-execution (CAR)Side buffer for stalled memory instructions so hits-under-miss can proceed past a backed-up load/store unit.Glossary → queue parks stalled memory instructions so hits-under-miss slip past the clogged LSU. (Non-owner CAR requests that miss are re-queued rather than sent to L2.)

5.1.3 Scheduling multiple kernels

With Streams and Hyper-Q making concurrent kernels real, preemption stops being optional — but CTA state is huge (§5.1). ChimeraChimeraGPU preemption picking per-CTA among context save, drain-to-finish, or idempotent restart to hit a context-switch latency target.Glossary → (Park et al.) picks per-CTA among save/restore, drain, and — the clever one — idempotent restartidempotent restartDropping a CTA without saving state because re-executing it from the start is provably safe (relaxed idempotence).Glossary →: if execution has been idempotent since thread start (a deliberately relaxed test), just drop the CTA and re-run it later. An estimator chooses victims to meet a user-specified switch-latency target at minimum throughput cost.

5.1.4 Fine-grain synchronization-aware scheduling

On real hardware, spin locks burn cycles — and naive “back off the spinners” can starve a lock-holder in the same warp (stack-based reconvergence again — old friend). ElTantawy & Aamodt detect spinning dynamically — a path history of PC bits plus a predicate- update history identifies spin loops — then deprioritize spinning warps right after their backward branch, once any in-warp lock-holders have released: 1.5× performance, 1.6× energy vs. prior warp-limiting.