Cache coherence refers to the mechanisms and processes that ensure data consistency among the caches of various processor cores or nodes, main memory, and other caches in multiprocessor systems or distributed systems. The following is a detailed understanding from aspects such as the causes of the problem, coherence protocols, and implementation methods:
1. Causes of the Problem
1.1 The Necessity of Caches
In computer systems, caches are high-speed storage areas designed to alleviate the speed difference between processors and memory. Since the computing speed of processors is much faster than the read/write speed of memory, introducing caches can preload data that the processor may access frequently in the near future into the cache. When the processor needs data, it first reads from the cache, thereby greatly improving system performance. For more details.
1.2 Coherence Issues Caused by Caches
When multiple processor cores or nodes have their own caches, there may be cases where the same data has multiple copies in different caches and main memory. If the data among these copies is inconsistent, it will lead to incorrect program results. For example, if one processor core modifies the data in its cache, but the data in the caches of other processor cores and main memory is not updated in time, then subsequent reads by other processor cores will get old data, resulting in a data inconsistency problem.
1.3 Common Cache Coherence Protocols
To solve the problem of cache data inconsistency mentioned above, cache coherence protocols have been proposed.
MESI Protocol
It is a common cache coherence protocol, where MESI stands for four states: Modified, Exclusive, Shared, and Invalid.
Each cache line is in one of these four states. When a processor core accesses a cache line, it decides how to handle it based on its state and the current operation. For example, when a processor core wants to modify a cache line in the Shared state, it first needs to change the state of the cache line to Exclusive, then perform the modification. After the modification is completed, the state of the corresponding cache line in the caches of other processor cores will be set to Invalid to ensure data consistency.
- Four States of Cache Lines
- Modified: The data in the cache line has been modified but not yet written back to memory. At this time, the data only exists in the current CPU’s cache and is inconsistent with the data in memory.
- Exclusive: The data in the cache line only exists in the current CPU’s cache and is consistent with the data in memory. No other CPU caches this data.
- Shared: The data in the cache line exists in the caches of multiple CPUs and is consistent with the data in memory.
- Invalid: The data in the cache line is invalid and cannot be read.
- State Transitions
- From Invalid to Exclusive: When a CPU reads data that is not cached by other CPUs, the state becomes Exclusive.
- From Invalid to Shared: When a CPU reads data that is already cached by other CPUs, the state becomes Shared.
- From Exclusive to Modified: When a CPU modifies exclusively held data, the state becomes Modified.
- From Shared to Invalid: When a CPU modifies shared data, the state of the corresponding cache line in other CPUs’ caches becomes Invalid.
MOESI Protocol
It adds an Owned state to the MESI protocol. When a cache line is in the Owned state, it means that the cache line has been modified, and the modified value only exists in the current processor core’s cache. The corresponding cache lines in other processor cores’ caches are invalid, and the data in main memory is also an old value. The introduction of this state is mainly to optimize write-back operations, reduce the number of write operations to main memory, and improve system performance.
2. Methods to Implement Cache Coherence
- Bus Snooping: In bus-based multiprocessor systems, each processor core can monitor other processor cores’ access operations to memory through the bus. When a processor core modifies data in its cache, it sends a message through the bus to inform other processor cores that the corresponding data in their caches is invalid. After receiving this message, other processor cores mark the corresponding cache line in their caches as invalid. This method is simple to implement, but as the number of processor cores increases, the bus bandwidth becomes a bottleneck, affecting system performance.
- Directory Mechanism: In distributed systems or large-scale multiprocessor systems, the directory mechanism is usually used to implement cache coherence. The system maintains a directory that records the distribution of copies of each data block and state information. When a processor core wants to modify data, it first queries the directory to find all processor cores that have copies of the data, then sends invalidation messages to these processor cores to invalidate their cache copies. The directory mechanism can effectively solve the bottleneck problem of the bus snooping method in large-scale systems, but it is more complex to implement and requires consuming a certain amount of storage space and processing time to maintain directory information.
