MOSI protocol

From HandWiki
Revision as of 07:48, 27 June 2023 by Gametune (talk | contribs) (correction)
(diff) ← Older revision | Latest revision (diff) | Newer revision → (diff)
Short description: Cache coherence protocol, includes an Owned state as an extension of the MSI protocol.

The MOSI protocol is an extension of the basic MSI cache coherency protocol. It adds the Owned state, which indicates that the current processor owns this block, and will service requests from other processors for the block.

Overview of States

Following are the permitted states of a given cache line:

Modified (M) - Only one cache has a valid copy of the block and the value is likely to be different from the one in main memory. It has almost the same meaning as a dirty state in a write-back cache except for the difference that modified state also implies exclusive ownership of that block. Dirty state just means that the value of the block is different from the one in main memory, whereas, modified implies that the value is different than that of the main memory and that it is cached in only one location.

Owned (O) - Multiple caches may hold the most recent and correct value of a block and the value in main memory may or may not be correct. At a time, only one cache can have the owned state for a block. All the other caches with the same block must be in shared state.[1]

Shared (S) - Cache block is valid, could be shared by multiple caches, and may or may not have the same value as the main memory. Other processors can read from this, but do not have write permissions.

Invalid (I) - Cache block is invalid.

For any given pair of caches, the permitted states of a given cache line are as follows:

 M   O   S   I 
 M  Red XN Red XN Red XN Green tickY
 O  Red XN Red XN Green tickY Green tickY
 S  Red XN Green tickY Green tickY Green tickY
 I  Green tickY Green tickY Green tickY Green tickY

Operations

A finite state machine showing the processor transactions for the MOSI protocol.

In MOSI protocol, each cache has the following requests:

  • PrRd - Processor request to read a cache block.
  • PrWr - Processor request to write into a cache block.
  • BusRd - Snooped request indicating that there is a read request to a cache block made by another processor.
  • BusRdX - Snooped request indicating that there is a write request to a cache block made by another processor that does not have the block.
  • BusUpgr - Snooped request depicting that there is a write request to a cache block made by another processor that already has the block in its cache.
  • Flush - Snooped request after which the cache block is placed on the bus for a cache to cache transfer.[2]

Processor Transactions

Looking at the case for processor transactions, when the block is in the Invalid (I) state, either the cache block was never fetched from the memory or it was invalidated. When there is a processor read (PrRd), the state changes from invalid (I) to shared (S), thereby generating a bus read (BusRd). At the same time, if it is a processor write request (PrWr), then the state of the block changes to modified (M) along with a snooped write request (BusRdX).

Once the block is in the Owned (O) state, then a processor read (PrRd) does not generate any snooped signal and the block remains in the same state. Whereas, a write request from the processor (PrWr) results in changing the state of the block from owned (O) to modified (M) along with generating a snooped write request (BusUpgr).[3]

When the block is in the Modified (M) state, neither a processor read (PrRd) nor a processor write (PrWr) request generates a snooped signal since the block already indicates that the most recent and correct value resides only in that cache. Hence, it does not change the state and stays in modified (M) state.

A finite state machine showing the snooped bus transactions for the MOSI protocol.

While the block is in the Shared (S) state and there is processor read (PrRd) request, since the value of the cache block is the same in every other processor and in the main memory, there is no bus signal that is generated after a processor read (PrRd). A bus write request (BusUpgr) is generated once there is a processor write (PrWr) request to a block in the shared (S) state because the cache block is now no longer valid in all the other caches and the state of the block changes from shared (S) to being modified (M).

Bus Transactions

Considering the behavior of the finite state machine to snooped bus transactions, if the cache block is in Invalid (I) state then no snooped bus request will affect the block in any way, so even if it is a bus read (BusRd) or bus write request from a processor that has or does not have the block (BusRdX or BusUpgr), the block remains in the same invalid (I) state and does not generate any further actions.

