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

<svg viewBox="0 0 760 470" xmlns="http://www.w3.org/2000/svg" font-family="-apple-system,Segoe UI,Roboto,sans-serif">
  <rect x="0" y="0" width="760" height="470" fill="#0d1117"/>
  <text x="380" y="28" fill="#e6edf3" font-size="21" font-weight="700" text-anchor="middle">Cache Coherence — MESI Protocol</text>
  <text x="380" y="48" fill="#8b98a5" font-size="12" text-anchor="middle">hardware ensures all cores see consistent memory — every cache line is in one of 4 states</text>

  <!-- MESI state diagram -->
  <rect x="30" y="65" width="430" height="310" rx="6" fill="#080d14" stroke="#233043" stroke-width="1"/>
  <text x="245" y="86" fill="#e6edf3" font-size="11" font-weight="600" text-anchor="middle">MESI State Machine</text>

  <!-- Modified -->
  <circle cx="150" cy="150" r="35" fill="#0b1220" stroke="#f87171" stroke-width="1.5"/>
  <text x="150" y="147" fill="#fca5a5" font-size="11" font-weight="700" text-anchor="middle">M</text>
  <text x="150" y="162" fill="#f87171" font-size="7" text-anchor="middle">Modified</text>

  <!-- Exclusive -->
  <circle cx="330" cy="150" r="35" fill="#0b1220" stroke="#34d399" stroke-width="1.5"/>
  <text x="330" y="147" fill="#6ee7b7" font-size="11" font-weight="700" text-anchor="middle">E</text>
  <text x="330" y="162" fill="#34d399" font-size="7" text-anchor="middle">Exclusive</text>

  <!-- Shared -->
  <circle cx="330" cy="290" r="35" fill="#0b1220" stroke="#60a5fa" stroke-width="1.5"/>
  <text x="330" y="287" fill="#93c5fd" font-size="11" font-weight="700" text-anchor="middle">S</text>
  <text x="330" y="302" fill="#60a5fa" font-size="7" text-anchor="middle">Shared</text>

  <!-- Invalid -->
  <circle cx="150" cy="290" r="35" fill="#0b1220" stroke="#6b7684" stroke-width="1.5"/>
  <text x="150" y="287" fill="#8b98a5" font-size="11" font-weight="700" text-anchor="middle">I</text>
  <text x="150" y="302" fill="#6b7684" font-size="7" text-anchor="middle">Invalid</text>

  <!-- Transitions -->
  <!-- I → E (read miss, no sharers) -->
  <path d="M175,265 L305,175" fill="none" stroke="#34d399" stroke-width="1" marker-end="url(#arrowG)"/>
  <text x="230" y="210" fill="#34d399" font-size="6.5">read miss</text>
  <text x="230" y="220" fill="#34d399" font-size="6">(no sharers)</text>

  <!-- I → S (read miss, sharers exist) -->
  <path d="M185,290 L295,290" fill="none" stroke="#60a5fa" stroke-width="1"/>
  <polygon points="293,287 299,290 293,293" fill="#60a5fa"/>
  <text x="240" y="284" fill="#60a5fa" font-size="6.5">read miss (sharers)</text>

  <!-- E → M (local write) -->
  <path d="M295,145 L185,145" fill="none" stroke="#f87171" stroke-width="1"/>
  <polygon points="187,148 181,145 187,142" fill="#f87171"/>
  <text x="240" y="138" fill="#f87171" font-size="6.5">local write</text>

  <!-- S → I (remote write / snoop invalidate) -->
  <path d="M305,318 L175,318" fill="none" stroke="#6b7684" stroke-width="1"/>
  <polygon points="177,321 171,318 177,315" fill="#6b7684"/>
  <text x="240" y="332" fill="#6b7684" font-size="6.5">snoop invalidate</text>

  <!-- M → I (remote read) -->
  <path d="M150,185 L150,255" fill="none" stroke="#6b7684" stroke-width="1"/>
  <polygon points="147,253 150,259 153,253" fill="#6b7684"/>
  <text x="115" y="220" fill="#6b7684" font-size="6">flush +</text>
  <text x="115" y="230" fill="#6b7684" font-size="6">invalidate</text>

  <!-- E → S (remote read) -->
  <path d="M340,185 L340,255" fill="none" stroke="#60a5fa" stroke-width="1"/>
  <polygon points="337,253 340,259 343,253" fill="#60a5fa"/>
  <text x="360" y="220" fill="#60a5fa" font-size="6">remote read</text>

  <!-- State descriptions (right) -->
  <rect x="480" y="65" width="250" height="310" rx="6" fill="#080d14" stroke="#233043" stroke-width="1"/>
  <text x="605" y="86" fill="#e6edf3" font-size="10" font-weight="600" text-anchor="middle">State Meanings</text>

  <text x="500" y="112" fill="#f87171" font-size="9" font-weight="600">M (Modified):</text>
  <text x="500" y="128" fill="#8b98a5" font-size="8">only copy, dirty (not in memory)</text>
  <text x="500" y="142" fill="#6b7684" font-size="7.5">must write back before sharing</text>

  <text x="500" y="166" fill="#34d399" font-size="9" font-weight="600">E (Exclusive):</text>
  <text x="500" y="182" fill="#8b98a5" font-size="8">only copy, clean (matches memory)</text>
  <text x="500" y="196" fill="#6b7684" font-size="7.5">can write without bus transaction</text>

  <text x="500" y="220" fill="#60a5fa" font-size="9" font-weight="600">S (Shared):</text>
  <text x="500" y="236" fill="#8b98a5" font-size="8">multiple copies exist, read-only</text>
  <text x="500" y="250" fill="#6b7684" font-size="7.5">must invalidate others before writing</text>

  <text x="500" y="274" fill="#6b7684" font-size="9" font-weight="600">I (Invalid):</text>
  <text x="500" y="290" fill="#8b98a5" font-size="8">line not present or stale</text>
  <text x="500" y="304" fill="#6b7684" font-size="7.5">must fetch from memory or peer cache</text>

  <text x="605" y="332" fill="#f59e0b" font-size="8" text-anchor="middle" font-weight="600">MOESI (AMD) adds Owned state</text>
  <text x="605" y="348" fill="#8b98a5" font-size="7.5" text-anchor="middle">dirty but shared — avoids writeback</text>
  <text x="605" y="366" fill="#6b7684" font-size="7.5" text-anchor="middle">Intel uses MESIF (F = Forward)</text>

  <!-- Bottom -->
  <rect x="30" y="388" width="700" height="42" rx="6" fill="#080d14" stroke="#233043" stroke-width="1"/>
  <text x="380" y="407" fill="#8b98a5" font-size="8.5" text-anchor="middle">coherence traffic is the #1 scaling bottleneck in multi-core chips — every write generates snoops to all cores</text>
  <text x="380" y="422" fill="#6b7684" font-size="7.5" text-anchor="middle">directory-based coherence (server chips) replaces broadcast snooping for &gt;16 cores</text>

  <text x="380" y="452" fill="#6b7684" font-size="11" text-anchor="middle">Cache coherence makes shared memory "just work" — but it costs bandwidth, latency, and design complexity.</text>
</svg>

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.