Cache Coherence Protocols
Multi-Core & Coherence · CPU Architectures track
7 min read
In this module
Keeping Caches Consistent
When multiple cores have private caches, a straightforward problem lurks: if Core A writes to a location cached by Core B, Core B's copy is now stale. Cache coherence protocols fix this — ensuring all cores see a consistent view of memory even as each one caches independently.
The MESI Protocol
MESI is the foundational cache coherence protocol. Each cache line is in one of four states:
Modified (M): this cache has the only copy, and it has been modified (dirty). Main memory is out of date. This cache is responsible for writing the data back before it can be evicted.
Exclusive (E): this cache has the only copy, but it has not been modified (clean). The data matches main memory. The cache can transition to Modified on a write without notifying anyone.
Shared (S): multiple caches may hold this line, and all copies match main memory. The line is read-only. A write requires sending invalidation messages to all other holders.
Invalid (I): this cache line is not valid (empty or invalidated). Any access requires fetching from another cache or memory.
State Transitions
The MESI state machine responds to two types of events: actions by the local core and snooped transactions from other cores.
A key optimisation in MESI is the Exclusive state. When only one cache holds a line in Exclusive, it can write to that line without any bus transaction (transitioning silently from Exclusive to Modified). Without the Exclusive state (as in the simpler MSI protocol), every write to a clean cache line would require a bus transaction to check if other caches have copies. The Exclusive state eliminates this unnecessary traffic for the common case of unshared data.
Drive the state machine yourself. The scripted button plays a counter ping-ponging between two cores: each one writes the same line in turn, so every write after the first drags the line across with a BusRdX and a flush. Then press Reset and try something kinder: Core 0 reads, Core 1 reads, and both read again. Count the bus transactions in each case. (This version sends BusRdX for every write that needs ownership; some real designs send a lighter upgrade message when the writer already holds a Shared copy.)
Ping-pong a counter
One cache line, one snooping bus. Read or write from any core and watch every cache react.
Every cache starts Invalid. Pick a core and read or write.
MOESI and MESIF Extensions
MOESI (AMD): adds an Owned (O) state. When a Modified line is snooped for reading, instead of writing back to memory and going to Shared, the line transitions to Owned. The owning cache supplies the data to the requester directly (cache-to-cache transfer), and the requester gets a Shared copy. The Owned cache is responsible for the write-back, but memory is not updated yet. This avoids unnecessary memory writes when data is actively shared between cores.
MESIF (Intel): adds a Forward (F) state. When multiple caches hold a Shared line and another core requests it, only the cache in Forward state responds (instead of all Shared caches or memory). This reduces duplicate responses and interconnect traffic.
Snooping vs Directory-Based Coherence
Snooping protocols broadcast every coherence transaction on a shared bus; every cache controller eavesdrops and checks whether it holds the relevant line. Simple, low-latency for small core counts, but the bus turns into a bottleneck as cores multiply.
Directory-based protocols keep a distributed directory — each memory controller tracks which caches hold which lines. When a core needs to invalidate or share a line, it queries the directory and sends messages only to caches that actually hold it. More bookkeeping, but the traffic scales far better.
Modern multi-core designs use hybrid approaches: snooping within a core complex (where core counts are small) and directory-based coherence between complexes and between sockets.
Coherence Traffic and Performance
Cache coherence is not free. Every write to shared data generates invalidation messages. Every read of recently-written data may require a cache-to-cache transfer. This coherence traffic consumes interconnect bandwidth and adds latency.
The performance impact depends on the sharing pattern:
- No sharing (thread-local data): zero coherence overhead
- Read sharing (multiple readers, rare writes): minimal overhead (data stays Shared)
- Write sharing (frequent writes from multiple cores): heavy overhead (constant invalidation and transfer)
False sharing - where two cores write to different variables on the same cache line - generates coherence traffic equivalent to true sharing but with no logical data dependency. Giving each frequently-written variable its own cache line eliminates false sharing. That usually means 64-byte alignment on x86, but Apple's M-series chips use 128-byte lines, and Intel's adjacent-line prefetcher fetches lines in pairs, so many libraries pad to 128 bytes to be safe.
The runner can't start threads, so here's the next best thing: a two-core MESI simulator. Each core increments its own counter 1,000 times, taking turns. Predict how many invalidations each layout causes before you run it.
On the shared line, nearly every increment forces an invalidation and a cache-to-cache transfer of the dirty line, even though the two counters never interact. Padded apart, each line settles in Modified in its own cache and the interconnect goes quiet. On real hardware with two threads, that difference typically shows up as a several-fold slowdown for the shared layout.
Practical Implications
For programmers: minimise writes to shared data, pad per-thread data to avoid false sharing, use read-write locks to allow concurrent reading, and be aware that atomic operations (CAS, fetch-and-add) generate coherence traffic on every invocation. Profile coherence-related events using hardware performance counters (on Intel, perf stat -e l2_rqsts.all_rfo counts Requests For Ownership, which indicate writes to shared lines; AMD and ARM name their events differently, and perf c2c finds contended lines on any of them) to identify sharing bottlenecks.