C.2.4 MESI Protocol Example
Keywords: perfbook_html

##
C.2.4 MESI Protocol Example

Let's now look at this from the perspective of a cache line's worth of data, initially residing in memory at address 0, as it travels through the various single-line direct-mapped caches in a four-CPU system. Table shows this flow of data, with the first column showing the sequence of operations, the second the CPU performing the operation, the third the operation being performed, the next four the state of each CPU's cache line (memory address followed by MESI state), and the final two columns whether the corresponding memory contents are up to date (``V'') or not (``I'').

Initially, the CPU cache lines in which the data would reside are in the ``invalid'' state, and the data is valid in memory. When CPU 0 loads the data at address 0, it enters the ``shared'' state in CPU 0's cache, and is still valid in memory. CPU 3 also loads the data at address 0, so that it is in the ``shared'' state in both CPUs' caches, and is still valid in memory. Next CPU 0 loads some other cache line (at address 8), which forces the data at address 0 out of its cache via an invalidation, replacing it with the data at address 8. CPU 2 now does a load from address 0, but this CPU realizes that it will soon need to store to it, and so it uses a ``read invalidate'' message in order to gain an exclusive copy, invalidating it from CPU 3's cache (though the copy in memory remains up to date). Next CPU 2 does its anticipated store, changing the state to ``modified''. The copy of the data in memory is now out of date. CPU 1 does an atomic increment, using a ``read invalidate'' to snoop the data from CPU 2's cache and invalidate it, so that the copy in CPU 1's cache is in the ``modified'' state (and the copy in memory remains out of date). Finally, CPU 1 reads the cache line at address 8, which uses a ``writeback'' message to push address 0's data back out to memory.

Table: Cache Coherence Example
|  |  | CPU Cache | Memory
Sequence # | CPU # | Operation | 0 | 1 | 2 | 3 | 0 | 8
0 |  | Initial State | -/I | -/I | -/I | -/I | V | V
1 | 0 | Load | 0/S | -/I | -/I | -/I | V | V
2 | 3 | Load | 0/S | -/I | -/I | 0/S | V | V
3 | 0 | Invalidation | 8/S | -/I | -/I | 0/S | V | V
4 | 2 | RMW | 8/S | -/I | 0/E | -/I | V | V
5 | 2 | Store | 8/S | -/I | 0/M | -/I | I | V
6 | 1 | Atomic Inc | 8/S | 0/M | -/I | -/I | I | V
7 | 1 | Writeback | 8/S | 8/S | -/I | -/I | V | V

Note that we end with data in some of the CPU's caches.

Quick Quiz C.5: What sequence of operations would put the CPUs' caches all back into the ``invalid'' state? End Quick Quiz