Editing MSI protocol

{{Short description|Cache coherence protocol}}
{{distinguish|Message Signaled Interrupts}}

In [[computing]], the '''MSI protocol''' - a basic [[Cache coherence|cache-coherence protocol]] - operates in multiprocessor systems.  As with other cache coherency protocols, the letters of the protocol name identify the possible states in which a cache line can be.

== Overview ==
In MSI, each block contained inside a cache can have one of three possible states:

*'''M'''odified: The block has been modified in the [[CPU cache|cache]].  The data in the cache is then inconsistent with the backing store (e.g. [[Main memory|memory]]).  A cache with a block in the "M" state has the responsibility to write the block to the backing store when it is evicted.
*'''S'''hared: This block is unmodified and exists in read-only state in at least one cache.  The cache can evict the data without writing it to the backing store.
*'''I'''nvalid: This block is either not present in the current cache or has been invalidated by a bus request, and must be fetched from memory or another [[CPU cache|cache]] if the block is to be stored in this cache.<ref>{{Cite book|last=Fuchsen|first=R.|title=29th Digital Avionics Systems Conference |chapter=How to address certification for multi-core based IMA platforms: Current status and potential solutions |date=2010-10-01|pages=5.E.3–1-5.E.3-11|doi=10.1109/DASC.2010.5655461|isbn=978-1-4244-6616-0|s2cid=16461614 }}</ref>

These coherency states are maintained through communication between the caches and the backing store.  The caches have different responsibilities when blocks are read or written, or when they learn of other caches issuing reads or writes for a block.

When a read request arrives at a cache for a block in the "M" or "S" states, the cache supplies the data.  If the block is not in the cache (in the "I" state), it must verify that the block is not in the "M" state in any other cache.  Different caching architectures handle this differently.  For example, bus architectures often perform [[Bus snooping|snooping]], where the read request is broadcast to all of the caches.  Other architectures include [[Directory-based coherence protocols|cache directories]] which have agents (directories) that know which caches last had copies of a particular cache block.  If another cache has the block in the "M" state, it must write back the data to the backing store and go to the "S" or "I" states. Once any "M" line is written back, the cache obtains the block from either the backing store, or another cache with the data in the "S" state.  The cache can then supply the data to the requester.  After supplying the data, the cache block is in the "S" state.

When a write request arrives at a cache for a block in the "M" state, the cache modifies the data locally.  If the block is in the "S" state, the cache must notify any other caches that might contain the block in the "S" state that they must evict the block.  This notification may be via bus snooping or a directory, as described above.  Then the data may be locally modified.  If the block is in the "I" state, the cache must notify any other caches that might contain the block in the "S" or "M" states that they must evict the block.  If the block is in another cache in the "M" state, that cache must either write the data to the backing store or supply it to the requesting cache.  If at this point the cache does not yet have the block locally, the block is read from the backing store before being modified in the cache.  After the data is modified, the cache block is in the "M" state.

For any given pair of caches, the permitted states of a given cache line are as follows:
{|class=wikitable style=text-align:center
!   !! &nbsp;M&nbsp; !! &nbsp;S&nbsp; !! &nbsp;I&nbsp;
|-
! &nbsp;M&nbsp;
|      {{N}} || {{N}} || {{Y}}
|-
! &nbsp;S&nbsp;
|      {{N}} || {{Y}} || {{Y}}
|-
! &nbsp;I&nbsp;
|      {{Y}} || {{Y}} || {{Y}}
|}

== State Machine ==
[[File:State diagram for processor transactions.png|thumb|State diagram of processor requests for the MSI protocol]]
Processor requests to the cache include:
* PrRd:  Processor request to read a cache block.
* PrWr:  Processor request to write a cache block.
[[File:State diagram for bus transactions.png|thumb|State diagram of bus transactions for the MSI protocol]]
In addition, there are bus side requests.  These include:
* BusRd:  When a read miss occurs in a processor's cache, it sends a BusRd request on the bus and expects to receive the cache block in return.
* BusRdX:  When a write miss occurs in a processor's cache, it sends a BusRdX request on the bus which returns the cache block and invalidates the block in the caches of other processors.
* BusUpgr:  When there's a write hit in a processor's cache, it sends a BusUpgr request on the bus to invalidate the block in the caches of other processors.
* Flush:  Request that indicates that a whole cache block is being written back to the memory.<ref name=":0" />
State Transitions:
* '''Invalid''':
** On a PrRd, BusRd is issued and state changes to '''Shared'''.
** On a PrWr, BusRdX is issued and state changes to '''Modified'''.
** On a BusRd, BusRdX or a BusUpgr an invalid block remains '''Invalid'''.
* '''Shared''':
** On a PrRd, the block remains in the '''Shared''' state.
** On a PrWr, BusUpgr is issued and state changes to '''Modified'''.
** On a BusRd, the block remains in the '''Shared''' state.
** On a BusRdX or BusUpgr, the block transitions to '''Invalid'''.
* '''Modified''':
** On a PrRd or PrWr, the block remains in the '''Modified''' state.
** On a BusRd, the cache block is flushed onto the bus and state changes to '''Shared'''.
** On a BusRdX, the cache block is flushed onto the bus and state changes to '''Invalid'''.<ref name=":0">{{Cite book|title=Fundamentals of Parallel Multicore Architecture|last=Solihin|first=Yan|publisher=Chapman & Hall/CRC Computational Science Series|year=2016}}</ref>
** A BusUpgr is not possible. Note that by being in the '''Modified''' state in one particular processor, a cache block has to be in the '''Invalid''' state in all other processor(s), as the '''Modified''' state is allowed in either none or only one processor. This effectively negates the possibility of a BusUpgr on the bus, which would require this block to be in the '''Shared''' state in one of the processor(s) that, as seen above, issues a PrWr.

==Usage==

This protocol is similar to the one used in the [[Silicon Graphics|SGI]] 4D machine.<ref>{{Cite web|url=https://smartech.gatech.edu/bitstream/handle/1853/14065/suh_taeweon_200612_phd.pdf|title=INTEGRATION AND EVALUATION OF CACHE COHERENCE PROTOCOLS FOR MULTIPROCESSOR SOCS|last=Suh|first=Taeweon|date=December 2006}}</ref>

==Variants==
Modern systems use variants of the MSI protocol to reduce the amount of traffic in the coherency interconnect.  The [[MESI protocol]] adds an "Exclusive" state to reduce the traffic caused by writes of blocks that only exist in one cache.  The [[MOSI protocol]] adds an "Owned" state to reduce the traffic caused by write-backs of blocks that are read by other caches.  The [[MOESI protocol]] does both of these things.

==See also==
*[[Coherence protocol]]
*[[MESI protocol]]
*[[MOSI protocol]]
*[[MOESI protocol]]
*[[MESIF protocol]]

== References ==
{{Reflist}}

[[Category:Cache coherency]]