cache coherence protocol
**Cache Coherence Protocols** are the **hardware mechanisms that maintain a consistent view of memory across multiple caches in a multiprocessor system**, ensuring that when one processor modifies a cached copy of data, all other processors observe the update — preventing stale data reads that would cause program correctness failures.
The fundamental problem: in a multiprocessor with private L1/L2 caches, multiple processors may cache copies of the same memory location. Without coherence, processor A writing to location X might not be visible to processor B reading the same location from its own cache.
**MESI Protocol States** (the baseline protocol for most implementations):
| State | Meaning | Permissions | Copies |
|-------|---------|------------|--------|
| **Modified (M)** | Dirty, exclusive | Read + Write | Only copy |
| **Exclusive (E)** | Clean, exclusive | Read + Write (silent upgrade) | Only copy |
| **Shared (S)** | Clean, shared | Read only | Multiple copies |
| **Invalid (I)** | Not valid | None | N/A |
**Protocol Extensions**: **MOESI** (AMD) adds Owned state — dirty shared, allowing forwarding without writeback to memory; **MESIF** (Intel) adds Forward state — designates one sharer as the responder to avoid duplicate responses; **CHI** (ARM) is a more elaborate protocol with additional transient states for the AMBA coherent hierarchy.
**Snooping Protocols**: Each cache monitors (snoops) bus transactions. When processor A writes to a shared line, the write is broadcast on the bus, and all caches holding that line invalidate their copies (write-invalidate) or update them (write-update). **Advantages**: low latency (bus broadcast is fast), simple implementation. **Limitations**: broadcast doesn't scale beyond ~8-16 cores (bus bandwidth saturated). Used in: Intel's ring-based multi-core designs for small core counts.
**Directory Protocols**: A directory (centralized or distributed) tracks which caches hold copies of each memory line. On a write, the directory sends targeted invalidations only to caches holding copies — no broadcast needed. **Advantages**: scales to hundreds of cores. **Disadvantages**: higher latency (indirection through directory), storage overhead (directory entry per cache line, tracking sharers via bit vector or limited pointer scheme). Used in: AMD EPYC (infinity fabric), ARM CMN-700, Intel mesh interconnect.
**Coherence Traffic Patterns**: **True sharing** — multiple threads legitimately access the same data (requires synchronization). **False sharing** — threads access different data that happens to share a cache line, causing unnecessary invalidation traffic. False sharing is a major performance pitfall: two threads writing adjacent elements in the same 64-byte cache line generate continuous invalidation traffic, degrading performance by 10-100x. Solution: pad data structures to cache-line boundaries.
**Scalability Challenges**: Coherence traffic grows with core count. Mitigations: **inclusive vs. exclusive cache hierarchies** (inclusive LLC acts as snoop filter, reducing coherence traffic), **snoop filters** (track cached lines to suppress unnecessary snoops), **region-based coherence** (track coherence at coarser granularity — 1KB regions instead of 64B lines), and **non-coherent domains** (accelerators with software-managed coherence to avoid hardware overhead).
**Cache coherence protocols are the invisible foundation of shared-memory multiprocessing — every correct execution of a multi-threaded program depends on the coherence hardware silently maintaining the illusion that all processors share a single, consistent memory, despite each having private caches.**