Cache Coherence Protocols are hardware mechanisms that ensure all processors in a shared-memory multiprocessor system observe a consistent view of memory by coordinating cache line states across private caches — without coherence protocols, one processor's cached copy of data could become stale when another processor modifies the same memory location.
The Coherence Problem:
- Private Caches: each processor core has private L1/L2 caches for low-latency access — when multiple cores cache the same memory address, modifications by one core must be visible to all others
- Write Propagation: a write to a shared location must eventually become visible to all processors — coherence ensures that reads always return the most recent write
- Write Serialization: all processors must observe writes to the same location in the same order — prevents inconsistent views of memory state
- False Sharing: when two processors modify different variables that happen to reside on the same cache line (typically 64 bytes), the coherence protocol forces unnecessary invalidations — a significant performance pitfall
MESI Protocol:
- Modified (M): the cache line has been modified and is the only valid copy — the cache is responsible for writing back the data before another processor can access it
- Exclusive (E): the cache line is unmodified and is the only cached copy — can be silently promoted to Modified on a write without bus transaction (important optimization over MSI)
- Shared (S): the cache line is unmodified and may exist in other caches — a write requires an invalidation broadcast to transition to Modified
- Invalid (I): the cache line is not valid — any access requires fetching the line from another cache or main memory
MOESI and MESIF Extensions:
- Owned (O) in MOESI: the cache holds a modified copy that is shared with other caches — the owning cache supplies the data on requests instead of main memory, reducing memory bandwidth (used by AMD processors)
- Forward (F) in MESIF: designates one shared copy as the supplier for future requests — prevents all shared copies from responding simultaneously, reducing bus traffic (used by Intel processors)
- State Transitions: each memory operation (read, write, eviction) triggers a state transition that may involve bus transactions — the protocol's efficiency depends on minimizing these transactions
Snooping Protocols:
- Bus-Based Snooping: all cache controllers monitor (snoop) the shared bus for memory transactions — when a cache detects a relevant transaction, it updates its state accordingly
- Write-Invalidate: on a write, the writing cache broadcasts an invalidation to all other copies — other caches mark their copies as Invalid and must fetch the updated version on next access
- Write-Update (Dragon Protocol): on a write, the new value is broadcast to all shared copies — reduces read miss latency but consumes more bus bandwidth than write-invalidate
- Scalability Limitation: snooping requires all caches to observe all bus transactions — practical limit is 8-16 cores before bus bandwidth becomes a bottleneck
Directory-Based Protocols:
- Directory Structure: a centralized or distributed directory tracks which caches hold copies of each memory block — eliminates the need for broadcast by sending targeted messages only to relevant sharers
- Bit Vector: directory entry contains one bit per processor indicating whether that processor caches the line — scales to hundreds of processors but directory storage grows as O(N × M) where N is processors and M is memory blocks
- Coarse Directory: reduces storage by tracking groups of processors rather than individual ones — sacrifices precision (invalidates entire groups) for reduced memory overhead
- NUMA Integration: directory-based coherence naturally integrates with Non-Uniform Memory Access architectures — the directory is distributed across memory controllers, with local lookups for local memory and remote requests for remote memory
Performance Impact:
- Coherence Traffic: in a 64-core system running a shared-data workload, coherence messages can consume 30-50% of interconnect bandwidth — optimizing data layout to minimize sharing reduces this overhead
- False Sharing Mitigation: padding data structures to cache line boundaries (64 bytes) prevents false sharing — __attribute__((aligned(64))) or alignas(64) in C/C++ ensures each variable occupies its own cache line
- Read-Write Asymmetry: read sharing is cheap (multiple Shared copies coexist), but write sharing is expensive (requires invalidation) — designing data structures for reader-writer separation dramatically reduces coherence traffic
- Coherence Latency: an L1 cache hit takes 1-4 cycles, but a cache-to-cache transfer for a coherence miss takes 20-100 cycles depending on interconnect topology — minimizing sharing reduces average memory access time
Cache coherence is invisible to most programmers but fundamentally shapes the performance of parallel software — understanding the underlying protocol helps explain why some parallel data structures scale linearly while others hit performance walls at just a few cores.