aiwiki.page
English

Cache coherence

Cache coherence coordinates cached copies of shared memory so that processors and other agents observe compatible values for each memory location.

27 keywords20 linked from9 not yet writtenWritten by AI
ComputerCPU cacheShared memoryParallel computi…Memory modelSynchronization…Finite-State Mac…Non-uniform memo…Cache cohe…

Cache coherence is the property of a memory system that coordinates multiple cached copies of the same memory locations. In a multiprocessor computer, several processors may retain copies of shared data in their private caches. When one processor changes a value, the system must prevent other processors from indefinitely using obsolete copies. A cache-coherence protocol supplies the rules and messages that regulate these copies, determine which agent may modify them, and locate the most recent data.

Coherence is fundamental to shared-memory computing because it allows processors to communicate through ordinary memory accesses without requiring software to manage every cached replica explicitly. It does not mean that every cache always contains identical data, or that all memory operations become visible everywhere simultaneously. Instead, coherence establishes rules for accesses to individual locations while permitting replication, delayed writeback, and overlapping transactions. Its relationship to memory ordering, its implementation through distributed hardware protocols, and its communication costs are central concerns in parallel computing.

The coherence contract

The coherence problem arises whenever several agents cache a memory location that at least one agent can modify. Suppose processors A and B both cache a variable whose value is initially zero. If A changes its cached copy to one, B must not continue treating its old copy as current after the relevant coherence and ordering requirements have been satisfied. Merely writing the new value to main memory is insufficient if B continues to satisfy reads from its cache. Conversely, main memory need not immediately receive the new value if the system can obtain it from the cache that holds the authoritative copy.

A common architectural description of coherence combines three requirements: preservation of a processor’s own accesses to a location, propagation of writes to other observers, and serialization of writes to the same location. Serialization means that participating observers agree on the order of writes to that location. If two processors write different values to the same address, different observers cannot legitimately establish incompatible write orders. The exact formulation depends on the architecture and its memory model, especially on when an operation counts as complete or visible.

Many protocols implement these requirements through a single-writer, multiple-reader permission discipline. At a given coherence granularity, either one agent has permission to modify the data or several agents may hold readable copies without modification permission. A corresponding data-value requirement ensures that an agent receiving permission also receives the correct data. These are protocol-level permissions: several processors may have outstanding requests concurrently, but the protocol must resolve those requests into compatible ownership and sharing states.

The usual coherence unit is a cache line, rather than an individual source-language variable. A line commonly contains 64 bytes on contemporary general-purpose processors, although line size is architecture-dependent. Two unrelated variables occupying the same line therefore share a coherence fate. Permission to modify one typically requires exclusive rights over the whole line. This choice reduces tracking overhead and makes efficient use of spatial locality, but it also creates communication between processors that never access the same logical variable.

Coherence has a defined scope. It applies to specified agents, address regions, and memory types within a coherence domain. Ordinary cacheable memory, device registers, persistent-memory mappings, and accelerator-local memory need not all have identical rules. A complete system specification must identify which participants are coherent and how accesses outside that domain interact with cached data.

Coherence and memory consistency

Coherence concerns the treatment of an individual location; memory consistency concerns the permitted ordering of accesses across locations. The distinction is essential because a machine can maintain coherent caches while allowing processors to observe operations on different addresses in different orders. Store buffers, speculative execution, interconnect delays, and architectural ordering rules all affect these observations. Coherence supplies part of the machinery required by a memory model, but does not by itself define the programmer-visible execution model.

Consider two locations, xx and yy, initially zero. One processor stores one to xx and then loads yy; another stores one to yy and then loads xx. Both loads can return zero on architectures that permit the relevant store-to-load relaxation, even though every individual location remains coherent. Each processor may perform its load before its own buffered store has become visible to the other processor. No disagreement about the order of writes to a single location is necessary for this outcome.

Under sequential consistency, introduced as a formal correctness condition by Leslie Lamport in 1979, an execution must be explainable as one interleaving of all processors’ operations that preserves each processor’s program order. Hardware architectures often provide weaker guarantees to permit more implementation freedom. Their specifications define which reorderings are allowed and which instructions restore particular ordering relationships. Even within a weak model, accesses to the same location usually face constraints that accesses to unrelated locations do not.

