Why is a Flush needed in the MSI cache coherency protocol when moving from Modified to Invalid?

Question

While studying the MSI protocol as described in different sources such as:

• https://en.wikipedia.org/w/index.php?title=MSI_protocol&oldid=941977299
• http://courses.csail.mit.edu/6.888/spring13/lectures/L7-coherence.pdf

they say that when moving from Modified to Invalid due to a BusRdX (another cache wants to write to the line), that the cache must write back to memory, or a "Flush" in the Wikipedia terminology.

However, I don't understand why this is needed. Wouldn't it be more efficient instead to:

• not do anything immediately

• service future reads from the new Modified cache.

  This new Modified cache must exist, because the only way for a cache to move from Modified to Invalid (besides eviction) is with a BusRdX, and the only thing that produces a BusRdX is another cache going to Modified after PrWr.

  More verbosely, the cache of the new writing CPU must first request that line to be read from the old modified cache, and this request both invalidates the old cache, and makes the most up to date value be in the new modified cache that was written to.

• only Flush on eviction, when the Modified cache is full and needs to offload something into main memory

If this approach is wrong, could anyone provide an example of how it would lead to a data loss problem? Or is there another more external reason why this Flush is needed?

This question somewhat supposes that cache-to-cache transfers are possible, which I'm not entirely sure. Here is a video that discusses that: Cache To Cache Transfers - Georgia Tech - HPCA: Part 5.

Answer 1

I believe in these models that there is no direct access to another processor's cache; values can only come from (a) the main memory or (b) a bus snooping operation.

I would also look at this from the perspective of the programmer's model of the synchronisation instructions on the CPU. There will usually be "compare and swap" and maybe an "atomic increment". Both of those require the old value.

The "stale" cached value absolutely does have to be invalidated in the cache of the other CPU, and I think you've correctly understood that.

Answer 2

I will let somebody else provide a full answer to your questions. For now I've included a table of state transitions for the MSI protocol taken from Sorin, Daniel J., Mark D. Hill, and David A. Wood. "A primer on memory consistency and cache coherence." Synthesis lectures on computer architecture 6.3 (2011): 1-212. Observing an Other-GetM (BusRdX) when in M state will transition to I state and send the data to the requestor. I imagine both variants could be considered "flavours" of MSI.

Theoretically, a CMP's bus could be split into control and data components where the former is the only part snooped. In this case, it wouldn't be possible to transfer lines between cache controllers and the data communication would need to happen through shared memory. I'm not sure if such designs occur in the wild though.