2.4(Consistency-Agnostic) Coherence Invariants

What invariants make caches invisible?

§2.3 promised that consistency-agnostic coherence presents the abstraction of an atomic memory system. What must a protocol actually guarantee to deliver that illusion? Many definitions of coherence exist in the literature (the sidebar below surveys them); the book commits to the one it finds most useful for designing protocols, built from two invariants.

The SWMR invariant

Coherence is defined first through the single-writer–multiple-reader ( 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:

For any given memory location, at any given moment in time, there is either a single core that may write it (and that may also read it) or some number of cores that may read it.

There is never a time when a location may be written by one core and simultaneously read or written by any other. An equivalent picture: divide each memory location’s lifetime into epochs epoch A slice of a memory location's lifetime during which one core has read-write access or some number of cores have read-only access. defined in Chapter 2 — open in glossary — in each epoch, either a single core has read-write access, or some number of cores (possibly zero) have read-only access. Explore the book’s example lifetime, then extend it yourself:

The data-value invariant

SWMR alone is not enough, because it says nothing about values. Even with SWMR holding, the system is incoherent if Cores 2 and 5 can read different values during their shared read-only epoch, or if Core 1 fails to see the last value Core 3 wrote in the preceding read-write epoch. So the definition adds the data-value invariant data-value invariant The value of a memory location at the start of an epoch equals its value at the end of its last read-write epoch. defined in Chapter 2 — open in glossary , governing how values pass from epoch to epoch:

The value of a memory location at the start of an epoch is the same as its value at the end of its last read-write epoch.

An equivalent view: tokens

A notable reinterpretation (Martin, Hill, and Wood) recasts the invariants as token counting: each memory location has a fixed number of tokens, at least as large as the number of cores. A core holding all the tokens may write the location; a core holding one or more may read it. One core writing concurrently with any other reader is then arithmetically impossible — SWMR by counting. File this away: it resurfaces as Token Coherence in Chapter 9.

2.4.1 Maintaining the invariants

The vast majority of protocols — invalidate protocols invalidate protocol The dominant protocol family maintaining SWMR: a read ends any other core's read-write epoch; a write also invalidates all other cached copies. defined in Chapter 2 — open in glossary — are designed explicitly around these invariants:

• To read a location, a core sends messages to obtain the current value and to ensure no other core holds it in a read-write state. That ends any active read-write epoch and begins (or joins) a read-only epoch.
• To write a location, a core sends messages to obtain the current value (if it lacks a valid read-only copy) and to invalidate all other cached copies. That ends any active epoch and begins a new read-write epoch.

Chapters 6–9 expand enormously on this two-sentence sketch — but the basic intuition you just exercised in the explorer above never changes.

2.4.2 The granularity of coherence

Cores load and store at granularities from 1 to 64 bytes, and in theory coherence could be tracked per byte. In practice it is maintained per cache block: the SWMR invariant really reads “for any block of memory, one writer or some number of readers.” In typical systems it is impossible for one core to write the first byte of a block while another core writes a different byte of the same block. Block granularity is assumed for the rest of the book — though protocols at finer and coarser granularities have existed.

2.4.3 When is coherence relevant?

Two closing points every architect must internalize:

• Coherence applies to every storage structure holding blocks from the shared address space — the L1 data cache, L2, shared LLC, and main memory, but also the L1 instruction cache and the TLBs (with the caveat that some architectures’ TLB entries aren’t strict copies of shared-memory blocks).
• Coherence is not architecturally visible. The pipeline and the coherence protocol jointly enforce the consistency model, and only the consistency model is visible to the programmer. Remember the pop quiz: several of its traps dissolve once you hold this line firmly.