MESI state transition diagram question

[galapogos]

Hi,
I was looking through the various snoopy protocols and I have a question regarding the transition from exclusive to shared state being BusRd/Flush. I understand that moving from modified to shared requires a flush from cache to memory due to the cache data being dirty, but what I don't understand is why a clean cache line in exclusive state also requires a flush to memory. It seems to me that a BusRd/- would do.

Also, I was trying to find out more information on the MOESI protocol, including state transition diagrams, but somehow all the information ended at MESI. Does anyone know of any good references for this?

Thanks!

[bitvector]

I was looking through the various snoopy protocols and I have a question regarding the transition from exclusive to shared state being BusRd/Flush. I understand that moving from modified to shared requires a flush from cache to memory due to the cache data being dirty, but what I don't understand is why a clean cache line in exclusive state also requires a flush to memory. It seems to me that a BusRd/- would do.

There is some variation in considering what exactly consitutes the MESI protocol. Various chips that have implementations (like PowerPC and many other older architures) may have subtle variations depending on bus capabilities, write-back/write-through cache, etc. The paper that introduced MOESI (see below) provided a mapping of several other previously defined cache consistency protocols on to the set of MOESI states and that pretty much where MESI came from. In that paper, both the Illinois and Firefly protocols map on to MESI states, though somewhat differently. I think what most people refer to as the MESI protocol is typically derived from the Illinois protocol, though. The Illinois protocol is defined in "A low-overhead coherence solution for multiprocessors with private cache memories" (Papamarcos and Patel), and the Firefly protocol is defined in "An Evaluation of Cache Coherence Solutions in Shared-Bus Multiprocessors" (Archibald and Baer). I'd provide a link to the first paper if it was publically available, but I was able to get a copy through the ACM online library (but the second paper also has a decent overview). In the Illinois protocol, the Exclusive-Modified state corresponds to Modified, and Exclusive-Unmodified corresponds to Exclusive. That paper says, "Upon a cache miss, a read request is broadcast to all caches and the main memory." The MOESI paper says the following of the Firefly protocol, "The Firefly protocol requires that when an intervenient cache provides data, memory be updated."

In case of the Illinois protocol, it would seem that the Flush isn't a proper flush (when going from Exclusive to Shared), but rather a broadcast so that the value may be picked up by the other interested caches. But it's probably so read misses are handled uniformly. Read misses are handled the same way always and you can determine your state based on where the value comes from: if the missed value comes from memory, you set your state to Exclusive, but if it came from another cache, you set your state to Shared.

Similarly, the Firefly protocol says that another cache supplies the missed read directly to the requesting cache. It says "if the owning cache had the block in state DIRTY [Modified], the block is written to main memory at the same time. If no other cache has a copy of the block, it is supplied by main memory, and it is loaded in state VALID-EXCLUSIVE [Exclusive]."

You're right that there's no need to update main memory if the cache contents is unmodified, but it would seem that these protocols simply handle read misses uniformly probably to simplify the memory subsystem. All read misses can be handled the same with respect to memory bus activity and the "flush" can simply be used to update the other caches and main memory.

Also, I was trying to find out more information on the MOESI protocol, including state transition diagrams, but somehow all the information ended at MESI. Does anyone know of any good references for this?

The MOESI protocol was introduced in the paper, "A Class of Compatible Cache Consistency Protocols and their Support by the IEEE Futurebus," so that's probably the most definitive reference. It also has a comparison of various other cache consistency protocols and how they map on to the MOESI states.


Edit: Here is a paper that describes some of the variations in MESI implementations well: http://tibrewala.net/papers/mesi98/

It says, "An interesting feature of this is that the actual transition mechanisms are not specified for the protocol. This is where there is room for optimization while still retaining the essential features of the protocol." It then goes on to talk about how the PowerPC 604 and the Pentium II differ on handling the Modified to Shared transition on a read miss.

[galapogos]

Wow, thanks. Those papers are great. Didn't come up when I tried to google for MESI/MOSEI/cache coherence. You explanation cleared things up a lot. I'll read the papers for details

Thanks again!