Cache coherence

Computers use many small parts to work.

Each part can keep its own copy of data. This data is like a small note.

Sometimes, one part changes its note.

If the other parts do not change too, they will have the wrong info. This can cause big mistakes.

To stay correct, all copies must stay the same. This keeps the data uniform. This is called being coherent.

Computers use special rules to help. Some rules watch all the parts. Other rules use a central list to keep track.

These rules make sure every part sees changes in the right order. This helps the whole system work well.

Computers often have many parts working at once.

Each part can keep its own local copy of data. This small storage is called a cache. Cache coherence is the way a system keeps all these copies the same.

If one part changes its data, the other copies must change too. This is called write propagation. This step makes sure all copies get the new info. The system must also use transaction serialization. This means all parts see changes in the same order. Without these rules, different parts might see different values. This can lead to big errors.

Computers use two main ways to stay coherent. One way is called snooping. In snooping, each cache watches the data lines. It listens for changes to the data it holds. This is fast but hard to do in very big systems.

The other way is directory-based. This uses a central directory to keep track of data. The directory acts like a list. It tells the system which parts have which data. This works well for very large systems with many processors.

Computers often use many processors at once to work faster. Each processor can have its own local storage called a cache. This cache holds copies of data from the main memory.

Cache coherence is the way a system keeps all these copies the same. If one processor changes a piece of data, all other copies must change too. Without this, different processors might see different values for the same thing. This mismatch can cause big errors in how the computer works.

To stay coherent, a system must follow two main rules. The first rule is called write propagation. This means any change made in one cache must be sent to all other copies. The second rule is called transaction serialization. This ensures that all processors see changes to the same data in the same order. Imagine if two people changed a number. One person changes it to 10, and another changes it to 20. Every processor must see those changes in that exact sequence. If some see 10 then 20, while others see 20 then 10, the system is incoherent.

There are two common ways to manage this process. The first way is called snooping. In a snooping system, each cache monitors the data lines to watch for changes. This is a fast method if there is enough bandwidth. However, it is hard to grow because every request must be sent to every processor. The second way is called directory-based. This uses a central directory to keep track of which caches hold which data. The directory acts like a filter for the processors. It tells them when they can load or change data.

Different protocols use different methods to handle these updates. In a write-invalidate protocol, a cache simply throws away its old copy when it sees a change. This forces the processor to get the new value from the main memory later. In a write-update protocol, the system actually sends the new data to update the other caches immediately. Many different types of protocols exist, such as MSI, MESI, and Dragon. In 2011, a company called ARM Ltd proposed the AMBA 4 ACE for handling this in specific computer chips. They also created the AMBA CHI specification for connecting fully coherent processors.

Understanding cache coherence helps us see how complex computers stay organized. It is like a group of friends sharing a single notebook. If one friend writes a new note, everyone else needs to know what it says. They must also agree on which note was written first. This keeps everyone on the same page. In a computer, this happens billions of times every second. It allows many processors to work together on one big task without getting confused.

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.