10.1GPU Consistency and Coherence

This is the age of specialization. A modern server, mobile, or desktop processor carries not just CPUs but a zoo of accelerators — GPUs most prominently, but also DSPs, AI engines, cryptographic units, and FPGAs. Heterogeneity creates a programmability problem: how do threads synchronize and communicate within and across these devices, and how do they do it efficiently? One promising answer is the one this whole book has been about: expose a global shared memory interface across CPUs and accelerators — an intuitive load-store interface for communication, plus programmer-transparent caching for locality.

The devices may be tightly integrated on one chip, actually sharing physical memory (as in mobile SoCs — our default assumption), or may have separate memories with a runtime faking the shared abstraction. Either way, shared memory immediately raises this book’s two questions. What is the consistency model? And how do the caches — within an accelerator, and across CPUs and accelerators — stay coherent?

Figure 10.1 (recreated): a heterogeneous SoC. Each device has per-core (or per-SM) L1s and a device-level L2; all devices share a memory-side LLC — which, per §2.1, poses no extra coherence issues and doubles as the memory controller. We assume it is non-inclusive unless stated otherwise. The dashed boxes are scopes*, defined below — each scope names both a set of threads and the cache level they share.*

This section studies consistency and coherence within an accelerator, focusing on GPUs; §10.2 tackles across devices.

10.1.1 Early GPUs: architecture and programming model

Early GPUs were built for embarrassingly parallel graphics work — computing each display pixel independently. Massive data-parallelism, minimal sharing, rare synchronization. Those workload assumptions shaped everything that follows.

Architecture. A GPU carries tens of cores called Streaming Multiprocessors streaming multiprocessor (sm) A GPU core: highly multithreaded (on the order of a thousand threads), whose threads share its L1 cache and scratchpad. AMD calls it a Compute Unit. defined in Chapter 10 — open in glossary (SMs — AMD says Compute Units), each highly multithreaded: on the order of a thousand threads per SM. Threads mapped to an SM share its L1 cache and a local scratchpad scratchpad Programmer-managed on-SM memory outside the cache hierarchy; integrating scratchpads into the global shared address space remains ongoing research. defined in Chapter 10 — open in glossary memory; all SMs share an L2. To amortize fetch/decode across those threads, the SM runs them in groups called warps warp Group of GPU threads fetched and decoded together, sharing PC and stack, executing SIMT-style under mask bits (AMD: wavefront). Modern GPUs allow the threads independent scheduling. defined in Chapter 10 — open in glossary (AMD: wavefronts): one program counter and stack per warp, with per-thread mask bits selecting who actually executes — Single-Instruction-Multiple-Threads simt Single-Instruction-Multiple-Threads: warp-wide instruction issue with per-thread mask bits selecting which threads execute. defined in Chapter 10 — open in glossary (SIMT) execution. (Recent GPUs allow per-thread PCs and independent scheduling; we assume independently schedulable threads throughout.)

Programming model. GPUs have virtual ISAs — NVIDIA’s is PTX — under language frameworks like CUDA and OpenCL; programs compile to the virtual ISA and translate to native binaries at installation. A kernel kernel (gpu) The unit of work a CPU offloads onto a GPU; typically comprises thousands of software threads. defined in Chapter 10 — open in glossary is the unit of work a CPU offloads to the GPU, typically thousands of software threads. And unlike CPU threads, which are all “equal,” a kernel’s threads come grouped: a Cooperative Thread Array cooperative thread array (cta) Cluster of a kernel's threads guaranteed to map to the same SM and hence share its L1 (OpenCL: workgroup; CUDA: thread block). defined in Chapter 10 — open in glossary (CTA — OpenCL workgroup, CUDA thread block) is a cluster of threads guaranteed to land on the same SM, and therefore to share its L1.

That thread hierarchy is exposed to software as scopes scope The set of threads a synchronization operation applies to (CTA / GPU / System), implicitly naming the memory-hierarchy level those threads share (L1 / L2 / LLC). defined in Chapter 10 — open in glossary , and every scope names two things at once — a set of threads and the memory level those threads share:

Why expose this to programmers? Because early GPUs did not implement hardware cache coherence for their L1s — they never enforced the SWMR swmr invariant Single-writer–multiple-reader: for any memory location at any moment, either one core may write (and read) it, or some number of cores may only read it. defined in Chapter 2 — open in glossary invariant. Sharing the hierarchy with software lets programmer and hardware cooperate: put two synchronizing threads in the same CTA, and they can synchronize cheaply through the L1 they share.

