Cache Coherence

This property guarantees that a write operation to a memory location by one processor will eventually become visible to all other processors. It prevents processors from reading stale data from their private caches after an update has occurred elsewhere in the system. Coherence protocols implement this through invalidation or update messages that are broadcast or sent to sharers of the cache line.

• Invalidation-based protocols: Mark other copies as invalid, forcing a miss on the next read.
• Update-based protocols: Propagate the new data value directly to all other caches holding the line.

Also known as write ordering, this property ensures that all processors observe writes to the same memory location in the same sequential order. If two processors write to the same address, the system must define a global order for those writes. All subsequent reads by any processor must reflect that order. This is critical for implementing synchronization primitives like locks and barriers. The coherence protocol, often in conjunction with the memory consistency model, establishes this global order, typically by serializing writes through a single point of coordination, such as the home directory in a directory-based protocol.

Cache lines are tracked using finite state machines. Common protocols define states like:

• Modified (M): The cache holds the only valid copy and the data is dirty (different from main memory).
• Exclusive (E): The cache holds the only valid copy, but it is clean (matches main memory).
• Shared (S): The cache holds a valid, clean copy, but other caches may also hold it.
• Invalid (I): The data in the cache line is stale and cannot be used.
• Owned (O): (MOESI) The cache holds a dirty copy and is responsible for supplying it to other caches, but other caches may hold it in Shared state.

Transitions between these states are triggered by local processor operations (read, write) and coherence messages from other caches or the directory.

These are the two primary architectural approaches to implementing coherence.

• Snooping (Bus-Based): All caches monitor (snoop) a shared broadcast interconnect (e.g., a bus) for transactions. When a write is seen, caches invalidate or update their local copies. This is simple but does not scale well to many cores due to broadcast traffic.
• Directory-Based: A centralized or distributed directory tracks which caches hold copies of each memory block. On a write, point-to-point messages are sent only to the caches that actually hold the data (the sharers). This scales to large core counts (dozens to hundreds) used in modern servers and NPUs, as it avoids broadcast storms.

A major performance pitfall where two unrelated variables reside on the same cache line. If different processors write to these different variables, the coherence protocol treats it as a write to the same address, causing unnecessary invalidation traffic and cache line ping-pong. This severely degrades performance even though the processors are not logically sharing data. Mitigation involves padding data structures or aligning variables to cache line boundaries to ensure they occupy separate lines.

Cache coherence and memory consistency are separate but related concepts. Coherence defines the behavior of reads and writes to a single memory location. Consistency (e.g., Sequential Consistency, Total Store Order, Release Consistency) defines the observable order of reads and writes to different memory locations across threads.

A system can be coherent but not sequentially consistent. For example, writes to different addresses by one processor may be observed in different orders by other processors, even though each individual location's history is coherent. The coherence protocol must provide the necessary guarantees (like write serialization) that the chosen consistency model relies upon.

A memory consistency model defines the formal rules for the order in which memory operations (loads and stores) from different threads become visible to each other in a shared memory system. It provides the programmer's contract with the hardware. Cache coherence is a specific protocol that implements a particular consistency model (often sequential consistency) by ensuring all caches see a consistent view of memory. Weaker models (e.g., release consistency) allow for higher performance but require explicit programmer synchronization.

Atomic operations are indivisible read-modify-write instructions (e.g., fetch-and-add, compare-and-swap) that complete without interruption from other threads. They are a fundamental building block for lock-free and wait-free algorithms. Cache coherence protocols are essential for implementing atomic operations correctly across a multi-processor system, as they ensure the atomic instruction's effect is globally visible and ordered relative to other operations on the same memory location.

A memory barrier (or memory fence) is a low-level instruction that enforces ordering constraints on memory operations issued before and after the barrier. In systems with weak memory consistency models, barriers are required to make shared writes visible and ensure correct synchronization. They interact directly with the cache coherence protocol, often forcing cache line flushes or invalidations to ensure a consistent global memory state is observed by all processors.

NUMA is a multiprocessor architecture where memory access time depends on the memory location's physical proximity to the processor. Each processor has local, fast memory, but can also access slower remote memory attached to other processors. Cache coherence in NUMA systems (CC-NUMA) is more complex and costly, as maintaining consistency for remote cache lines requires communication across an interconnect, making data placement and migration critical for performance.

A data race is a critical concurrency bug that occurs when two or more threads in a process access the same memory location concurrently, at least one access is a write, and the accesses are not ordered by proper synchronization (e.g., locks, atomics). While cache coherence ensures all processors see a consistent final value, it does not prevent races; it merely defines the order in which conflicting writes become visible. Races lead to undefined, non-deterministic program behavior.

The MESI protocol is a specific, widely implemented cache coherence protocol that defines four states for each cache line: Modified (M), Exclusive (E), Shared (S), and Invalid (I). It uses these states and a snooping or directory-based mechanism to track ownership and manage updates. For example, a write to a line in the Shared state requires invalidating all other copies, transitioning it to Modified. This protocol minimizes unnecessary bus traffic while ensuring consistency.