June

June

写代码是热爱,写到世界充满爱

MESI protocol

Based on the invalid-based cache coherence protocol (invalid-based)

Status#

MESI corresponds to 4 states

  • Modified(M)

    The cache line is dirty and different from the value in main memory. If another CPU core wants to read this data from main memory, the cache line must be written back to main memory, and the state becomes shared(S).

  • Exclusive(E)

    The cache line is only in the current cache and is clean, consistent with the data in main memory. When another cache reads it, the state becomes shared; when writing data, it becomes modified.

  • Shared(S)

    The cache line also exists in other caches and is clean. The cache line can be discarded at any time.

  • Invalid(I)

    The cache line is invalid

Operations#

Two scenarios for state transitions:

  • Read and write operations of the cache on the processor & read and write operations of other processors
  • Bus requests monitored by bus snooper

Processor requests for the cache:

  1. PrRd: The processor requests to read a cache block
  2. PrWr: The processor requests to write a cache block

Bus requests for the cache:

  1. BusRd: The snooper requests indicate that other processors request to read a cache block
  2. BusRdX: The snooper requests indicate that other processors request to write a cache block that this processor does not own
  3. BusUpgr: The snooper requests indicate that other processors request to write a cache block that this processor owns
  4. Flush: The snooper requests indicate to write back the entire cache to main memory
  5. FlushOpt: The snooper requests indicate that the entire cache block is sent to the bus to be sent to another processor (copy from cache to cache)

State changes caused by processor operations:
Invalid:
PrRead:

  1. Send busRd signal to the bus -> Other processors see busRd, check if there is a valid data copy and notify the requesting cache. If there is a valid copy and the state is M, it needs to be written back to memory first, and then the local cache reads the data from memory, and the state becomes (S)Shared. If the state is S or E, the local cache reads the data from memory and sets the cache state to S. If no other cache has a valid copy, read from memory and the local cache state becomes (E)Exclusive.

PrWr:
Send BusRdx signal to the bus, change to Modified. If other caches have valid copies, one of the caches sends the data, otherwise get the data from main memory. If there is a valid copy in other caches, when they see the busRdx signal, the local cache is set to invalid (I).

MESI Protocol Operation Diagram[5]

Assume the following read/write operations access data at the same main memory location. The operation flow is: R1, W1, R3, W3, R1, R3, R2. Initially, all caches are empty.

Table 1.3 Example of MESI Operation, all operations refer to the same cache line (e.g., "R3" refers to a read operation by processor 3)
Local RequestP1P2P3Generated

Bus Requests

Data Provider
0Initial-----
1R1E--BusRdMem
2W1M----
3R3S-SBusRdP1's Cache
4W3I-MBusUpgr-
5R1S-SBusRdP3's Cache
6R3S-S--
7R2SSSBusRdP1/P3's Cache

Summary#

When a CPU writes data (M), if it operates on a shared variable (S), it sends a signal to notify other CPUs to invalidate the cache line of that variable (I). Therefore, when other CPUs need to read this variable, they find that the cache line in their cache is invalid, so they read it from memory again to ensure consistency.

When reading data, if the cache line in other CPUs is modified, the data must be written back to main memory first. When modifying data, the cache lines in other CPUs must be invalidated.

MESI and Memory Barriers#

If MESI is implemented straightforwardly, there are two obvious performance issues:

  • When trying to write to an Invalid cache line, it needs to wait for the latest data to be read from other processors or main memory, resulting in a long delay.
  • Setting the cache line to Invalid state is also slow.
    Therefore, CPUs generally optimize this by using Store Buffer and Invalidate Queue mechanisms.
Loading...
Ownership of this post data is guaranteed by blockchain and smart contracts to the creator alone.