| --- |
| layout: documentation |
| title: "MESI two level" |
| doc: gem5 documentation |
| parent: ruby |
| permalink: /documentation/general_docs/ruby/MESI_Two_Level/ |
| author: Jason Lowe-Power |
| --- |
| |
| # 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. | |