GPU consistency without coherence

GPUs support relaxed consistency: like the relaxed CPUs of Chapter 5, they enforce only the orderings the programmer asks for via FENCE fence Instruction forcing all program-order-earlier memory operations into memory order before all later ones (a.k.a. memory barrier). defined in Chapter 4 — open in glossary instructions. But with no L1 coherence, a GPU FENCE means less than a CPU FENCE: it orders the thread’s memory operations only with respect to threads of the same CTA. A corollary: GPU stores are not store atomic write atomicity A store becomes logically visible to all other cores at once (its own core may see it early); a.k.a. store atomicity or multi-copy atomicity. defined in Chapter 5 — open in glossary (§5.5) — a store may become visible to a same-CTA thread long before anyone else.

Consider message passing — the same idiom as Table 3.1, now on a GPU (book Table 10.1):

Without the FENCEs, r2 can certainly be 0 — a relaxed GPU reorders freely. With them, and with T1 and T2 in the same CTA (hence the same SM), the FENCEs work exactly like XC’s: the reorder unit enforces Load/Store → FENCE → Load/Store, both stores reach the shared L1 in program order, and r2 = NEW. So far so good.

Now put T1 and T2 in different CTAs, on SMs 1 and 2. The FENCE still writes NEW then SET into SM1’s L1 in order — but visibility to T2 is at the mercy of cache geography. One legal sequence of events (book p. 215):

1. Initially both data and flag are cached in both L1s.
2. St1 and St2 perform in program order into SM1’s L1.
3. The line holding flag is evicted from SM1’s L1 → flag=SET reaches the L2.
4. The line holding flag in SM2’s L1 is evicted too.
5. Ld1 misses in SM2’s L1, fetches from the L2 — reads SET.
6. Ld2 hits in SM2’s L1 — and reads the stale 0.

The stores became visible in the opposite order. This is why early GPU manuals simply forbade inter-CTA synchronization between a kernel’s threads. The practical workaround (book Table 10.2): special memory operations that target a specific hierarchy level —

Bypassing works — here both variables genuinely must cross SMs — but it scales terribly: with many variables, only some of which cross SMs, the programmer must hand-route every load and store to the right cache level or forfeit the L1 entirely. Confusion documented in the wild.

Where that leaves us. For graphics, the design was rational: no coherence hardware, at the price of a scoped consistency model scoped consistency model Consistency model whose atomic operations carry scopes; a release synchronizes with an acquire only if the acquire reads the release's value AND each operation's scope includes the thread executing the other. Formalized with Shasha–Snir-style partial orders (NVIDIA PTX). defined in Chapter 10 — open in glossary that only really permitted intra-CTA synchronization. But GPUs now run general-purpose workloads (GPGPU) with fine-grained synchronization and richer sharing. A GPGPU wants:

• a rigorous, intuitive consistency model permitting synchronization among all threads; and
• a coherence protocol that enforces it while keeping data sharing efficient — and keeping the conventional GPU architecture simple, because graphics still pays the bills.

10.1.2 Big picture: why not just do what CPUs do?

The obvious move is to bolt on a consistency-agnostic consistency-agnostic coherence Coherence in which a write returns only after being made visible to all cores; presents the illusion of an atomic memory, independent of the consistency model. defined in Chapter 2 — open in glossary protocol from Chapters 6–9 and enforce, say, SC. It ticks nearly every box — intuitive model, no scopes, efficient sharing — and it is ill-suited to a GPU for two structural reasons:

Drop writer-initiated invalidation, though, and a puzzle appears: if a writer never invalidates remote copies, how does its store ever become visible to other CTAs — let alone under a strong model? The answer both proposals below share is self-invalidation self-invalidation The reading core invalidates blocks in its own cache to make other threads' stores visible, replacing writer-initiated invalidation — the enabling idea of GPU coherence. defined in Chapter 10 — open in glossary : the reader invalidates lines in its own cache so that other threads’ stores can be seen. And self-invalidating protocols turn out to be a natural fit for consistency-directed consistency-directed coherence Coherence in which writes propagate asynchronously but the order writes become visible must obey the consistency model; the newer GPU-era category. defined in Chapter 2 — open in glossary coherence (§2.3’s second, till-now-unused category): rather than enforcing SWMR and letting the pipeline build consistency on top, they enforce the relaxed consistency model itself, directly.

