CSC/ECE 506 Spring 2010/8a sk

MSI

MSI protocol is a three-state write-back invalidation protocol which is one of the simplest and earliest-used snooping-based cache coherence-protocols. According to this protocol, a cache block can be in one of the Modified (M), Shared (S), and Invalid (I) states.

State transition diagram for MSI protocol

• Modified state indicates that the variable in the cache has been modified and therefore has a different value from that found in the main memory. A cache line in this state thus needs to be written back to the block to memory during eviction.
• Shared state indicates that the block exists in one or more caches, and is clean, implying that its value is consistent with the one in main memory. So a cache block in this state can be evicted without having to write it back to the main memory.
• Invalid state indicates that the cache block is invalid.

In MSI protocol, processor requests to the cache include:

• PrRd: Processor requests read to a cache block.
• PrWr: Processor requests write to a cache block.

In MSI protocol Bus-side requests include:

• BusRd: BusRd transaction is generated by a PrRd that misses in the cache, and the processor expects a data response as a result. The cache controller puts the address on the bus and asks for a copy that it does not intend to modify. The memory supplies the data.
• BusRdX: BusRdX transaction is generated by a PrWr to a block that is either not in the cache or is in the cache but is not in modified state. The cache controller puts the address on the bus and asks for an exclusive copy that it intends to modify. The memory system provides the data. All other caches are invalidated. Once the cache obtains the exclusive copy, the write can be performed in the cache.
• Flush: Flush is a snooped request that indicates that an entire cache block is written back to the main memory by another processor.

The three states in the MSI protocol are used to directly enforce the cache coherence by allowing only a single processor in the modified state at a given time, allowing multiple processors in the shared state concurrently, and disallowing other processors in the shared state while a processor is in the modified state. In the MSI system, there is a serious drawback that an explicit BusRdX transaction is required for a read followed by a write, even if there are no other shared copies. When a processor reads in and modifies a data item, two bus transactions are generated in this protocol even in the absence of shared copies. The first is a BusRd that gets the cache block to S state, and the second is a BusRdX(or BusUpgr) to invalidate other cached copies. The BusRdX is useless in case there are no other shared copies.

SGI(Silicon Graphics, Inc) had used a protocol much like MSI in the IRIS 4D multiprocessor series. The bus used in this workstation is a pipelined, block transfer bus that supports the cache coherence protocol. The 4D-MP graphics superworkstation brought 40 MIPS(million instructions per second) of computing performance to a graphics super workstation. The cache coherence protocol had to support synchronization as well as sharing, so improvement in efficiency operations necessitated a compromise in the efficiency of the data sharing protocol. With the simple rules of MSI protocol enforced by hardware, efficient synchronization and efficient data sharing are achieved in a simple shared memory model of parallel processing in the 4D-MP graphics super workstation. So the simple MSI protocol is well-suited to these needs.

MESI

MESI protocol is a 4-state protocol, in which a cache block can have an 'Exclusive' state apart from the Modified, Shared and Invalid state as in MSI protocol.

State Transition Diagram for MESI protocol

• Modified : The cache block is possibly dirty,valid only in one cache, and the value may differ from the value in main memory so may need to be written back to main memory upon eviction.
• Exclusive : The cache block is clean, valid and exists only in one cache.
• Shared : The cache block exists in more than one cache and is clean.
• Invalid : The value of the cache block is invalid.

In the MESI protocol, the same as the MSI protocol, processor requests to the cache include:

• PrRd: processor-side request to read to a cache block
• PrWr: processor-side request to write to a cache block

Bus-side request, include:

• BusRd: snooped request that indicates there is a read request to a cache block made by another processor.
• BusRdX: snooped request that indicates there is a read exclusive (write)request to a cache block made by another processor which does not already have the block.
• BusUpgr: snooped request that indicates that there is a write request to a cache block that another processor already has in its cache.
• Flush: snooped request that indicates that an entire cache block is written back to the main memory by another processor.
• FlushOpt: snooped request that indicates that an entire cache block is posted on the bus in order to supply it to another processor. We distinguish FlushOpt from Flush because while Flush is needed for write propagation, FlushOpt is not required for correctness. It is implemented as a performance enhancing feature that can be removed without impacting correctness. It is referred to as an optional block flush cache-to-cache transfer.

MESI states under different conditions is shown in the figure below:

MESI protocol is used in Intel's IA32 Pentium class processors. In Intel Pentium 4 IA-32 Architecture Processor, the data cache uses MESI protocol to support more efficient write-back cache in addition to the write-through cache previously used by the Intel486 processor. According to Intel's processor manual, IA-32 processors (beginning with the Pentium processor) and Intel 64 processors use MESI (modified, exclusive, shared, invalid) cache protocol to maintain consistency with internal caches and caches in other processors.
The figure below represents the cache structure of Intel Pentium 4 processors:

In the L1 data cache and in the L2/L3 unified caches, the MESI (modified, exclusive, shared, invalid) cache protocol maintains consistency with caches of other processors. The L1 data cache and the L2/L3 unified caches have two MESI status flags per cache line. Each line can be marked as being in one of the states defined in the table shown below. In general, the operation of the MESI protocol is transparent to programs. The L1 instruction cache in P6 family processors implements only the “SI” part of the MESI protocol, because the instruction cache is not writable. The instruction cache monitors changes in the data cache to maintain consistency between the caches when instructions are modified.
During replacement of a cache block, some MESI implementations require a message to be sent to memory when a cache line is flushed - an E to I transition, as the line was exclusively in one cache before it was removed. In alternate implementation, this replacement message could be avoided if the system is designed so that the flush of a modified /exclusive line requires an acknowledgment from the memory. However, this requires the flush to be stored in a 'write-back' buffer until the reply arrives to ensure the change is successfully propagated to memory. There is a bandwidth trade-off in both these implementations.