CPU Cache Coherency: How Multi-Core Processors Keep Data Consistent

Executive Summary & Key Takeaways

Imagine a busy architectural studio where eight designers work on different sections of the same building blueprint. Each designer has a personal sketchbook at their desk where they copy over room measurements from the main drafting table in the center of the office. Working from their personal sketchbooks is blazing fast: they can check dimensions in seconds without standing up. But what happens when Designer A changes a load-bearing wall's position in her sketchbook? If Designer B across the room keeps working from his older copy, his calculations will cause the ceiling to collapse.

To prevent catastrophe, the studio enforces a strict communication protocol: before anyone alters a dimension, they must announce the change to the room, requiring everyone else to mark that page in their sketchbook as void. In modern multi-core computing, this mechanism is called CPU cache coherency.

Every modern processor relies on a hierarchy of high-speed local caches (L1 and L2) embedded right next to each CPU core. These caches operate at sub-nanosecond speeds (around 1 to 3 nanoseconds), shielding the execution units from the sluggish performance of main system memory (DRAM), which demands 60 to 100 nanoseconds per trip. However, distributing local copies of memory across dozens of cores introduces a fundamental consistency hazard: multiple cores can simultaneously hold, read, and modify cached copies of the exact same memory address.

• The Single-Writer, Multiple-Reader (SWMR) Invariant: At any point in time, a given 64-byte memory slice (a cache line) can either be read simultaneously by any number of cores, or modified by exactly one core.
• Snooping vs. Directory Topologies: Small systems (4 to 16 cores) snoop on a broadcast bus where every core observes all memory transactions. Larger server platforms (32 to 128+ cores) use directory-based tracking over 2D mesh interconnects, routing messages point-to-point to prevent bus saturation.
• The Cost of Cache Thrashing: When multiple cores compete to write to the same cache line—or unrelated variables packed onto that same line (false sharing)—throughput collapses by 60% to 85% due to serialized interconnect invalidation storms.
• Entropy and Bandwidth Bottlenecks: Hardware performance is bounded by memory interconnect bandwidth, not arithmetic processing power. Low-entropy (predictable, localized) memory access patterns achieve linear multi-core scaling, whereas high-entropy (random, interleaved concurrent) access patterns trigger latency spikes and arbitration stalls.

1. Architectural Foundations & Mechanics

To appreciate why cache coherency exists, consider the staggering physical speed differences inside modern computer hardware. An execution core running at 4.5 GHz executes an instruction cycle in approximately 0.22 nanoseconds. Reading data from Level 1 (L1) cache takes about 4 to 5 cycles (~1 nanosecond). Level 2 (L2) cache takes roughly 12 to 14 cycles (~3 nanoseconds). The shared Level 3 (L3) or Last-Level Cache (LLC) requires 35 to 50 cycles (~10 to 15 nanoseconds).

In contrast, retrieving data from main system DRAM requires traversing memory controllers, physical buses, and row-column refresh cycles, requiring between 60 and 100 nanoseconds—over 300 wasted CPU cycles. Without caches, our processors would spend 99% of their time stalled, waiting on data.

However, caches do not store isolated single bytes. Instead, memory is fetched, stored, and managed in uniform chunks called cache lines, universally sized at 64 bytes across x86-64 and ARMv8/v9 microarchitectures. When Core 0 reads a single 4-byte integer from address 0x1000, its cache controller loads the entire 64-byte block from 0x1000 to 0x103F into its private L1 data cache.

The Two Formal Coherence Invariants

A memory system is coherent if and only if it guarantees two formal rules across all shared memory locations:

1. Single-Writer, Multiple-Reader (SWMR): For any memory address at any instant in logical time, there may either be a single core with write permission (and zero or more cores waiting), or an arbitrary number of cores with read-only permission, but never both.
2. Write Propagation and Serialization: Changes made by one core must eventually be visible to all other cores, and writes to the same address must be seen in the exact same sequence by every core in the system.

Snooping Protocols vs. Directory Protocols

How do separate physical cores reach consensus on who owns a cache line? Hardware designers use two primary architectures depending on core count:

1. Snooping-Based Coherence

In a snooping architecture, all CPU cores are connected to a shared physical communication medium, such as a multi-drop bus or a high-speed ring. Every cache controller constantly "listens" (snoops) to all transactions broadcast across this channel.