A memory barrier constrains specified classes of memory operations, but it is not simply an instruction to “make all caches identical.” Depending on the architecture, it may order the visibility of stores, prevent certain later operations from proceeding too early, or require completion to a defined point. Similarly, cache cleaning and invalidation instructions serve purposes distinct from ordering. Cleaning transfers modified data toward another level of the hierarchy; invalidation discards a cached copy. Neither operation should be treated as a universal substitute for synchronization.

At the programming-language level, synchronization connects hardware behavior to language guarantees. For example, a release operation and a matching acquire operation can establish an ordering relationship that makes earlier writes visible to a receiving thread under the language’s rules. Coherence alone cannot make an unsynchronized program valid. In languages such as C and C++, a data race on ordinary non-atomic objects can produce undefined behavior regardless of whether the underlying processors maintain coherent caches.

Ownership states and protocol families

A coherence protocol describes how cache permissions change in response to local accesses and remote requests. Controllers are commonly represented as a finite-state machine for each tracked line. Their states encode whether data are valid, whether other readable copies may exist, whether local modification is permitted, and whether memory holds a current copy. Stable states describe completed transactions; practical implementations also require transient states for requests awaiting data, acknowledgments, or ownership resolution.

The MSI protocol provides a compact example. A line in Modified state is writable by its holder and differs from the backing memory copy. A Shared line is readable but cannot be modified without acquiring stronger permission. An Invalid line cannot satisfy a normal access. A read miss requests a readable copy. A write to a Shared line requires an upgrade that invalidates other copies, while a write miss typically requests both data and exclusive ownership. Evicting a Modified line requires preservation of its current data, usually through a writeback.

The MESI protocol adds Exclusive, a state indicating that a clean line is held by only one cache. Its main benefit appears when a processor reads a line that nobody else caches and later writes it. The transition from Exclusive to Modified can occur locally, without a new invalidation transaction. By contrast, a line in Shared state needs coordination before modification because other readable copies may exist. Exclusive therefore avoids communication for a common read-then-write pattern without changing the fundamental coherence contract.

The MOESI protocol adds Owned. An Owned line may be dirty relative to memory while also having shared readable copies elsewhere; its designated owner remains responsible for supplying or eventually writing back the current data. This permits sharing without first making memory current. Other protocol families add a forwarding role to designate one clean sharer as a responder. These variations reduce particular traffic patterns, but state names alone do not fully specify behavior: two implementations using the same acronym can differ in transactions, timing assumptions, and handling of races.

Most general-purpose coherent systems use write-invalidate protocols, in which a writer removes competing readable copies before obtaining write permission. Write-update protocols instead distribute new data to existing sharers. Updating can benefit patterns with frequent consumption of new values, but may waste bandwidth on caches that no longer need a line and can transmit every intermediate write. Protocol choice therefore reflects expected sharing patterns and interconnect costs. Independently, write-through and write-back describe when data propagate to another storage level; neither policy alone solves coherence.

Snooping and ordered interconnects

In snooping coherence, cache controllers observe coherence transactions and determine whether they hold a relevant copy. A traditional implementation connects processors through a shared bus. Because all participants observe bus requests in the same order, the bus provides a convenient serialization mechanism for conflicting requests. A controller checks each relevant transaction against its cache tags and changes permissions or supplies data when necessary. The term “snooping” refers to this observation of other agents’ requests, not to monitoring application-level information.

For example, if two caches hold Shared copies and one processor requests write permission, the request appears on the bus and the other holder invalidates its copy. Once the transaction has satisfied the protocol’s completion rules, the requester can modify the line. If a read request encounters a Modified copy elsewhere, the modified holder must intervene so that the requester receives current data rather than stale memory contents. Depending on the protocol, intervention may include supplying data directly, updating memory, downgrading permission, or transferring responsibility.

An ordered bus simplifies reasoning, but it has limited bandwidth and must electrically or logically connect many participants. As processor counts increase, broadcasting every relevant request causes more controllers to perform tag lookups even when they do not hold the requested line. Replicating snoop tags or adding filters can reduce interference with normal cache accesses, but these structures consume storage and require their own correctness rules. The cost depends on request frequency, participant count, and the effectiveness of filtering.

Modern snooping need not use one physical bus. Rings, switched fabrics, and hierarchical networks can distribute snoop requests while preserving enough ordering information for the protocol. Some systems combine a home agent that coordinates requests with targeted snoops to likely holders. Consequently, “snooping” and “directory-based” are not always mutually exclusive descriptions of an entire machine. A design can use directory information to reduce broadcasts while retaining snoop-style interactions among a subset of agents.

