Cache Coherence as an Optimisation Challenge for Parallelism — Epoche C1
What coherence is, and what it is not Two processor cores each hold a copy of the same 64-byte block of memory in their own private caches. Core A writes a new value into its copy. Unless something intervenes, core B will go on reading the old value from its copy indefinitely, because nothing in its local cache knows that anything happened. Cache coherence is the mechanism that intervenes, and this essay is about the fact that it does considerably more than prevent that one failure. The original version of this essay described coherence as ensuring "that all processors observe a unified view of memory". That description is too loose to support the argument built on it, and replacing it with a precise one changes what the rest can claim. Sorin, Hill and Wood's primer defines coherence by two invariants, and the definition is worth having exactly. Single-writer, multiple-reader. For any given memory location, at any given moment, either exactly one core may write it (and read it), or any number of cores may read it and none may write. Data value. When a location enters a period in which it may be read, the value it starts with is the value left by the most recent period in which it could be written. Two things follow. First, coherence is a property per memory location . It says nothing about the order in which operations to different locations become visible, which is the province of the memory consistency model and a separate subject. Conflating the two, as the original description invited, obscures the fact that coherence can be perfect while a program still behaves surprisingly. Second — and this is where the original essay's central insight is correct and can now be grounded — the first invariant delivers something stronger than freshness of data. It delivers a single total order of writes to each location on which every core agrees, because the writer-exclusive periods for a location cannot overlap and therefore form a sequence. That serialisation is not a by-product. It is the definition. Why MESI has those four states The states of the standard protocol are not an arbitrary vocabulary; each exists to make the invariants cheap to enforce for one common access pattern. A cached copy of a block is in one of four states, named by their initials. Invalid : the cache does not hold usable data for this block. Shared : the cache holds a clean, read-only copy; other caches may hold identical copies. This is the multiple-reader half of the first invariant. Modified : the cache holds the only copy, it has been written, and memory is stale. This is the single-writer half, and it also records that this cache owes memory a writeback. Exclusive : the cache holds the only copy and it is clean. Exclusive is the state whose purpose is least obvious and most instructive. It is redundant for correctness — the invariants would hold with Shared, Modified and Invalid alone. It exists because the commonest pattern in real code is to read a private variable and then write it. Without Exclusive, the read leaves the block Shared, and the subsequent write must broadcast an invalidation and wait for acknowledgement even though no other cache holds a copy. With Exclusive, a core that misses on a block nobody else holds is told so, and the later write is a silent local transition to Modified with no traffic at all. The extra state buys the elimination of a coherence transaction on every private read-modify-write, which is why every production protocol has it. MOESI adds an Owned state on the same principle: a modified block can be supplied directly to another requesting cache while the supplier retains responsibility for the eventual writeback, saving a write to memory that a plain MESI transition would force. The state space, counted properly The original essay observed that "the state space and potential transitions grow rapidly" for $N$ processors, without saying how fast. The count is worth doing because the naive answer and the right answer differ by a large factor and are both exponential. Naively, each of $N$ caches is independently in one of four states, giving $4^{N}$ global configurations per block — about $4.3 \times 10^{9}$ for sixteen cores. But the invariants forbid most of these. At most one cache may be in Modified or Exclusive, and if any cache is, no other may be in Shared. The legal configurations are therefore: all Invalid, which is one; exactly one cache Modified with the rest Invalid, which is $N$; exactly one Exclusive with the rest Invalid, another $N$; and any non-empty subset of caches in Shared with the rest Invalid, which is $2^{N} - 1$. The total is $$ 2^{N} + 2N , $$ which for sixteen cores is $65{,}568$ — smaller than the naive figure by a factor of about sixty-five thousand, and still exponential in the core count. This is why coherence protocols are verified by model checking rather than by inspection, and why the count understates the difficulty: the states above are the stable ones, and a real implementation on a network that does not guarantee message ordering needs a larger number of transient states to represent blocks with requests outstanding. Atomicity falls out of the same machinery The original essay claimed that the exclusive ownership granted by the protocol acts as a distributed lock and thereby makes atomic operations possible. That is right, and the mechanism is worth stating because it also exposes the cost. Compare-and-swap is an instruction that reads a location, compares it with an expected value, and writes a new value only if they match, all as one indivisible step. Its implementation needs no additional hardware beyond coherence: the core acquires the block in Modified state, performs the read, the comparison and the write, and simply declines to answer coherence requests for that block until it is done. Because the first invariant guarantees that no other core can hold the block writable during that window, no interleaving is possible. Load-linked and store-