A protocol designer chooses states, transactions, events, and transitions for each controller. Usefully, the first two are largely independent of the protocol — a snooping protocol and a directory protocol can share the same stable states and transactions — while events, transitions, and the specific transient states are deeply protocol-dependent (chapters 7 and 8 own those).
6.4.1 States
In a single-actor system a block is just valid or invalid — maybe valid-and- dirty dirty A block value that is more recent than the LLC/memory copy, which this cache must eventually update; clean is the opposite. defined in Chapter 6 — open in glossary if a write-back L1 must remember it’s newer than the L2. Multiple actors make two more characteristics meaningful, for four in total:
Validity
A valid block holds the most up-to-date value. It may be read — but written only if also exclusive.
Dirtiness
The value is newer than the LLC/memory copy, and this cache controller must eventually update memory. Clean = the opposite.
Exclusivity multi-actor only
The only privately cached copy in the system (except perhaps the shared LLC). Careful: “exclusive” the characteristic ≠ “Exclusive” the state.
Ownership multi-actor only
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 must respond to coherence requests for the block, and may not evict it without transferring ownership. Non-owned blocks may allow silent eviction silent eviction Evicting a block without sending any message; permitted for non-owned states (S, sometimes E) in some protocols. defined in Chapter 6 — open in glossary .
The MOESI stable states
Most protocols use a subset of the classic MOESI moesi Sweazey and Smith's five classic stable states (Modified, Owned, Exclusive, Shared, Invalid); MSI is the fundamental core, with O and E as optimizations. defined in Chapter 6 — open in glossary model (Sweazey and Smith; pronounced “MO-sey” or “mo-EE-see”). MSI is the fundamental core; O and E are optimizations:
- M(odified) — valid, exclusive, owned, potentially dirty. Read-write. The only valid copy; must respond to requests; memory potentially stale.
- O(wned) — valid, owned, potentially dirty, not exclusive. Read-only; other caches may hold read-only copies; memory potentially stale.
- E(xclusive) — valid, exclusive, clean. Read-only; no other cached copy; memory up-to-date. This primer treats E as an ownership state — some protocols don’t, and the MESI chapters return to that choice.
- S(hared) — valid, not exclusive, not dirty, not owned. A read-only copy; others may exist.
- I(nvalid) — no usable copy: absent, or a potentially stale copy that may not be read or written. (The primer doesn’t distinguish absence — “Not Present” — from staleness.)
Figure 6.4 (recreated): which MOESI states share which characteristics. §6.3’s toy protocol condensed M, O, E, and S into its single V state.
MOESI is common but not exhaustive — the F(orward) forward (f) A non-MOESI stable state like Owned except clean (the LLC/memory copy is up-to-date). defined in Chapter 6 — open in glossary state, for example, is O’s clean twin (memory stays up-to-date).
Transient states, and where states live
For LLC/memory blocks, two naming conventions exist — cache-centric 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 (the state aggregates the caches’ states: all-I ⇒ I, some-S ⇒ S, one-M ⇒ M; the primer’s choice) and memory-centric (the state describes memory’s own permissions: all-caches-I would be O, since memory acts as owner). Purely a specification convention — §6.3’s memory table already showed how confusing it can read.
Maintaining all this: stable state costs a few bits per cache/LLC block (3 bits cover MOESI); transient states are needed only for blocks with pending transactions, so they live in MSHRs mshr Miss status handling register; tracks a pending transaction and holds the block's transient coherence state bits. defined in Chapter 6 — open in glossary . And memory? Modern multicores usually have an inclusive LLC inclusive llc An LLC holding a copy of every block cached anywhere in the system, letting memory omit explicit coherence state (absence from the LLC implies Invalid). defined in Chapter 6 — open in glossary — a copy of every cached block — so a block’s memory state is its LLC state, and absence from the LLC implies Invalid.
6.4.2 Transactions
Most protocols share a similar transaction set, because the controllers’ goals are similar (Table 6.4):
| Transaction | Goal of requestor |
|---|---|
| GetShared ( GetS gets Coherence request to obtain a block in a read-only (Shared) state. defined in Chapter 3 — open in glossary ) | Obtain block in Shared (read-only) state |
| GetModified ( GetM getm Coherence request to obtain a block in a read-write (Modified) state. defined in Chapter 3 — open in glossary ) | Obtain block in Modified (read-write) state |
| Upgrade (Upg) upgrade (upg) Transaction upgrading a block from read-only (Shared or Owned) to read-write (Modified) without a data transfer. defined in Chapter 6 — open in glossary | Upgrade from read-only (S or O) to read-write (M); unlike GetM, no data transfer — the requestor already has the block |
| PutShared (PutS) | Evict a Shared block † |
| PutExclusive (PutE) | Evict an Exclusive block † |
| PutOwned (PutO) | Evict an Owned block (with data) |
| PutModified (PutM) | Evict a Modified block (with data) |
† Some protocols need no transaction at all to evict S and/or E blocks — the PutS/PutE put transactions (puts/pute/puto/putm) Eviction transactions for blocks in Shared/Exclusive/Owned/Modified state; PutM and PutO carry data; PutS and PutE may be silent in some protocols. defined in Chapter 6 — open in glossary are “silent.”
Table 6.5 maps what cores ask for onto these transactions:
| Core request | Typical cache controller response |
|---|---|
| Load | Hit: respond with data. Miss: initiate GetS |
| Store | Hit in E or M: write the cache. Else: GetM or Upg |
| Atomic RMW | Hit in E or M: execute RMW atomically. Else: GetM or Upg |
| Instruction fetch | Hit (I-cache): respond. Miss: GetS |
| Read-only prefetch | Hit: ignore. Else: optionally GetS (controllers may ignore prefetches) |
| Read-write prefetch | Hit in M: ignore. Else: optionally GetM/Upg |
| Replacement | PutS / PutE / PutO / PutM, per the block’s state |
Where protocols differ is how controllers interact to perform these transactions — a GetS may be broadcast to everyone (snooping, with whichever controller owns the block responding) or unicast to one pre-defined controller that responds or forwards (directory).
6.4.3 The two big design decisions
Snooping snooping protocol Cache controllers broadcast requests to all coherence controllers, which collectively "do the right thing" (the owner responds); relies on ordered — typically totally ordered — request delivery. defined in Chapter 6 — open in glossary
Requests are broadcast to all coherence controllers, which collectively “do the right thing” (the owner responds). Relies on the network delivering broadcasts in a consistent — usually total — order, e.g., a shared-wire bus. Logically simple; broadcasting doesn’t scale.
Directory directory protocol Cache controllers unicast requests to the block's home memory controller, whose directory tracks owner/sharer state and responds or forwards to the owner; scalable but adds indirection. defined in Chapter 6 — open in glossary
Requests are unicast to the block’s home memory controller, whose directory records owner/sharer identities; it responds, or forwards to the owner cache, which responds. Scalable; but an extra message when the home isn’t the owner.
Invalidate 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
A write first invalidates all other copies; a later reader re-fetches from the writer. The overwhelmingly common choice, and this primer’s focus.
Update update protocol On a write, other copies are updated with the new value instead of invalidated; cheaper subsequent reads but more bandwidth and much harder write atomicity; rarely implemented. defined in Chapter 6 — open in glossary
A write pushes the new value into all other copies. Cheaper subsequent reads — but bigger messages (address + value), much more bandwidth, and write atomicity becomes very hard with multiple updates in flight. Rarely implemented.
The two axes are independent — and neither is a straitjacket: hybrids exist on both (protocols blending snooping with directories, and invalidation with updates). The design space is rich, and the next three chapters explore its most important regions.
Check yourself
1.Four characteristics of a cache block are encoded in its state. Which two exist ONLY in systems with multiple actors?
2.Owned (O) and Exclusive (E) are the two optional MOESI states. What distinguishes them?
3.What does the transient-state notation IM^D mean?
4.Why does an INCLUSIVE LLC let memory avoid storing any explicit coherence state?
5.How does an Upgrade (Upg) transaction differ from a GetM?
6.Update protocols reduce read latency after a write, yet the book (and industry) sticks with invalidate. Why?
Chapter 6 references
- A. Charlesworth. The Sun Fireplane SMP interconnect in the Sun 6800. Hot Interconnects, 2001.
- P. Conway and B. Hughes. The AMD Opteron northbridge architecture. IEEE Micro, 27(2), 2007.
- S. J. Frank. Tightly coupled multiprocessor system speeds memory-access times. Electronics, 57(1), 1984.
- D. Kroft. Lockup-free instruction fetch/prefetch cache organization. ISCA, 1981.
- H. Q. Le et al. IBM POWER6 microarchitecture. IBM J. R&D, 51(6), 2007.
- M. M. K. Martin, D. J. Sorin, M. D. Hill, and D. A. Wood. Bandwidth adaptive snooping. HPCA, 2002.
- A. Nowatzyk, G. Aybay, M. Browne, E. Kelly, and M. Parkin. The S3.mp scalable shared memory multiprocessor. ICPP, 1995.
- A. Raynaud, Z. Zhang, and J. Torrellas. Distance-adaptive update protocols for scalable shared-memory multiprocessors. HPCA, 1996.
- D. J. Sorin, M. Plakal, M. D. Hill, A. E. Condon, M. M. Martin, and D. A. Wood. Specifying and verifying a broadcast and a multicast snooping cache coherence protocol. IEEE TPDS, 13(6), 2002.
- P. Sweazey and A. J. Smith. A class of compatible cache consistency protocols and their support by the IEEE Futurebus. ISCA, 1986.