When the cache block is in the Shared (S) state and there is a snooped bus read (BusRd) transaction, then the block stays in the same state and generates no more transactions as all the cache blocks have the same value including the main memory and it is only being read, not written into. If there is snooped write request (BusRdX or BusUpgr), then the state of the block changes from shared (S) to invalid (I) as the value of the block has been modified in one of the other cache blocks and all the other copies now must be invalidated.

Once the cache block is in the Modified (M) state and there is a bus read (BusRd) request, the block flushes (Flush) the modified data and changes the state to owned (O), thus making it the sole owner for that particular cache block. At the same time, when it is in the modified (M) state, there is never going to be a bus write request (BusUpgr) from another processor as it does not have the cache block. With a write request from another processor that doesn't have the block (BusRdX), the block changes its state to invalid (I) as another processor is writing to the block and hence will have the ownership for that block.

While a cache block is in the modified state, there is no possibility of a BusUpgr request from any other processor as none of them will have the block. By the definition of the modified (M) state, only that processor has the block, rest all are invalidated and hence cannot initiate a BusUpgr request.

While in the Owner (O) state and there is a snooped read request (BusRd), the block remains in the same state while flushing (Flush) the data for the other processor to read from it. With a snooped write request (BusRdX), the block changes state to invalid (I) along with flushing (Flush) the data as another processor is writing to it, thereby losing its ownership on that block. Whenever another processor tries to access that block, instead of going to the memory to access it, the processor takes it from other cache which already has that block in the owned (O) state. With a BusUpgr, it just changes the state from owner (O) to invalid (I).[3]

Comparison to MSI Protocol

The obvious difference between the MSI protocol and the MOSI protocol, also known as the Berkeley protocol[4] is the presence of an extra state (owned) in MOSI in addition to having just a modified (M) state.

In the MSI protocol, whenever there is a read miss request to block which is in the modified (M) state, it writes back to the main memory while changing the status of the block to shared (S). But in the case of MOSI protocol, where we have an additional state (owner), whenever another processor requests for a read operation, the block changes from modified to the owned (O) state and so retains the dirty block of cache, thereby removing the need to write back to the main memory immediately.

This deferral can save bus traffic and main memory writes in certain sequences of transactions. Consider for example if a cache is M for processor 1, then processor 2 reads from it, and then processor 1 writes again to it. In MSI, the MS transition of processor 1 from the read leads to one memory write, and then the SM transition leads to a BusUpgr. On MOSI, the MO transition generates no traffic, and the OM transition also generates one BusUpgr as before. MOSI therefore dispensed the initial memory write back and associated bus traffic which MSI would do.

Comparison to MESI Protocol

Both MESI (also known as Illinois)[4] and MOSI protocols, are extensions of the MSI protocol to improve different functionalities. MOSI focuses on reducing write backs and MESI attempts to reduce the number of bus transactions required after a read and write request from another processor. The exclusive (E) state in MESI protocol implies that the cache block is valid, clean (same value as in the main memory) and cached only in one cache whereas the owned (O) state in MOSI protocol implies that the cache block is valid, potentially dirty, writable and could be present in more than one cache (all caches have the same value).

References

  1. ↑ Sorin, Daniel; Hill, Mark; Wood, David (2011). A Primer on Memory Consistency and Cache Coherence. Morgan & Claypool. pp. 119–122. ISBN 9781608455645. 
  2. ↑ Solihin, Yan (2016). Fundamentals of parallel multi core architecture. RC Press, Taylor & Francis Group. ISBN 9781482211184. 
  3. ↑ 3.0 3.1 "An Evaluation of Snoop-Based Cache Coherence Protocols". http://hps.ece.utexas.edu/people/suleman/class_projects/pca_report.pdf. 
  4. ↑ 4.0 4.1 Yang, Q.; Bhuyan, L.N.; Liu, B.-C. (1989). "Analysis and Comparison of Cache Coherence Protocols for a Packet-Switched Multiprocessor". IEEE Transactions on Computers 38 (8): 1143–1153. doi:10.1109/12.30868. 

See also



Retrieved from "https://handwiki.org/wiki/index.php?title=MOSI_protocol&oldid=3014609"