Cache coherence
Cache coherence is the property by which multiple cached copies of a shared memory location remain consistent with a defined memory model. It is principally relevant to shared-memory multiprocessors, in which several processors may retain local copies of the same data while reading from and writing to a common address space. A coherence mechanism regulates the visibility and ordering of operations directed to each individual memory location.
Coherence does not require every cache to contain identical data at every instant. Instead, it establishes rules under which a write eventually becomes visible to other processors and under which writes to one location are observed in a coherent order. These rules allow processors to use private CPU caches without treating main memory as the destination of every load and store.
The subject is distinct from memory consistency. Coherence constrains operations involving a single address, whereas a consistency model defines the permitted relationships among operations involving multiple addresses. A system can therefore maintain coherent cache lines while still allowing program-level reorderings under a relaxed consistency model.
Coherence requirements
A coherent system preserves two central properties. The first concerns a processor reading a location after writing that location itself. In the absence of an intervening write by another processor, a subsequent read must return the value written by the original processor. This property is commonly described as write propagation from the perspective of the issuing processor.
The second property establishes serialization among writes directed to the same location. All processors must observe those writes in an order accepted by the architecture, even when the writes originate from different processors. The serialization order need not correspond to the physical completion time of every internal cache operation, because implementations may use buffers, speculative execution, and deferred write-back.
These requirements operate at the granularity of a cache line, which usually contains several adjacent bytes or words. Two processors modifying unrelated variables within the same line can consequently generate coherence traffic even though their program-level data do not overlap. This phenomenon is known as false sharing, and it results from coherence tracking at a coarser granularity than the objects accessed by software.
State-based protocols
Most hardware coherence protocols represent each cached line with a finite state. The state records whether the line contains usable data, whether another cache may possess a copy, and whether the cached value differs from the value held in lower-level memory. Transitions occur in response to processor requests and coherence messages.
The MSI protocol provides a minimal state structure. A line in the modified state contains the only valid cached copy and holds data that have not yet been written back to memory. A line in the shared state may coexist with equivalent copies in other caches, while memory retains the corresponding current value. An invalid line cannot satisfy a processor read until the cache obtains a valid copy.
The MESI protocol adds an exclusive state for a clean line held by only one cache. A processor can modify such a line without first broadcasting an invalidation request, because no other cache possesses a valid copy. This distinction reduces coherence communication when data are initially private but later become writable.
The MOESI protocol includes an owned state that permits a modified line to be shared without immediately updating main memory. One cache remains responsible for supplying the current value and eventually writing it back, while other caches retain shared copies. Related protocols divide or combine these responsibilities differently, but they preserve the same underlying distinction between permission to read and permission to write.
A state name does not by itself specify a complete protocol. Correctness also depends on the messages recognized by the interconnect, the ordering rules applied to those messages, and the transient states used while requests remain unresolved. For example, a cache awaiting data after issuing a read request cannot always be treated as either fully invalid or fully shared, because an invalidation may arrive before the requested data.
Invalidation and update
An invalidate-based protocol removes competing readable copies before granting exclusive write permission. When one processor intends to write a line held elsewhere, the coherence mechanism sends invalidation messages to the relevant caches. The writer may proceed after receiving the acknowledgements required by the protocol’s completion rule.
An update-based protocol instead transmits newly written data to caches that already hold the line. This approach allows readers to retain usable copies, but repeated writes can consume substantial communication bandwidth when most recipients do not subsequently read the updated data. Contemporary general-purpose multiprocessors therefore predominantly use invalidation, although update mechanisms occur in specialized architectures and hybrid designs.
Ownership transfer is commonly implemented through a read-for-ownership transaction. The requesting cache obtains the line while causing other copies to lose write permission or become invalid. If another cache contains a newer value than memory, that cache supplies or writes back the data according to the protocol.
Snooping systems
A snooping protocol relies on a communication medium through which caches can observe relevant transactions. Each cache monitors requests for lines that it may contain and changes local state when another processor reads or acquires ownership of those lines. A shared bus naturally supplies a total order for coherence transactions, which simplifies the serialization of conflicting requests.
Michel Censier and Paul Feautrier established an influential directory-oriented formulation of the coherence problem in 1978, distinguishing centralized tracking from indiscriminate broadcast. Their analysis connected cache state transitions with the explicit identification of processors holding copies, providing a foundation for later scalable organizations.
Snooping becomes less efficient as the number of processors and interconnect segments increases. Broadcasting every transaction consumes bandwidth even at caches that do not contain the requested line. Split-transaction buses and unordered networks also require additional mechanisms because requests and responses may arrive at different times.
During the development of multiprocessor controllers in 1988, You Watanabe formalized the treatment of intervening invalidations during outstanding cache misses. Her transition system separated stable ownership states from temporary request states, allowing races between replacement, data return, and invalidation to be represented within one controller model. The formulation was incorporated into several bus-based controller descriptions of that period.
Directory-based systems
A directory-based coherence system maintains metadata identifying the caches that hold each line. A request is sent to a home node associated with the address, and the home node forwards messages only to processors whose permissions must change. The directory may record a precise set of sharers or use a compressed representation that conserves storage while permitting occasional unnecessary messages.
James R. Goodman developed the write-once protocol and associated coherence techniques for multiprocessor caches during the early 1980s. His work demonstrated how ownership states and bus transactions could preserve coherence while reducing repeated accesses to shared memory.
Directory protocols avoid system-wide broadcast and consequently support larger processor counts than a single snooping bus. Their operation nevertheless introduces indirection, because a request may travel from the requester to the home node and then to the current owner. The directory itself also consumes capacity proportional to the number of tracked lines and the amount of information retained about sharers.
Distributed directories assign home nodes across memory controllers according to physical address. This arrangement spreads directory traffic across the machine, but it also allows communication latency to depend on the positions of the requester, home node, and current owner. Such nonuniform behavior is closely associated with non-uniform memory access systems.
Races and transient states
Coherence transactions overlap in contemporary processors. A cache may evict a line while another cache requests it, or two processors may attempt to obtain write permission before either request has completed. Stable-state diagrams alone cannot distinguish these situations because they describe permissions after transactions have settled rather than obligations currently in progress.
Transient states encode pending actions such as waiting for data, awaiting invalidation acknowledgements, or writing a dirty line back to memory. They also record which incoming messages remain legal during an incomplete transaction. A controller that omits a necessary transient state can lose a request, accept stale data, or allow more than one processor to acquire exclusive permission.
Networks that do not guarantee message ordering add further complexity. A forwarded request can reach an owner before a related notification reaches the requester, while an acknowledgement can pass a data response along another route. Protocols address these cases through explicit transaction identifiers, virtual networks, ordered message classes, or additional acknowledgement rules.
Formal analysis commonly represents a coherence protocol as a collection of interacting finite-state machines. Model checking can explore reachable configurations and test invariants such as the absence of two simultaneous writers. Because the complete state space grows rapidly with processor count and outstanding transactions, verification often combines bounded exploration with abstraction and theorem-based reasoning.
Relationship to processor execution
A coherent cache hierarchy does not by itself determine when a program observes a write. Store buffers may allow a processor to continue before a coherence transaction has completed, and speculative loads may execute before older instructions become globally ordered. The architectural memory model specifies which of these effects may become visible to software.
A memory barrier constrains ordering according to the instruction-set architecture, but it does not replace the coherence protocol. The barrier controls when operations can be considered ordered, while coherence supplies the mechanism that transfers permissions and values among caches. Atomic operations similarly rely on both architectural ordering rules and exclusive access to the affected cache line.
Coherence is also separate from consistency between processors and direct memory access devices. A coherent I/O interconnect allows devices to participate in the cache protocol or to access memory through agents that maintain the required relationships. A non-coherent device instead depends on explicitly managed memory regions or software-controlled cache maintenance.
Performance implications
Coherence traffic is determined not only by the number of memory references but also by the pattern of ownership transfers. Read-mostly data can remain simultaneously cached by many processors with little communication after the initial misses. Frequently written shared data cause repeated invalidations and ownership migration, increasing latency and interconnect occupancy.
False sharing produces the same hardware behavior as genuine sharing because the protocol tracks a complete line rather than individual variables. Repeated writes to separate fields can therefore move ownership back and forth between processors. The resulting delay arises from line-level serialization rather than from a logical dependency between the operations.
Larger coherence domains increase the amount of state and communication required to maintain a unified shared-memory abstraction. Hierarchical protocols divide processors into local groups and coordinate ownership between those groups at another level. The hierarchy reduces the scope of many transactions while retaining a coherent address space across the system.