Cache coherence

In modern computer architecture, cache coherence is the discipline of maintaining uniformity across shared data. Many computers use multiprocessing systems to increase speed. In these systems, each individual CPU often has its own local cache memory. This local cache stores copies of data from a shared main memory resource.

Cache coherence ensures that if multiple clients hold a cached copy of the same memory region, all those copies remain identical. Without this discipline, one client might change a data block without the others knowing. This leads to an incoherent state where different processors see different values for the same memory address. Such mismatches can cause serious errors in how a computer processes information.

To achieve true cache coherence, a system must satisfy two specific requirements. The first is write propagation. This means any change made to data in one cache must be sent to all other copies of that cache line in peer caches. The second requirement is transaction serialization. This ensures that all reads and writes to a single memory location are seen by all processors in the exact same order. For example, if a memory location receives two different values, A and then B, every processor must see them in that specific sequence. If one processor reads B and then A, the system has failed to maintain transaction serialization.

We can see the danger of incoherence by looking at a multi-processor example. Imagine four processors, P1 through P4, all holding a shared variable S with an initial value of 0. If P1 changes S to 10, and then P2 changes S to 20, write propagation alone is not enough. If the system only uses write propagation, P3 might see the change to 10 after seeing the change to 20. Meanwhile, P4 might see the changes in the correct order. Because P3 and P4 now have different views of the memory, the system is incoherent. Proper coherence protocols prevent this by sequencing all writes to the same location.

There are two primary mechanisms used to maintain this coherence: snooping and directory-based protocols. Snooping was first introduced in 1983. In a snooping protocol, individual caches monitor the address lines to watch for memory accesses they have cached. This method can be very fast if there is enough bandwidth available. However, snooping is not easily scalable. Because every request must be broadcast to every node in the system, the required bandwidth grows rapidly as the system gets larger. To help manage this, some systems use a snoop filter. A snoop filter maintains entries representing cache lines owned by various nodes to reduce unnecessary traffic.

Directory-based protocols offer a different approach that works better for very large systems. In these systems, shared data is managed by a common directory. This directory acts as a filter through which a processor must ask permission to load an entry from primary memory into its cache. When an entry is changed, the directory is responsible for either updating or invalidating the other caches that hold that entry. While directory-based systems often have longer latencies due to a three-hop request process, they use much less bandwidth. Because messages are point-to-point rather than broadcast, this method is preferred for large systems with more than 64 processors.

Within these mechanisms, protocols use different strategies to handle data changes. One strategy is the write-invalidate protocol. When a cache observes a write to a location it also holds, it simply invalidates its own copy. This forces the processor to read the new value from main memory during its next access. Another strategy is the write-update protocol. In this version, the cache controller updates its own copy with the new data immediately when a write is observed. Many specific protocol models have been developed to refine these actions, including MSI, MESI (also known as Illinois), MOSI, MOESI, and Dragon.

Cache coherence is a specialized form of memory consistency. While a cache coherent system focuses on the behavior of reads and writes to a single address location, a sequentially consistent system is broader. A sequentially consistent model requires that all loads and stores to all memory locations appear to execute in a total order. This hierarchy of rules allows complex, multi-core processors to function as a single, organized unit. By managing how data moves between local caches and main memory, these protocols allow many processors to work on the same tasks without creating conflicting versions of reality.