Whether the model should keep scopes is genuinely contested — scopes burden programmers but simplify hardware. Since they refuse to die (all of today’s industrial GPU models are scoped), we’ll build up to a scoped model whose scopes do not restrict who may synchronize with whom.

10.1.3 Temporal coherence

The first approach rests on one idea: leases. Each reader brings a block into its L1 for a finite period — its lease lease The finite validity period a reader requests for a block; the L1 tags the block with it and the L2 keeps the maximum lease across all L1s. defined in Chapter 10 — open in glossary — and when the lease expires the block self-invalidates. No sharer lists, no invalidation messages: time does the work. This is temporal coherence temporal coherence Lease-based self-invalidation protocol on globally synchronized timestamps: readers hold blocks for a lease and self-invalidate at expiry. The consistency-agnostic variant stalls writes at the L2 until expiry (SWMR ⇒ SC); the consistency-directed variant returns GWCTs and stalls FENCEs instead (XC-like). defined in Chapter 10 — open in glossary , and it needs global timestamps: every L1 and the L2 can read a synchronized global-time register.

Mechanics, for the whole subsection: L1s are write-through / no-write-allocate (§9.1’s trade-offs apply); the L2 is inclusive. On an L1 miss the reader predicts how long it wants the block and requests that lease with GetV(t); every L1 block is tagged with its lease timestamp, and a read past the timestamp is a miss. The L2 tags every block with a timestamp too, maintained as the latest lease across all L1s.

Consistency-agnostic temporal coherence: writers wait

The first variant enforces SWMR outright: a write to a block with unexpired leases stalls at the L2 until the last lease runs out. When it finally performs, provably no reader holds a valid copy. Combined with cores that present operations in program order, that yields SC.

Step through the book’s timeline (Table 10.4) for the message-passing program of Table 10.3 — T1: St1 data1=NEW; St2 data2=NEW; FENCE; St3 flag=SET versus T2: spin on flag, then read data2:

The protocol itself is two small stable-state tables. (High-level specs, like all of this chapter’s: stable states only — the book elides the transient states that Chapters 7–8 taught you to expect. Also note the L1’s V takes the Shared color: many L1s may hold a block at once, and nothing but time ever takes it away.)

Two cells deserve special attention: P × WriteV(t)’s timestamp check (the delayed-write corner case, where a WriteV from an old private holder races the block becoming private elsewhere), and the eviction columns — the L2 may only evict Expired blocks, because a future write must find the lease here to know how long to stall.

Consistency-directed temporal coherence: FENCEs wait instead

Stalling writes at the L2 is expensive real estate — the L2 is shared by all threads, so one thread’s wait can throttle the whole GPU. But who said we need SWMR? A relaxed model like XC only requires the orderings that FENCEs demand. For Table 10.3, XC requires St1 and St2 to be visible before St3 — it does not require St1 to be visible the moment it performs.

So: let writes perform at the L2 immediately. If the block’s lease is unexpired, the L2 replies with the block’s timestamp — the Global Write Completion Time global write completion time (gwct) The timestamp the L2 returns to a writer: the time by which the write is globally visible. Each SM tracks a per-thread max GWCT and stalls FENCEs until it. defined in Chapter 10 — open in glossary , the moment the write becomes visible to all threads (every stale lease expired). Each SM accumulates, per thread, the maximum GWCT in a stall-time register; a FENCE stalls the thread until its stall-time passes. The waiting still happens — but privately, on the one thread that fenced, not at the shared L2.

The specs change by exactly this much (diffs called out per cell — in the book they’re bold, with the removed stalls struck through):

What model does this enforce? An XC-like model without store atomicity — enforced directly by the coherence protocol, with SWMR consciously abandoned. That is consistency-directed coherence, no longer as a ch. 2 abstraction but as real hardware.

10.1.4 Release consistency-directed coherence

Leases are powerful but heavyweight. The second family — release consistency-directed coherence release consistency-directed coherence (rcc) Protocol enforcing release consistency directly: a release writes back all dirty L1 blocks; an acquire reads a fresh copy from the L2 and self-invalidates all other valid blocks. CTA-scoped synchronization skips both. defined in Chapter 10 — open in glossary (RCC) — narrows its ambition: it can only enforce variants of release consistency release consistency (rc) Relaxed model observing that an acquire needs only a succeeding fence and a release only a preceding one, replacing full FENCEs with one-direction ACQUIRE/RELEASE. defined in Chapter 5 — open in glossary (§5.5), and in exchange it is simpler, needs no timestamps, works with non-inclusive L2s, and exploits scopes naturally.

