6.1The Big Picture

This chapter returns to cache coherence, defined back in chapter 2 to understand its role in supporting consistency — but chapter 2 never said how coherence protocols work. This chapter covers protocols in general: the big picture here, the specification methodology in §6.2, one simple concrete protocol in §6.3, and the design space in §6.4. The two chapters after that cover the two great protocol families — snooping and directory — in depth.

Distributed state machines

The goal of a coherence protocol is to enforce the two invariants of §2.4, restated:

The enforcement mechanism: associate with each storage structure — each cache, and the LLC/memory — a finite state machine called a coherence controller 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 . Together the controllers form a distributed system, exchanging messages to keep both invariants holding for every block at all times. The coherence protocol is precisely the specification of how these state machines interact.

The two controller types

The cache controller cache controller The coherence controller at a private cache: a core side accepting loads/stores and returning values, and a network side issuing/receiving coherence messages; misses initiate coherence transactions. defined in Chapter 6 — open in glossary serves two masters. On its core side, it accepts loads and stores from the processor core and returns loaded values. A cache miss makes the controller start a coherence transaction 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 by issuing a coherence request for the block (e.g., a request for read-only permission) across the interconnection network; the transaction consists of that request plus the other messages exchanged to satisfy it (e.g., a data response from another controller). On its network side, it receives and processes the coherence requests and responses of others. Which transactions and messages exist depends on the specific protocol.

The memory controller memory controller (coherence) The coherence controller at the LLC/memory; usually network-side only, so it neither issues requests on behalf of loads/stores nor receives coherence responses. defined in Chapter 6 — open in glossary at the LLC/memory is the same idea with the core side removed: it usually has only a network side, so it does not issue coherence requests on behalf of loads or stores, and does not receive coherence responses. Other agents — I/O devices, for instance — may behave like cache controllers, memory controllers, or both.

One state machine per block

Each controller implements a set of finite state machines — logically one independent but identical FSM per block. When an event of type E (say, a store request from the core) arrives for block B, the controller takes actions that are a function of both E and B’s current state (say, issue a request for read-write permission because B is read-only), and may then change B’s state.

That “function of event and state” phrasing is no accident: it is exactly the shape of a table — and tables are how the book (and this site) specifies every protocol from here on. On to §6.2.