1.2Coherence (a.k.a. Cache Coherence)

When copies go stale

A coherence problem can arise whenever three ingredients meet: multiple actors (e.g., multiple cores) with access to multiple copies of a datum (e.g., in multiple caches), where at least one access is a write. Remove any ingredient — one actor, one copy, or reads only — and nothing can go wrong.

The book replays the university story from §1.1, but with a crucial twist: this time the student keeps a copy. Step through what happens:

The student’s calendar entry is a cached copy of the schedule. When the registrar writes to the original, the copy silently becomes stale — an incoherent incoherence Accessing a stale copy of a datum after another actor has written the original. defined in Chapter 1 — open in glossary situation. If she trusts the copy, she goes to Room 152 and finds an empty room.

Note how this differs from §1.1’s problem. There, the student read the original schedule and the issue was purely the order in which two writes became visible. Here the issue is a stale copy that no longer reflects the original at all. That is the distinction between consistency (ordering rules for reads and writes) and coherence cache coherence Making caches functionally invisible by propagating one processor's writes to other processors' caches; a means of supporting a consistency model, not a correctness definition itself. defined in Chapter 1 — open in glossary (keeping copies in sync) — the two problems the two halves of this book address.

Incoherence is not an exotic hardware phenomenon. The book offers everyday computing examples: stale web caches serving yesterday’s page, and programmers working from a repository clone that hasn’t pulled recent commits. Any cached copy anywhere can go stale.

Coherence protocols

Access to stale data is prevented by a coherence protocol coherence protocol The set of rules implemented by a system's distributed actors (cache and memory controllers) that prevents access to stale data. defined in Chapter 1 — open in glossary : a set of rules implemented by the distributed set of actors within a system — there is no central referee; every cache controller and memory controller follows the rules locally, and the rules guarantee the global property. Protocols come in many variants (developed across chapters 6–9), but all share one essence: they make one processor’s write visible to the other processors by propagating the write to all caches — keeping the calendar in sync with the online schedule. Where variants differ is in when and how the syncing happens.

Two classes of coherence protocols

The design space splits at the top into two classes, distinguished by when writes propagate:

1. Synchronous propagation (“consistency-agnostic” coherence). The protocol ensures that writes propagate to the other caches synchronously: the moment the online schedule is updated, the student’s calendar is updated too. Because copies never lag, this class makes caches invisible regardless of which consistency model sits on top. This is the class the primer focuses on, in chapters 6–9.
2. Asynchronous propagation (“consistency-directed” coherence). The protocol may propagate a write lazily — the calendar can go stale for a while — as long as the consistency model is still honored: the new value must reach the student’s calendar before the registrar’s text message reaches her phone. This emerging class, common in GPUs and heterogeneous systems, is the subject of Chapter 10.

The coherence roadmap (chapters 6–9)

• Chapter 6 — the big picture. What all protocols share: the distributed operation of cache controllers and memory controllers, and the five classic stable states MOESI — Modified, Owned, Exclusive, Shared, Invalid. It also introduces the primer’s table-driven methodology for specifying protocols, including transient states. Real systems rarely allow an atomic jump between stable states — a read miss in Invalid waits for a data response before reaching Shared — and much of the true complexity of coherence hides in those in-between states, just as much of a processor core’s complexity hides in micro-architectural state.
• Chapter 7 — snooping protocols. Historically dominant and simple at hand-wave level: on a miss, a cache controller arbitrates for a shared bus and broadcasts its request; because every controller observes every request in the same order, their distributed actions stay globally consistent. The complexity arrives when the bus stops being ideal — multiple buses, queued arbitration, unicast, pipelined or out-of-order responses — each feature breeding more transient states. Case studies: Sun UltraEnterprise E10000 and IBM Power5.
• Chapter 8 — directory protocols. Built on the old joke that every problem in computer science can be solved with a level of indirection. A miss asks the next-level controller, which consults a directory tracking which caches hold which locations, then responds directly or forwards the request to the current holders. Messages are unicast — no broadcast — which is why directories promise scaling to many more cores; the price is indirection latency and an abundance of transient states, since one stable-to-stable transition can involve messages proportional to the number of actors. The chapter grows a basic MSI directory into E and O states, distributed directories, less stalling, and approximate directory representations. Case studies: SGI Origin 2000, AMD Coherent HyperTransport, HyperTransport Assist, Intel QPI.
• Chapter 9 — advanced topics. The realistic system models the earlier chapters deliberately simplified away: instruction caches, multilevel caches, write-through caches, TLBs, coherent DMA, virtual caches, and hierarchical protocols; then performance optimizations targeting migratory sharing and false sharing, and Token Coherence, a protocol family that subsumes both snooping and directories.