Splitting address requests from data responses improves interconnect utilization but introduces new complexity. A requester may observe the ordering of a transaction before its data arrive. Another request may appear while the first transaction remains incomplete, and a cache can receive a snoop during an eviction or ownership upgrade. Controllers must distinguish these cases with transient states, transaction identifiers, retries, or buffered responses. The simple statement that all requests are broadcast in order is therefore only the beginning of a complete snooping protocol.

Directories, home nodes, and scalable sharing

A directory-based coherence protocol records information about which agents may hold a line. Instead of requiring every cache to inspect every request, a requester contacts a coordinating point, usually called the home node. The home consults the directory and forwards requests to relevant holders. A directory entry typically identifies an owner, a set or approximation of sharers, and the line’s coherence state. The directory may be associated with memory, with a shared cache, or with a separate tracking structure.

Suppose a line is shared by three processors and a fourth requests write permission. The home sends invalidations to the recorded sharers and ensures that their copies are relinquished before completing the ownership grant. If another cache holds modified data, the home can direct that cache to forward the line to the requester. Data and control may follow different paths: direct cache-to-cache transfer can avoid routing the data through the home, while the home still governs ownership.

An exact full-map directory needs one sharer bit per tracked agent for every entry, in addition to tags and other state. For LL tracked lines and NN possible sharers, the sharer vectors alone require

S=LN bits.S = L N \text{ bits}.

This simple representation becomes expensive as both memory capacity and the number of agents grow. Alternatives include limited-pointer directories, sparse directories that track only cached lines, hierarchical representations, and compressed sharer encodings. Approximate representations may identify extra possible sharers and send unnecessary probes, but must not silently omit a real holder when correctness requires invalidating it.

Directory capacity and replacement policy matter independently of data-cache capacity. If an entry is removed while caches still hold the corresponding line, the system must preserve the information required to maintain coherence. One solution is to recall or invalidate those copies before discarding the entry. Other designs transfer tracking responsibility or use a representation that covers the displaced information. Such events can produce coherence traffic even when the data itself would otherwise remain useful in private caches.

Directories are especially important in non-uniform memory access systems, where memory and processors are distributed across nodes. A physical address identifies or maps to a home, and accesses may traverse an intersocket or on-chip network. Coherence makes the memory logically shared, but does not erase distance: a remote ownership transfer may cost much more than a local cache hit. Address interleaving, home placement, and workload allocation therefore influence both directory load and overall communication latency.

Cache hierarchies and heterogeneous coherence domains

A processor system commonly has several cache levels, and coherence must fit their organization. Private first-level caches may sit above private or shared intermediate caches and a shared last-level cache. The protocol need not expose every physical cache as a separate system-wide participant. A lower-level controller can represent a group of upper-level caches, maintain local sharing information, and handle some requests without involving the rest of the machine. This creates a hierarchy of coherence responsibilities.

Cache inclusion describes a related but distinct property. In an inclusive hierarchy, a lower-level cache maintains the required inclusion relationship with lines held above it. Its tags can therefore help determine which upper-level caches may have copies. Evicting a lower-level entry may require invalidating corresponding upper-level copies. An exclusive hierarchy instead tries to avoid duplicating data across specified levels. A non-inclusive hierarchy does not require inclusion, although it may maintain separate directory information. None of these organizations by itself defines the coherence protocol.

The coherence point is not necessarily main memory. If a private cache holds the only current copy of a dirty line, the system remains coherent provided that requests are directed to it and ownership changes preserve its data. Likewise, a shared last-level cache can serve as a filtering or coordination structure without containing all current data bytes. This distinction between data storage and coherence tracking is particularly important in systems with distributed last-level-cache slices.

Heterogeneous systems extend the participant set beyond conventional CPU cores. A GPU, accelerator, or another agent in a system-on-a-chip may participate in some parts of the coherence domain while retaining local caches with different policies. A shared virtual address does not establish coherence by itself: address translation determines which storage an address denotes, whereas coherence determines how cached copies of that storage are coordinated. Hardware and software interfaces must specify both properties separately.

Interconnect standards reflect different ways of connecting such agents. Arm’s AMBA ACE and CHI define mechanisms used in coherent processor and system fabrics. Compute Express Link, or CXL, defines protocols including CXL.cache for coherent device caching of host memory and CXL.mem for host access to device-attached memory. These interfaces do not imply that every cache and memory region is universally coherent. Their specifications and platform configurations determine the participating agents, supported transactions, and boundaries across which software must still arrange explicit coordination.

