MESI
MESI ( M odified E xclusive S hared I nvalid) is a protocol for maintaining the cache consistency
in memory-coupled multiprocessor systems . The MESI protocol was first published by researchers at the University of Illinois . It is also often referred to as the Illinois Protocol.
Since each processor in memory-coupled multiprocessor systems has a cache , it must be determined whether one of the caches or the main memory contains the current value of a date. A system is said to be cache-coherent if it can be guaranteed to obtain the current value of a date at any time, even if it is in a different cache.
With the MESI protocol , two status bits are assigned to each cache line , which describe one of the following four states:
- (exclusive) Modified: This cache line was changed locally. The (old) copy in main memory is therefore invalid . If another computer wants to read this data in the main memory, the line must first be written back from the cache memory to the main memory.
- Exclusive (unmodified): This cache is the only one that contains this data block. The value in main memory is valid . If another computer reads this data in the main memory, the line must be marked as Shared. If the data in the main memory is changed, it must be declared invalid in the cache so that it can be reloaded from the main memory the next time it is accessed.
- Shared (unmodified): Several caches contain this data block. But since everyone has only read so far, the value in the main memory is valid. Write access to a shared line must always lead to an access to the external bus in order to update the main memory so that the lines in other cache memories can be declared invalid.
- Invalid: The content of this cache line is not up-to-date or there is still no value in this cache line ( compulsory miss ).
The transitions between these four states can now be triggered in two different ways: Either
- directly by writing or reading the data from the program
- indirectly by eavesdropping ( bus snooping ) on the actions of another processor on the bus through the cache. A cache uses the following control signals:
- Invalidate signal: Invalidate the line in the caches of other processors.
- Shared signal: Signaling whether a memory block to be loaded is already available as a copy in the cache.
- Retry signal: Request to a processor to cancel the loading of a block from the main memory into the cache, since the main memory still has an old, invalid date and must be updated beforehand. The loading can then be repeated.
A processor can read or write to a single address in the memory system. Correspondingly, read and write operations of a processor trigger bus transactions. With the MESI protocol there are the following bus transactions:
- Bus-Read (BusRd): The signal is placed on the bus when a processor wants to read the date or the value of a memory block.
- Bus-Read-Exclusive (BusRdX): The signal is sent to the bus when a processor wants to overwrite the data in a memory block.
- Flush: This signal is generated when only one processor (possibly also the main memory) has the current date of a memory cell in its cache and another processor tries to read or write to the same address of this memory cell. When the Flush signal appears on the bus, the date of the corresponding memory cell is also placed on the bus.
The read and write operations as well as the directly and indirectly generated bus transactions determine the behavior of the state machine , which is defined by the MESI protocol (see figure).
example
Assume a computer system with two processors, two caches, each with a cache line and shared main memory, which uses the MESI cache coherence protocol.
Hauptspeicher Cache A Cache B ------------------------------------- Datum_1 - -
Processor A now loads data 1, whereupon this is stored in the cache. Cache A signals to cache B that date 1 is being loaded. Since cache B has no entry for date 1, it does not signal anything. Cache A can therefore mark date 1 as exclusive (unmodified) .
Hauptspeicher Cache A Cache B ------------------------------------- Datum_1 E Datum_1 -
Processor B then also needs date 1 and loads it. Cache B signals that date 1 is being loaded. Since cache A already has an entry for date 1, it signals shared during this time and both caches mark their entry as shared (unmodified) .
Hauptspeicher Cache A Cache B -------------------------------------- Datum_1 S Datum_1 S Datum_1
Processor A has completed its work with date 1 and is now changing its value. Since date 1 is marked with Shared (unmodified) , Cache A signals Invalidate when the entry is changed , whereupon Cache B marks the entry with Invalid . Cache A changes the value of date 1 and then marks date 1 with (exclusive) Modified , since no other cache has this value in stock after the Invalidate signal.
Hauptspeicher Cache A Cache B --------------------------------------- Datum_1 M Datum_1' I Datum_1
Processor B now wants to work with date 1. So it requests the value from cache B. However, cache B does not have this in stock because an entry marked as invalid is treated as a nonexistent entry. Cache B tries to load date 1 from the main memory. In doing so, it signals to cache A that it would like to do this. Cache A recognizes, however, that the value in the main memory is no longer up-to-date because it itself has an entry with date 1 and the (exclusive) Modified mark . So cache A must prevent the wrong value from the main memory from being used. It immediately sends the retry signal . Cache B registers this and aborts the loading process. To give cache A enough time, cache B waits for a short period of time. Meanwhile, cache A writes the current date 1 into main memory and then sets its own value to Shared .
Hauptspeicher Cache A Cache B --------------------------------------- Datum_1' S Datum_1' I Datum_1
At the end of the waiting time, cache B would like to finally have date 1 and read this from the main memory. Cache A registers the read process, signals shared and both caches have entered the current date 1 with the shared (unmodified) marker .
Hauptspeicher Cache A Cache B --------------------------------------- Datum_1' S Datum_1' S Datum_1'
The MOESI protocol is a further development of the MESI protocol.
See also
- Cache Coherency - General Procedure Overview
- MOESI - In addition to the MESI protocol, there is also an owned state
- MSI - basis of the MESI protocol
- MOSI - without exclusive , but with owned condition
- MESIF protocol
literature
- David E. Culler, Jaswinder Pal Singh: Parallel Computer Architecture - A Hardware / Software Approach Morgan Kaufmann, 1999, ISBN 1-55860-343-3