Protocols are tables
We specify a coherence protocol by specifying its coherence controllers coherence controller The finite state machine at each storage structure (logically one independent FSM per block); the controllers' message exchanges enforce the SWMR and data-value invariants. defined in Chapter 6 — open in glossary — and a controller’s behavior lends itself perfectly to a tabular specification:
- Rows are block states.
- Columns are events.
- Each state/event entry is a transition: (a) the actions taken when event E occurs for a block in this state, and (b) the block’s next state — written “action/next state”, with the “/next state” part omitted when the state doesn’t change.
Table 6.1 demonstrates the methodology with a deliberately incomplete three-state controller. This is also the debut of the widget that will carry chapters 7–9: click any cell for a plain-English explanation of its transition, or a state chip for that state’s meaning:
Table 6.1 (recreated): an intentionally incomplete cache controller
| State | Load request from core | Store request from core | Incoming coherence request to obtain block in read-write state |
|---|---|---|---|
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.
Reading one example off the table: a store request arrives from the core for a block in read-only (RO) state → the controller performs “issue coherence request for read-write permission” and the block’s state becomes RW.
Why this table can’t ship
The book is upfront: this specification is intentionally incomplete. It shows the methodology’s shape, but a real controller table needs more of everything — more events (evictions, more kinds of incoming requests), and above all the transient states that describe a block while a transaction is outstanding (N’s load transition can’t really jump straight to RO — the data hasn’t arrived yet). §6.3 fixes exactly that with a small but complete protocol.
The punchline of the methodology: the differences between coherence protocols are differences in their controller specifications — different sets of block states, transactions coherence transaction A coherence request plus the other messages exchanged to satisfy it (e.g., the data response). defined in Chapter 6 — open in glossary , events, and transitions. Specify the cache controller and memory controller tables completely, and you have specified the protocol. Every protocol in the rest of this book — snooping and directory, MSI through MOESI — speaks this one tabular language.
Check yourself
1.In the tabular specification methodology, what exactly is a TRANSITION?
2.In Table 6.1, a store request arrives for a block in read-only (RO) state. What does the specification say happens?
3.What actually differs between two coherence protocols, in this framework?
4.Table 6.1 is described as "intentionally incomplete." What's missing that a real specification would need?