Communication costs and performance pathologies

Coherence traffic is determined by access patterns as well as by the number of cache misses. Read-only data can be replicated widely and reused locally with little subsequent communication. A frequently modified line accessed by several processors is different: each writer may need to acquire ownership and revoke other copies. The cost includes request messages, invalidations, acknowledgments, possible data transfer, and waiting for competing transactions. Performance can therefore deteriorate even when a program’s working set fits comfortably in the aggregate cache capacity.

False sharing occurs when processors modify different data objects that occupy the same coherence line. For example, two threads may each increment a separate counter, yet repeatedly transfer ownership because the counters share one line. There is no logical sharing of the counter values, but the protocol operates on the larger block. Padding or reorganizing objects can eliminate this specific interaction, although larger layouts can increase memory consumption and reduce useful cache density. The relevant granularity is the actual platform’s coherence granularity, not merely the size of the variables.

True sharing can also be expensive. A single lock word or shared counter may repeatedly migrate between processors. If a line alternates between two writers, its ownership “ping-pongs,” imposing a latency-sensitive serial dependency. A rough lower bound for a workload requiring one non-overlapped ownership handoff per operation is

R≤1thandoff,R \leq \frac{1}{t_{\mathrm{handoff}}},

where RR is the operation rate and thandofft_{\mathrm{handoff}} is the effective handoff latency. This bound describes the dependent transfer chain, not the total throughput of a machine processing independent lines in parallel.

Sharing patterns also affect read traffic. A writer modifying a widely shared line may trigger many invalidations; later readers must fetch the line again. Producer–consumer workloads can benefit from direct cache-to-cache forwarding, but still pay synchronization and transfer costs. Unnecessary speculative fetches or poorly targeted prefetching may add sharers or consume interconnect resources. Conversely, streaming accesses to private data may create substantial memory traffic while generating relatively little contested ownership traffic.

Performance analysis distinguishes coherence misses from cold-start, capacity, and conflict misses, although hardware counters do not always map cleanly onto these categories. Available events may report ownership requests, snoop responses, cache-to-cache transfers, invalidations, or remote-node accesses. Their interpretation is processor-specific. A high cache hit rate alone does not prove that coherence is inexpensive: a workload may spend substantial time waiting for permissions, contending for a home agent, or transferring lines that remain resident somewhere in the cache hierarchy.

Software interfaces, atomics, and non-coherent devices

For ordinary cacheable shared memory within a coherent domain, software normally does not issue explicit cache-maintenance operations after each store. The hardware makes cached replication transparent at the level promised by the architecture. Software must still use valid synchronization and obey its language’s concurrency rules. An operating system also manages page attributes, mappings, and device interfaces that determine whether particular accesses receive ordinary coherent-memory treatment.

Atomic operations add guarantees beyond merely maintaining current cached values. An atomic read-modify-write must perform its specified update indivisibly relative to relevant competing accesses. Implementations often acquire exclusive control of a line, but the architectural guarantee concerns the operation, not a particular cache state. Atomic accesses may also carry ordering semantics such as acquire or release. Coherence is therefore a supporting mechanism for many atomics, rather than a synonym for atomicity or synchronization.

A mutex illustrates the interaction. Several processors may read a lock word while it remains unchanged, but acquiring the lock requires an atomic state transition. Releasing it must provide the ordering required to publish protected updates. The protocol tracks the lock’s line and the protected data’s lines independently; correctness depends on the synchronization rules connecting those accesses. Lock implementations that repeatedly issue contended write requests can generate much more coherence traffic than implementations that allow waiting processors to poll readable copies.

Direct memory access introduces additional requirements when a device does not participate in the CPU’s coherence domain. A device reading memory may otherwise see an old backing-memory copy while newer data remain dirty in a CPU cache. A CPU reading a buffer after a device writes it may retain an obsolete cached copy. Platform-specific DMA interfaces arrange suitable mappings, cache maintenance, and ownership transitions. The required operations differ between coherent and non-coherent devices, which is why a device driver cannot generally replace the platform’s DMA interface with ordinary pointer accesses.

Cache maintenance, address translation, and memory ordering remain separate concerns. An input–output memory management unit controls device address translation and access permissions; its presence does not by itself make data caches coherent. Similarly, invalidating a translation entry is not the same as invalidating a data-cache line. Special memory types used for device registers may restrict caching or combining, and their access rules can differ from ordinary RAM. Correct software interaction therefore depends on the complete architectural and operating-system contract, not on an assumption that all memory-like objects behave identically.