RC, without and with scopes

Recall RC’s one-directional orderings, now written GPU-style:

The message-passing idiom needs no FENCEs at all (book Table 10.10):

In the non-scoped model, that guarantee holds no matter where T1 and T2 run. In a scoped model, each atomic carries a scope, and a release synchronizes with an acquire only if both conditions hold: the acquire reads the release’s value, and each operation’s scope includes the thread executing the other operation. Concretely (book Table 10.11):

Formally, scoped RC drops the total memory order in favor of a partial order on conflicting operations, in the spirit of Shasha and Snir (§3.11) — only synchronizing release/acquire pairs are ordered. NVIDIA formalized its PTX memory model exactly this way.

Plain RCC: push on release, pull on acquire

The protocol enforces RC directly — SWMR is never attempted. L1s are now ordinary write-back/write-allocate caches, and the whole protocol is three rules:

1. Unmarked loads and stores behave normally (hit locally, dirty the line).
2. A release first writes back every dirty block in the L1 to the L2, then performs and writes back its own store — enforcing Load/Store → Rel Store.
3. An acquire reads a fresh copy of its block from the L2, then self-invalidates every other valid block in the L1 — enforcing Acq Load → Load/Store.

Scopes drop out beautifully: a GPU-scoped release/acquire is exactly the protocol above (the L2 is GPU scope’s memory level), while a CTA-scoped release or acquire degenerates to a plain store or load — the CTA’s threads already share the L1. And because the L2 holds no metadata — no sharers, no owner — it may evict blocks silently and needn’t be inclusive, the two things temporal coherence couldn’t offer. The price: without scope annotations, RCC must assume the worst. Two threads synchronizing on the same SM still pay a full flush-and-purge.

RCC-O: ownership as an optimization

Full-L1 write-backs and self-invalidations are the expensive part. The first fix: track ownership. Every store must first obtain ownership of its line (GetO); the L2 remembers, per block, which L1 owns it, and downgrades a previous owner (collecting its data) before granting. Then:

• An Owned block need not be written back on a release — the L2 knows where to find it.
• An Owned block need not be self-invalidated on an acquire — we own it; no remote writer can exist.
• Best of all: an acquire that hits an Owned block in its own L1 has detected intra-CTA synchronization — the matching release must have happened on this SM — so the whole self-invalidation is skipped, even with no scope information at all.

The residual conservatism: releases still pay. Every store before a release obtained ownership with a GetO round-trip — even when the synchronization never leaves the CTA.

LRCC: laziness completes the picture

Lazy RCC lazy release consistency-directed coherence (lrcc) Only release stores obtain ownership (on behalf of prior stores); all coherence actions are deferred to the acquire, whose block state discriminates intra-CTA (owned locally: nothing to do) from inter-CTA (owned remotely: remote write-backs plus local self-invalidation). defined in Chapter 10 — open in glossary makes the last move: ordinary stores don’t obtain ownership — only release stores do, on behalf of all the stores before them. Nothing else happens at release time. The coherence work is deferred until some thread acquires the released block, and the block’s state at that moment tells the protocol which case it’s in:

• Owned by the acquirer’s own L1 → the release happened here: intra-CTA, read hit, done. Zero self-invalidations, zero write-backs.
• Owned by a remote L1 → inter-CTA: the L2 downgrades the owner, which first writes back all its dirty non-owned blocks (the deferred release work) and then the flag; the acquirer self-invalidates its valid non-owned blocks and proceeds.

Note what O means now: an owned block is a synchronization object — a flag or lock standing in for the unpublished stores behind it. That’s why evicting or downgrading an O block first flushes the L1’s dirty non-owned data, and why the L2 can never drop an O block silently — though since only releases create O blocks, that burden touches sync objects only.

The family at a glance — and the scopes verdict

So if LRCC handles intra-CTA synchronization efficiently without scopes — can scoped models finally retire? The book’s answer: not quite. Laziness moves every deferred write-back onto the acquire’s critical path, and inter-CTA acquires get slower — much more so when the synchronization crosses devices (CPU ↔ GPU). Scopes versus scope-free remains a genuine programmability-vs-performance trade-off, not a solved problem.