The system, the states, the messages
To make the methodology concrete, here is a complete — if simplistic — protocol. The system is chapter 2’s baseline with the interconnection network restricted to a shared bus: a set of wires on which one message at a time is observed by all cores and the LLC/memory.
- States: each cache block is I(nvalid) or V(alid); each LLC/memory block is also I or V — named cache-centrically cache-centric naming Naming an LLC/memory block's state as the aggregation of its caches' states (the primer's convention); the alternative memory-centric naming uses the memory controller's own permissions. defined in Chapter 6 — open in glossary (more below). Plus one transient state transient state A state occurring during a non-atomic transition between stable states; notation XY^Z means "was X, becoming Y, completing when an event of type Z occurs." defined in Chapter 6 — open in glossary , IV^D. Everything starts in I.
- Messages: Get requests a block, DataResp carries its data, Put writes it back (with data) to the memory controller.
- Transactions: Get (= Get + DataResp) and Put. The Get transaction is atomic: no other transaction may use the bus between a cache’s Get and the corresponding DataResp.
- Caches are writeback: a store hit writes only the local cache; the block reaches memory later, via Put, on an Evict Block event.
The cache controller — table and FSM, linked
The state machine and the specification table below are two views of the same thing — click a table cell and watch the matching arc light up, or click an arc to jump to its cell. The book’s Figure 6.3 shows only the stable states (I → V via “Own-Get + DataResp”); the site’s version includes the transient state that transition secretly passes through:
Figure 6.3 (recreated, transient state included)
Solid = stable state · dashed = transient · click a state or an arrow.
Table 6.2 (recreated): cache controller specification
| Core events | Bus events — own transactions | Bus events — other cores' transactions | ||||||
|---|---|---|---|---|---|---|---|---|
| State | Load or Store | Evict Block | Own-Get | DataResp for Own-Get | Own-Put | Other-Get | DataResp for Other-Get | Other-Put |
Cell format: action / next state (next state omitted when unchanged) · blank = event ignored · shaded = impossible. Click any cell or state chip.
Click a transition cell for its plain-English explanation, or a state chip for its invariants.
Three reading notes:
- Own- vs. Other- prefixes distinguish bus messages of transactions this controller initiated from everyone else’s.
- Blank cells are ignored events — they can occur, but require no action (e.g., another core’s Put while we hold nothing).
- Shaded cells are impossible — and each records an argument. The book’s example: a controller can never see its Own-Put while in V, because issuing the Put already moved the block to I. And every Other-event is impossible in IV^D, because the atomic bus admits no other transaction between our Get and our DataResp.
The memory controller
Table 6.3 (recreated): memory controller specification
| Bus events | ||
|---|---|---|
| State | Get | Put |
Cell format: action / next state (next state omitted when unchanged) · blank = event ignored · shaded = impossible. Click any cell or state chip.
Click a transition cell for its plain-English explanation, or a state chip for its invariants.
Note the naming trap: LLC/memory state I is when memory responds to Gets. The convention is cache-centric — the LLC/memory state aggregates the caches’ states (I = no cache holds the block), rather than describing memory’s own permissions. The memory-centric convention (§6.4.1) would call this same state O, since memory behaves as the owner owner The coherence controller responsible for responding to requests for a block; in most protocols exactly one owner exists at all times, and owned blocks may not be evicted without transferring ownership. defined in Chapter 6 — open in glossary . All protocols in this book (and on this site) use cache-centric names. Also note the blank V × Get cell: when a cache holds V, that cache answers the Get and memory stays in V — one holder simply replaces another.
What this protocol teaches
The transient state deserves the spotlight. Transient states arise whenever transitions between stable states are not atomic. Here, message sends and receives are individually atomic, but fetching a block takes a Get and a DataResp with an indeterminate gap between — so IV^D (“in I, going to V, waiting for D”) bridges the gap. This protocol needs exactly one transient state; the protocols of chapters 7 and 8 will need dozens, and chapter 7’s non-atomic buses (§7.5) are where the real explosion happens.
The protocol is deliberately inefficient — there is no read-only sharing at all (two readers ping-pong the block through memory-facing transactions), evictions of clean blocks still send full-data Puts, and every miss serializes on the atomic bus. Its job was only to show how a complete specification reads. §6.4 explores the design space real protocols occupy.
Check yourself
1.Why does even this two-state protocol need the transient state IV^D?
2.A cache holds block B in V, and another cache's Get for B appears on the bus. What must the V-holding cache do, and why?
3.Why is observing Own-Put while in state V an IMPOSSIBLE (shaded) entry?
4.Why are ALL the "Other-" bus events impossible while a cache is in IV^D?
5.At the LLC/memory, state I means all caches hold the block in I — and it's exactly then that MEMORY responds to Gets. Why the seemingly backwards name?