Cache Coherence Is Per Location, Consistency Is Not

Coherence is often described as the rule that all processors see the same order of writes to a single location. That rule is necessary for a working multiprocessor and it is not sufficient for anything a programmer would call correct. The two properties are enforced by different machinery at different layers, and conflating them produces code that looks synchronised and is not.

The clean way to separate them is by what each one quantifies over. Coherence is a statement about one address at a time. Consistency is a statement about the set of all addresses, and about which orderings between them survive.

What coherence actually guarantees, stated narrowly

For a single memory location, a coherence protocol guarantees three things, all of which follow from having one authoritative copy of the line at any moment:

• A read returns the most recently written value to that location, in the serial order of writes to it.
• Writes to the same location are serialised into a single order, the same order for every observer.
• A processor that writes a location and then reads it back, with nothing else writing in between, reads what it wrote.

That third clause is sometimes called read-your-write or program-order-for-same-address, and it is the one a store buffer threatens. If a core writes x into a buffer and then loads x, the load must be satisfied from the buffer, not from the cache line still holding the old value. Every real design does this: a load checks the store buffer before the cache, a mechanism usually called store-to-load forwarding.

Notice what is absent. Coherence says nothing about two writes to different locations, because different locations may live in different cache lines and be owned by different cores at the same time. It says nothing about a load of y relative to a store of x. It says nothing about the order in which a third core observes a sequence of writes to two different lines.

The protocol that provides these guarantees in a typical design is a directory or snooping scheme over cache lines, most commonly a four-state MESI variant. Each line is in Modified, Exclusive, Shared, or Invalid state in each cache, and transitions are driven by read and read-for-ownership requests on the interconnect. The unit of coherence is the cache line, not the byte: 64 bytes on the common architectures, and the protocol tracks ownership at that granularity. False sharing is the direct consequence, and it is a coherence phenomenon, not a consistency one. Two cores writing different bytes of the same line serialise against each other even though their data does not overlap.

The two-location counterexample

The distinction matters because coherence is compatible with an execution no single ordering explains. Take four threads and two locations, initialised to zero:

// x = 0, y = 0
void *t1(void *_) { x = 1; return NULL; }   // store x
void *t2(void *_) { y = 1; return NULL; }   // store y
void *t3(void *_) { int a = x; int b = y; return NULL; } // load x, then y
void *t4(void *_) { int c = y; int d = x; return NULL; } // load y, then x

Suppose the observed values are a == 1, b == 0 and c == 1, d == 0. Thread 3 saw the new x before the new y. Thread 4 saw the new y before the new x. Each thread’s loads are internally consistent with some order of the two stores, and each location’s writes are trivially serialised because there is only one write to each. Yet the two observations contradict each other: no single order of x = 1 and y = 1 makes thread 3 see x first and thread 4 see y first.

Coherence is satisfied. Each location has a well-defined write order, and each load returned a value that some write to that location produced, with no value going backwards. What failed is the requirement that the two per-location orders be embedded in one global sequence. This is the distinction the sequential consistency definition in Sequential Consistency and the Cost of One Global Memory Order is built on, and the reason a coherent machine is not automatically a sequentially consistent one.

The physical mechanism that produces this outcome is mundane. The two stores are issued by two cores at nearly the same time and propagate through the interconnect along different paths to different observers. There is no global clock and no global ordering point, so “which store happened first” is not a fact the hardware possesses. It only has per-line serialisation points.

Where the ordering obligation is discharged

Since coherence will not order accesses to different lines, something else must, and there are only three candidates: the memory model implemented by the hardware, the fence instructions the program uses, and the compiler that emits them.

At the hardware level, a model specifies which orderings are preserved for which access types. Total Store Order preserves store-store, load-load, and load-store order but lets a load bypass an earlier store to a different address, which is why the store-buffering outcome is legal on x86 while the four-thread outcome above is not. Models that also relax store-store order, such as Arm and PowerPC, make message passing legal. The four-thread outcome is a further step down: it needs two observers to disagree about the order of the two stores, which is possible only on a model that is not multi-copy atomic, such as PowerPC. Those models are described in Store Buffers and the Total Store Order That Replaces Sequential Consistency and its successors in this cluster.

At the instruction level, a fence is a directive to the implementation to stop reordering across a point. It has no effect on coherence, because coherence was never the problem; it constrains the order in which operations become visible relative to other operations. The cost model of a fence is therefore entirely about draining queues and waiting for acknowledgements, which is What a Fence Instruction Actually Does to the Pipeline.

At the compiler level, the language memory model decides what reordering the optimiser may perform before the hardware ever sees the code. A compiler that moves a non-atomic load across a store because the two do not alias has broken the program’s ordering regardless of what the fences in the emitted code say.

The three layers compose, and the composition is not commutative in cost. Ordering that the compiler can establish statically is free at run time. Ordering that requires a hardware fence costs the pipeline drain. Ordering that requires a locked read-modify-write costs an interconnect round trip. Choosing the weakest sufficient ordering at each layer is the whole craft.

Coherence traffic is not a consistency violation

A frequent misreading of coherence protocols assigns them responsibility for ordering they do not provide, or blames them for behaviour that is actually correct. Three cases are worth separating.

Stale reads during invalidation. A core reads a line, then another core writes it. The first core’s copy is invalidated, and its next read misses and fetches the new value. Between the write and the invalidation, the first core could have read the old value; that is legal and is exactly what coherence permits. It is not a bug, and no amount of fencing in the reader’s code prevents it. Only a synchronisation operation that establishes a happens-before edge does.

Write propagation delay. A store becomes visible to other cores at some later time, measured in interconnect latency rather than cycles. A program that writes a flag and immediately expects another core to have observed it is relying on propagation timing, which no model guarantees. The flag pattern requires the store to be ordered before the reader’s subsequent load, which is a fence or a release store, not a coherence property.

Non-atomic wide accesses. A 16-byte store compiled to two 8-byte stores is not atomic even though each half is. Coherence serialises each half independently, and another core can observe the first half without the second. This is why lock-free algorithms restrict themselves to the machine’s guaranteed atomic width, and why a structure whose fields are updated together needs a seqlock, a version counter, or a lock rather than an assumption that the two stores land together.

A coherence protocol can also be correct while permitting a specific pathology: a line ping-pongs between two cores that both write it repeatedly, because each write invalidates the other’s copy. That is a performance failure with no correctness component, and it is addressed by reducing sharing or by padding, not by changing the memory model.

The layering that keeps each part tractable

The reason the split persists in every commercial design is that each layer can be verified against its own specification. A coherence protocol is checked against the per-location rules, typically by model checking the state machine for all reachable transitions and by asserting that no two caches hold a line in a state combination that would allow divergent values. A memory model is checked against litmus tests, which are small enough to enumerate exhaustively. A compiler’s reordering rules are checked against the language’s axiomatic model, which is a set of constraints on the relations between operations in a single execution.

Combining them into one specification would be more honest about the whole system and much harder to verify, because the state space multiplies. The layered arrangement lets a coherence bug be found without reasoning about fences and lets a fence bug be found without reasoning about line states.

The practical upshot for a programmer is a rule of thumb worth stating plainly: coherence gives per-address sanity, and nothing else. Any claim that spans two addresses, or a flag and the data it guards, needs an ordering edge that coherence does not supply. The edge comes from an atomic operation with acquire or release semantics, and its cost is the subject of Acquire and Release as One-Way Ordering Constraints.