When Core 0 wants to write to a cache line that it only shares as read-only, it broadcasts an Invalidate signal onto the bus. Every other core snooping on the bus inspects the target address. If Core 1 holds a copy, it immediately marks its local cache line as Invalid and sends an acknowledgment. While snooping provides minimal latency for small multi-core processors (typically 4 to 16 cores), it does not scale well to large systems. Because every write broadcasts to every core, bus traffic explodes as an $O(N^2)$ communication pattern, quickly consuming available interconnect bandwidth.

2. Directory-Based Coherence

To scale to 32, 64, or 128+ cores on server platforms (like AMD EPYC or Intel Xeon scalable processors), systems discard broadcast snooping in favor of point-to-point networks (such as 2D tori or meshes) managed by a coherence directory.

The directory acts as a centralized or distributed clearinghouse. For every memory block, the directory maintains a state bitmask identifying exactly which cores currently hold a copy of that line. When Core 0 wants to modify a line, it does not scream across a shared bus. Instead, it sends a targeted message to the specific directory slice (home node) responsible for that physical address.

The directory looks up its tracking bitmask and sends targeted point-to-point invalidation messages only to the specific cores that currently hold that line. Once those cores acknowledge the invalidation, the directory grants exclusive ownership to Core 0. This reduces message complexity to $O(K)$, where $K$ is the number of actual sharers rather than the total core count $N$.

The Evolution of State Machines: MSI, MESI, and MOESI

Every cache line stored inside an L1 or L2 cache contains tag bits representing its physical address, along with status bits that encode its current state within a finite-state machine.

The Foundational MESI Protocol

The industry-standard baseline protocol is MESI (also known as the Illinois protocol). It uses four discrete states:

• Modified (M): The cache line is present only in the current core's cache and is dirty—meaning its contents have been altered and no longer match the backup data in main memory. The local core holds exclusive read and write permissions.
• Exclusive (E): The cache line is present only in the current core's cache, but it is clean—meaning its contents match main memory exactly. The core can read immediately, and it can silently transition to Modified on a write without issuing a bus invalidation, because no other core holds a copy.
• Shared (S): The cache line may be present in multiple cores' caches simultaneously. It is clean with respect to main memory. Cores have read-only permission. Any write requires broadcasting an invalidation request to revoke other cores' shared copies.
• Invalid (I): The cache line does not contain valid data. Reading from or writing to this line results in a cache miss, requiring a bus or directory transaction.

The MOESI Protocol and Dirty Sharing

While MESI is effective, it has an inefficiency: if Core 0 has a line in the Modified state and Core 1 requests to read that same line, Core 0 must flush its modified data all the way back to main DRAM before Core 1 can read it, after which both transition to Shared. Writing to DRAM costs valuable time and bandwidth.

The MOESI protocol (common in AMD architectures) solves this by introducing a fifth state: Owner (O).

The Owner state represents a line that is both dirty (modified relative to DRAM) and shared across multiple cores. When Core 1 requests a read, Core 0 provides the updated data directly over the internal interconnect without touching DRAM. Core 0 transitions from Modified to Owner, while Core 1 enters the Shared state. Core 0 (the Owner) retains the duty of eventually writing the dirty data back to DRAM whenever the line is evicted.

Extending Coherence Beyond the CPU: Heterogeneous CXL and NVLink

In modern machine learning and high-performance computing, the boundary of cache coherency has expanded past CPU sockets to include GPUs, TPUs, and FPGA accelerators. Technologies such as Compute Express Link (CXL.cache / CXL.mem) and NVIDIA NVLink / C2C (Chip-to-Chip) allow CPUs and discrete accelerators to share a unified, hardware-coherent physical address space.

Instead of requiring expensive kernel driver interventions, PCIe DMA copies, and serialization barriers between host memory and accelerator memory, coherent interconnects allow an accelerator's tensor cores to access host memory lines directly. If a GPU thread updates a tensor buffer, the CPU's hardware coherence directory handles the invalidation seamlessly, eliminating software serialization bottlenecks.

2. Mathematical Modeling & Resource Bounds

Hardware engineers evaluate cache coherence systems by measuring their memory consumption, message overhead, and effective latency under varying access patterns.

1. Coherence Directory Memory Overhead

While directory-based protocols eliminate the bus broadcast bottleneck, they require dedicated on-chip SRAM to store the tracking bitmasks. We can calculate the total memory overhead of a full-bitvector directory system using the following formula:

$S_{\text{dir}} = N_{\text{lines}} \times \left( N_{\text{cores}} + \lceil \log_2(S_{\text{states}}) \rceil \right) \text{ bits}$

Where:

• $N_{\text{lines}}$ is the total number of tracked 64-byte cache lines in the system (determined by total cache capacity divided by 64 bytes).
• $N_{\text{cores}}$ is the number of cores tracked in the sharing bitmask vector (each bit indicates whether that specific core shares the line).
• $S_{\text{states}}$ is the count of protocol states (for example, MOESI has 5 states, requiring $\lceil \log_2(5) \rceil = 3$ state bits).

Real-World Resource Bound: Consider a modern 64-core processor equipped with a combined 128 MB of cache.

• $N_{\text{lines}} = \frac{128 \times 1024 \times 1024}{64} = 2,097,152 \text{ cache lines}$.
• With 64 cores and 3 state bits, each entry requires $64 + 3 = 67 \text{ bits}$ (approximately 8.375 bytes).
• Total directory SRAM footprint: $2,097,152 \times 67 \text{ bits} \approx 17.56 \text{ Megabytes}$.

This reveals an important engineering trade-off: spending nearly 14% of equivalent cache area purely on directory metadata is the price paid to avoid interconnect message storms.

2. Average Memory Access Time (AMAT) Under Coherence Contention

In a single-core environment, the Average Memory Access Time depends simply on local hit rates and memory latency:

$\text{AMAT}_{\text{single}} = T_{\text{L1\_hit}} + (1 - H_{\text{L1}}) \times T_{\text{L1\_miss\_penalty}}$

In a multi-core coherent system, a cache miss is no longer a simple fetch from DRAM. It must account for coherence states, remote cache lookups, and directory arbitration stalls:

$\text{AMAT}_{\text{multi}} = T_{\text{L1}} + M_{\text{L1}} \left( T_{\text{L2}} + M_{\text{L2}} \left( T_{\text{LLC}} + P_{\text{remote}} \cdot T_{\text{coherence\_stall}} + P_{\text{dram}} \cdot T_{\text{dram}} \right) \right)$

Where:

• $T_{\text{L1}}, T_{\text{L2}}, T_{\text{LLC}}$ are the hit latencies of the respective cache tiers (~1ns, ~3ns, ~12ns).
• $M_{\text{L1}}, M_{\text{L2}}$ are the miss rates at each cache tier (typically $0.05$ to $0.15$).
• $P_{\text{remote}}$ is the probability that the requested line is held in a Modified or Owner state in another core's private cache.
• $T_{\text{coherence\_stall}}$ is the round-trip interconnect latency required to force the remote core to invalidate or downgrade its line and transfer the dirty payload (~40 to 80ns on a single socket; ~150 to 250ns across NUMA sockets).

3. Low-Entropy vs. High-Entropy Throughput Divergence

A frequent mystery in multi-threaded programming is why an algorithm that runs with near-perfect speedup across 4 cores can hit a performance wall when scaled to 32 or 64 cores. The root cause is the information entropy of memory access patterns.

Let the address distribution of memory write operations across cores be represented as a discrete random variable $X$ with probability distribution $P(X)$. The access entropy is:

$H(X) = -\sum_{i=1}^{K} p_i \log_2(p_i)$

• Low-Entropy Access (Predictable & Localized): When threads access disjoint, private memory regions or perform read-dominated workloads, $H(X)$ is low. Cache lines remain in the Exclusive or Shared states. Coherence invalidation traffic approaches zero, and aggregate execution throughput scales linearly ($O(N)$) with core count.
• High-Entropy Access (Scattered & Interleaved): When multiple threads unpredictably write to overlapping memory regions or shared counters, $H(X)$ is high. The exact same cache line must ping-pong between competing cores. Each write forces the owning core to transition the line to Invalid in all other caches.

Under high-entropy access, interconnect queues fill up, forcing execution pipelines into arbitration backoff states. As profiled on systems with high memory concurrency, total throughput collapses by 60% to 85% compared to linear projections. The system becomes completely bound by interconnect coherence bandwidth rather than raw processor math capabilities.

3. Memory Allocation Architectures: Contiguous vs. Segmented

How memory buffers are laid out in software directly dictates how the underlying hardware cache coherence engine performs. Developers often debate whether to organize high-concurrency buffers as flat contiguous arrays, segmented arena chunks, or dynamically allocated node structures.

The table below compares these approaches from a cache-coherence and hardware-efficiency perspective: