MESI Two Level

Protocol Overview

• This protocol models two-level cache hierarchy. The L1 cache is private to a core, while the L2 cache is shared among the cores. L1 Cache is split into Instruction and Data cache.
• Inclusion is maintained between the L1 and L2 cache.
• At high level the protocol has four stable states, M, E, S and I. A block in M state means the blocks is writable (i.e. has exclusive permission) and has been dirtied (i.e. its the only valid copy on-chip). E state represent a cache block with exclusive permission (i.e. writable) but is not written yet. S state means the cache block is only readable and possible multiple copies of it exists in multiple private cache and as well as in the shared cache. I means that the cache block is invalid.
• The on-chip cache coherence is maintained through Directory Coherence scheme, where the directory information is co-located with the corresponding cache blocks in the shared L2 cache.
• The protocol has four types of controllers -- L1 cache controller, L2 cache controller, Directory controller and DMA controller. L1 cache controller is responsible for managing L1 Instruction and L1 Data Cache. Number of instantiation of L1 cache controller is equal to the number of cores in the simulated system. L2 cache controller is responsible for managing the shared L2 cache and for maintaining coherence of on-chip data through directory coherence scheme. The Directory controller act as interface to the Memory Controller/Off-chip main memory and also responsible for coherence across multiple chips/and external coherence request from DMA controller. DMA controller is responsible for satisfying coherent DMA requests.
• One of the primary optimization in this protocol is that if a L1 Cache request a data block even for read permission, the L2 cache controller if finds that no other core has the block, it returns the cache block with exclusive permission. This is an optimization done in anticipation that a cache blocks read would be written by the same core soon and thus save an extra request with this optimization. This is exactly why E state exits (i.e. when a cache block is writable but not yet written).
• The protocol supports silent eviction of clean cache blocks from the private L1 caches. This means that cache blocks which have not been written to and has readable permission only can drop the cache block from the private L1 cache without informing the L2 cache. This optimization helps reducing write-back traffic to the L2 cache controller.

Related Files

• src/mem/protocols
  • MESI_CMP_directory-L1cache.sm: L1 cache controller specification
  • MESI_CMP_directory-L2cache.sm: L2 cache controller specification
  • MESI_CMP_directory-dir.sm: directory controller specification
  • MESI_CMP_directory-dma.sm: dma controller specification
  • MESI_CMP_directory-msg.sm: coherence message type specifications. This defines different field of different type of messages that would be used by the given protocol
  • MESI_CMP_directory.slicc: container file

Controller Description

• L1 cache controller

States	Invariants and Semantic/Purpose of the state
M	The cache block is held in exclusive state by only one L1 cache. There are no sharers of this block. The data is potentially is the only valid copy in the system. The copy of the cache block is writable and as well as readable.
E	The cache block is held with exclusive permission by exactly only one L1 cache. The difference with the M state is that the cache block is writable (and readable) but not yet written.
S	The cache block is held in shared state by 1 or more L1 caches and/or by the L2 cache. The block is only readable. No cache can have the cache block with exclusive permission.
I / NP	The cache block is invalid.
IS	Transient state. This means that GETS (Read) request has been issued for the cache block and awaiting for response. The cache block is neither readable nor writable.
IM	Transient state. This means that GETX (Write) request has been issued for the cache block and awaiting for response. The cache block is neither readable nor writable.
SM	Transient state. This means the cache block was originally in S state and then UPGRADE (Write) request was issued to get exclusive permission for the blocks and awaiting response. The cache block is readable.
IS_I	Transient state. This means that while in IS state the cache controller received Invalidation from the L2 Cache's directory. This happens due to race condition due to write to the same cache block by other core, while the given core was trying to get the same cache blocks for reading. The cache block is neither readable nor writable..
M_I	Transient state. This state indicates that the cache is trying to replace a cache block in M state from its cache and the write-back (PUTX) to the L2 cache's directory has been issued but awaiting write-back acknowledgement.
SINK_WB_ACK	Transient state. This state is reached when waiting for write-back acknowledgement from the L2 cache's directory, the L1 cache received intervention (forwarded request from other cores). This indicates a race between the issued write-back to the directory and another request from the another cache has happened. This also indicates that the write-back has lost the race (i.e. before it reached the L2 cache's directory, another core's request has reached the L2). This state is essential to avoid possibility of complicated race condition that can happen if write-backs are silently dropped at the directory.

• L2 cache controller

Recall that the on-chip directory is co-located with the corresponding cache blocks in the L2 Cache. Thus following states in the L2 cache block encodes the information about the status and permissions of the cache blocks in the L2 cache as well as the coherence status of the cache block that may be present in one or more private L1 caches. Beyond the coherence states there are also two more important fields per cache block that aids to make proper coherence actions. These fields are Sharers field, which can be thought of as a bit-vector indicating which of the private L1 caches potentially have the given cache block. The other important field is the Owner field, which is the identity of the private L1 cache in case the cache block is held with exclusive permission in a L1 cache.

States	Invariants and Semantic/Purpose of the state
NP	The cache blocks is not present in the on-chip cache hierarchy.
SS	The cache block is present in potentially multiple private caches in only readable mode (i.e.in "S" state in private caches). Corresponding "Sharers" vector with the block should give the identity of the private caches which possibly have the cache block in its cache. The cache block in the L2 cache is valid and readable.
M	The cache block is present ONLY in the L2 cache and has exclusive permission. L1 Cache's read/write requests (GETS/GETX) can be satisfied directly from the L2 cache.
MT	The cache block is in ONE of the private L1 caches with exclusive permission. The data in the L2 cache is potentially stale. The identity of the L1 cache which has the block can be found in the "Owner" field associated with the cache block. Any request for read/write (GETS/GETX) from other cores/private L1 caches need to be forwarded to the owner of the cache block. L2 can not service requests itself.
M_I	Its a transient state. This state indicates that the cache is trying to replace the cache block from its cache and the write-back (PUTX/PUTS) to the Directory controller (which act as interface to Main memory) has been issued but awaiting write-back acknowledgement. The data is neither readable nor writable.
MT_I	Its a transient state. This state indicates that the cache is trying to replace a cache block in MT state from its cache. Invalidation to the current owner (private L1 cache) of the cache block has been issued and awaiting write-back from the Owner L1 cache. Note that the this Invalidation (called back-invalidation) is instrumental in making sure that the inclusion is maintained between L1 and L2 caches. The data is neither readable nor writable.
MCT_I	Its a transient state.This state is same as MT_I, except that it is known that the data in the L2 cache is in clean state. The data is neither readable nor writable.
I_I	Its a transient state. The L2 cache is trying to replace a cache block in the SS state and the cache block in the L2 is in clean state. Invalidations has been sent to all potential sharers (L1 caches) of the cache block. The L2 cache's directory is waiting for all the required Acknowledgements to arrive from the L1 caches. Note that the this Invalidation (called back-invalidation) is instrumental in making sure that the inclusion is maintained between L1 and L2 caches. The data is neither readable nor writable.
S_I	Its a transient state.Same as I_I, except the data in L2 cache for the cache block is dirty. This means unlike in the case of I_I, the data needs to be sent to the Main memory. The cache block is neither readable nor writable..
ISS	Its a transient state. L2 has received a GETS (read) request from one of the private L1 caches, for a cache block that it not present in the on-chip caches. A read request has been sent to the Main Memory (Directory controller) and waiting for the response from the memory. This state is reached only when the request is for data cache block (not instruction cache block). The purpose of this state is that if it is found that only one L1 cache has requested the cache block then the block is returned to the requester with exclusive permission (although it was requested for reading permission). The cache block is neither readable nor writable.
IS	Its a transient state. The state is similar to ISS, except the fact that if the requested cache block is Instruction cache block or more than one core request the same cache block while waiting for the response from the memory, this state is reached instead of ISS. Once the requested cache block arrives from the Main Memory, the block is sent to the requester(s) with read-only permission. The cache block is neither readable nor writable at this state.
IM	Its a transient state. This state is reached when a L1 GETX (write) request is received by the L2 cache for a cache blocks that is not present in the on-chip cache hierarchy. The request for the cache block in exclusive mode has been issued to the main memory but response is yet to arrive.The cache block is neither readable nor writable at this state.
SS_MB	Its a transient state. In general any state whose name ends with "B" (like this one) also means that it is a blocking coherence state. This means the directory awaiting for some response from the private L1 cache ans until it receives the desired response any other request is not entertained (i.e. request are effectively serialized). This particular state is reached when a L1 cache requests a cache block with exclusive permission (i.e. GETX or UPGRADE) and the coherence state of the cache blocks was in SS state. This means that the requested cache blocks potentially has readable copies in the private L1 caches. Thus before giving the exclusive permission to the requester, all the readable copies in the L1 caches need to be invalidated. This state indicate that the required invalidations has been sent to the potential sharers (L1 caches) and the requester has been informed about the required number of Invalidation Acknowledgement it needs before it can have the exclusive permission for the cache block. Once the requester L1 cache gets the required number of Invalidation Acknowledgement it informs the director about this by UNBLOCK message which allows the directory to move out of this blocking coherence state and thereafter it can resume entertaining other request for the given cache block. The cache block is neither readable nor writable at this state.
MT_MB	Its a transient state and also a blocking state. This state is reached when L2 cache's directory has sent out a cache block with exclusive permission to a requester L1 cache but yet to receive UNBLOCK from the requester L1 cache acknowledging the receipt of exclusive permission. The cache block is neither readable nor writable at this state.
MT_IIB	Its a transient state and also a blocking state. This state is reached when a read request (GETS) request is received for a cache blocks which is currently held with exclusive permission in another private L1 cache (i.e. directory state is MT). On such requests the L2 cache's directory forwards the request to the current owner L1 cache and transitions to this state. Two events need to happen before this cache block can be unblocked (and thus start entertaining further request for this cache block). The current owner cache block need to send a write-back to the L2 cache to update the L2's copy with latest value. The requester L1 cache also needs to send UNBLOCK to the L2 cache indicating that it has got the requested cache block with desired coherence permissions. The cache block is neither readable nor writable at this state in the L2 cache.
MT_IB	Its a transient state and also a blocking state. This state is reached when at MT_IIB state the L2 cache controller receives the UNBLOCK from the requester L1 cache but yet to receive the write-back from the previous owner L1 cache of the block. The cache block is neither readable nor writable at this state in the L2 cache.
MT_SB	Its a transient state and also a blocking state. This state is reached when at MT_IIB state the L2 cache controller receives write-back from the previous owner L1 cache for the blocks, while yet to receive the UNBLOCK from the current requester for the cache block. The cache block is neither readable nor writable at this state in the L2 cache.