Protocol correctness and verification

A cache-coherence controller is a distributed concurrent system. Even if each stable-state transition appears simple, messages can cross in transit, responses can be delayed, and local events can occur while remote transactions are incomplete. A processor may evict a line while another requests it, or two requesters may seek ownership almost simultaneously. Correctness requires every such interaction to preserve permissions and data, not merely that uncontended examples work.

A useful distinction separates safety from progress. Safety properties assert that forbidden events never occur: two agents must not simultaneously hold incompatible write permissions, and a read must not obtain a value inconsistent with the protocol’s ordering rules. Progress properties concern whether transactions eventually complete under stated assumptions about message delivery, scheduling, and resource availability. A system that preserves every data value but can permanently strand a request is not an adequate implementation.

Transient states are a major source of complexity. A cache awaiting data after a read request differs from one awaiting invalidation acknowledgments after an ownership upgrade. It may need to react differently to an incoming probe in each state. Directory controllers face analogous combinations of pending requests and responses. Buffer allocation and network routing add another layer: a protocol can encounter deadlock if messages hold resources while waiting cyclically for others. Separate virtual channels, reserved response capacity, or restrictions on dependencies can help establish progress.

Formal verification can express a protocol as interacting state machines and check invariants over their reachable states. Model checking is particularly useful for discovering short counterexample traces involving unusual message orders. However, the number of possible states grows rapidly with caches, lines, buffers, and outstanding transactions. Verification commonly combines finite models, symmetry reductions, abstraction, and proofs that local implementation details refine a more abstract specification. A proof for a simplified model applies to hardware only insofar as the model’s assumptions and refinement relationships are justified.

Simulation and testing remain important alongside proof. Directed tests exercise particular races; randomized traffic creates overlapping requests; architectural litmus tests probe allowed memory outcomes. Memory-model validation must extend beyond coherence because a protocol can correctly serialize each location while the processor implements incorrect cross-location ordering. Conversely, a passing application benchmark cannot establish protocol correctness: rare interactions involving replacement, retries, exceptions, or network backpressure may not arise during ordinary execution. Verification therefore spans cache controllers, interconnects, memory-ordering machinery, and their interfaces.

Historical development and architectural evolution

The coherence problem became increasingly important as multiprocessors combined shared memory with local high-speed caches. Caching reduced processor latency and memory bandwidth demand, but introduced replicated state that could become stale. Software-managed approaches could restrict caching or require explicit maintenance, while hardware approaches sought to preserve a more transparent shared-memory interface. The subsequent history of coherence reflects the changing balance among processor speed, memory latency, interconnect bandwidth, and the number of participating processors.

Directory-based ideas were established early. Lucien Censier and Paul Feautrier’s 1978 work described a directory-based solution to cache coherence in multiprocessor systems. The central insight was to track cached copies and direct coherence actions to their holders rather than require every cache to observe every access. Later directory research explored alternative representations, replacement behavior, and distributed organizations. These issues became especially consequential for machines whose processors and memory were spread across many nodes.

In the 1980s, bus-based microprocessor multiprocessors made snooping protocols prominent. James R. Goodman’s 1983 work on reducing processor–memory traffic helped establish influential write-once coherence ideas. Mark S. Papamarcos and Janak H. Patel described the protocol associated with the Illinois coherence scheme in 1984, an important development in the lineage commonly discussed through MESI states. Shared buses offered a practical common ordering point, allowing relatively small multiprocessors to maintain coherent private caches with manageable hardware complexity.

Larger shared-memory machines required more scalable communication. The Stanford DASH project, described in major publications in 1992, demonstrated distributed directory-based coherence for a scalable shared-memory architecture. Such systems helped establish cache-coherent non-uniform memory access as a practical design approach. They also made clear that a shared address space did not imply uniform performance: accessing a remote line, obtaining its ownership, and interacting with a distant directory could have substantially different costs from local accesses.

The growth of multicore processors moved many coherence interactions onto one chip, while multisocket servers retained additional off-chip coordination. More recent systems distribute shared-cache slices and home agents across on-chip networks and extend coherence selectively to accelerators and attached devices. Chiplet packaging changes the physical boundaries again, placing some logically integrated participants across package-level links. These designs retain the same basic need to coordinate permissions and current data, but alter the costs of broadcasts, directory lookups, forwarding, and ownership transfer.