Cache Coherence Protocols: Purpose and Mechanisms

The Cache Coherence Problem

Imagine a simple scenario in a dual-core system:

1. A shared variable x with an initial value of 10 is stored in main memory.
2. Core 0 reads x. A copy of the memory block containing x (value 10) is loaded into Core 0's private cache.
3. Core 1 also reads x. A copy of the same block (value 10) is loaded into Core 1's private cache.
4. Now, Core 0 executes an instruction to update x to 20. It updates its private cache line to reflect this new value.

At this moment, we have an inconsistency:

• Core 0's cache holds x = 20.
• Core 1's cache still holds the stale value x = 10.
• Main memory also holds the stale value x = 10.

If Core 1 now reads x from its cache, it will get the incorrect value 10. This violates the fundamental expectation of a shared-memory system: that a read should return the most recently written value. A cache coherence protocol is a hardware-level mechanism designed to prevent this from ever happening.

A coherent system must provide two guarantees:

1. Write Propagation: A write by one processor will eventually become visible to all other processors.
2. Write Serialization: All processors must observe writes to the same memory location in the same order. For example, if Core 0 writes x=20 and then Core 1 writes x=30, no processor should see the write to 30 occur before the write to 20.

Strategies for Maintaining Coherence

To enforce these guarantees, coherence protocols primarily use one of two strategies when a write to a shared data block occurs:

• Update Protocol: The writing core broadcasts the new data to all other caches. Those caches then update their local copies with the new value.
• Invalidate Protocol: The writing core broadcasts an invalidation message. All other caches with a copy of the data mark their version as invalid. If they need to read that data again, they must fetch the new version.

Most modern processors, including those using MESI, are based on invalidate protocols. While an update seems more direct, it can generate a lot of bus traffic if a variable is written many times before another core actually needs to read it. Invalidation is often more efficient: after one invalidation message, the writing core has exclusive ownership and can perform subsequent writes locally without any further bus traffic until another core requests the data.

Snooping Protocols and MESI

In bus-based systems (like the UMA architectures we discussed), the shared bus is the perfect place to implement coherence. Every memory request from any core is broadcast on the bus. This allows each cache controller to "snoop" on the bus, observing the transactions of other cores and reacting accordingly to keep its own state consistent.

The most widely used snooping-based coherence protocol is MESI. The name is an acronym for the four states a cache line can be in:

• Modified: The cache line is present only in the current cache, and its value is "dirty"—it has been modified and is different from main memory. The cache must write the data back to memory at some point.
• Exclusive: The cache line is present only in the current cache, and its value is "clean"—it is consistent with main memory. The core can write to this line without notifying other caches.
• Shared: The cache line may be present in other caches, and its value is "clean." The line is effectively read-only in this state; a write requires upgrading its status.
• Invalid: The cache line does not contain valid data.

To understand these states more deeply, please watch the following short video.

MESI State Transitions in Action

The real power of the MESI protocol lies in how cache lines transition between these states in response to CPU operations (local reads/writes) and bus transactions (snooped reads/writes from other cores).

Let's walk through a common sequence of events. The diagram below shows a full state machine, which can look complex at first. We will break it down with a step-by-step example.

The best way to understand this is to see it in action. The following animated video from MIT OpenCourseWare walks through a concrete example involving two threads.

Let's solidify this with a static visual of a similar scenario. The image below tracks the state of a memory block 'A' across three CPUs.

By following these rules, the MESI protocol ensures that no core ever reads a stale value, maintaining a coherent view of memory across the entire system. Your experience with C++ is relevant here; when you use std::atomic variables in a multithreaded program, you are relying on these underlying hardware coherence mechanisms to ensure that updates made by one thread are correctly and promptly seen by others.

A Note on Scalability: Snooping vs. Directory Protocols

The snooping mechanism we've discussed works beautifully but has a natural limitation: it relies on a broadcast medium (the bus) where all participants can see all messages. As we saw in the last lesson, buses don't scale well. With dozens or hundreds of cores, the bus would be completely saturated with snoop traffic.

For large-scale NUMA systems, a different approach is used: directory-based coherence.

• Instead of broadcasting, a centralized (but physically distributed) directory maintains the state of each memory block and a list of which caches are sharing it.
• When a core needs to read or write, it sends a request to the directory.
• The directory then sends targeted point-to-point messages only to the caches that need to be invalidated or that need to supply the data.

This approach avoids broadcast storms and is far more scalable, though it can introduce slightly higher latency because of the extra communication hop to the directory.

Conclusion

In this lesson, we tackled the critical challenge of maintaining data consistency in shared-memory systems. You learned how private caches can lead to the cache coherence problem and how hardware protocols solve it.

Key Takeaways:

• Cache coherence ensures that all cores have a consistent view of shared memory, guaranteeing that reads retrieve the most recently written values.
• Protocols can be invalidate-based (like MESI) or update-based. Invalidate protocols are generally more common in modern CPUs.
• Snooping is the mechanism used in bus-based systems, where cache controllers monitor bus traffic to maintain coherence.
• The MESI protocol uses four states (Modified, Exclusive, Shared, Invalid) to efficiently manage data sharing and ownership, minimizing bus traffic by allowing silent writes to exclusive data.
• For highly scalable systems, directory-based protocols replace snooping's broadcast mechanism with a more scalable point-to-point messaging system managed by a directory.

Preview of the Next Lesson

We have now completed our foundational look at shared-memory architectures, from their UMA/NUMA organization to the MESI protocol that makes them work correctly.

In the next lesson, we will shift our focus to the other major paradigm of parallel computing: distributed-memory architectures. We will explore systems where each processor has its own private memory, and all communication must be done explicitly by sending messages across an interconnection network. This will set the stage for understanding technologies like MPI (Message Passing Interface).