Chp8 my

In computing, cache coherence (also cache coherency) refers to the consistency of data stored in local caches of a shared resource. Cache coherence is a special case of memory coherence.

Cache Coherence

Definition

In computing, cache coherence (also cache coherency) refers to the integrity of data stored in local caches of a shared resource. Cache coherence is a special case of memory coherence. In order to maintain the property of correct accesses to memory, system engineers develop kinds of coherence protocols to tackle them down. In this section, coherence protocols in bus-based multiprocessors are discussed.

Coherency protocol

MESI protocol (Intel)

MESI basics

In MESI protocol, there are four cache block status:

• 1. Modified (M): the cache block valid in only one cache and the value is like different from the main memory.
• 2. Exclusive (E): the cache block is valid and clean, but only resides in one cache.
• 3. Shared (S): the cache block is valid and clean, but may exist in multiple caches.
• 4. Invalid (I): the cache block is invalid.

This figure shows the status change when bus traction generated. We are going to introduce those requests.

• PrRd: processors request to read a cache block.
• PrWr: processors request to write a cache block.
• BusRd: snooped request a read request to a cache block made by another processor.
• BusRdX: snooped request a read exclusive (write) request to a cache block made by another processor which doesn't already have the block. Shortly, write cache-to-memory
• BusUpgr: snooped request indicates that there is a write request to a cache block that another processor already has in its cache.
• Flush: snooped request indicates than an entire cache block is written back to main memory by another processors.
• FlushOpt: snooped request indicates that an entire block cache block is posted on the bus in order to supply it to another processor. Shortly, cache-to-cache.

Here we will introduce how Intel implements MESI.

• Modified state

- a read will leave the line in the M state, and transfer the data to the CPU. - a write to a modified line will leave the line in the M state. The write is held in the cache. - snooping results in one of two transitions. Either the cache line is written back to RAM and marked shared, or it is written back to RAM and marked invalid, so that it can become exclusively held by another cache.

• Exclusive state

- a read will leave the line in the E state, and transfer the data to the CPU - a write will push the line into the modified state. The write is held in the cache. - snooping again results in one of two transitions, either to the shared or invalid state, for the same reasons as in state M.

• Shared state

- a read will leave the line in the S state, and transfer the data to the CPU - a write results in one of two transitions. Either the line becomes exclusively held by this cache resulting in a transition to state E (and I elsewhere), or this is a write-through cache and the update is sent to memory, and the line stays in state S. - snooping also results in one of two transitions, either back to shared or to invalid, for the same reasons as in state M.

• Invalid state

- a read results in one of three transitions. First, the data may be read into the cache to become exclusively held. Or the data may be read into the cache, and become shared. The third possibility is for a miss on a block that is exclusively held elsewhere; the block cannot be read, and the line remains invalid. - a write results in a miss, but there is no allowance for write-allocate on a miss in this protocol. The line remains invalid. - snooping results in a transition back to the invalid state, because the cache does not hold the data being checked for.

MOESI protocol （AMD）

MOESI basics

AMD Opteron is using MOESI (modified, owned, exclusive, shared, invalid) protocol for cache sharing. In addition to the four states in MESI, which is adopted by Intel for their Xeon processors, a fifth state "Owned" appears here representing data that is both modified and shared. Using MOESI, writing modified data back to main memory is avoided before being shared, which could save bandwidth and gain much faster access to users to the cache.

The states of the MOESI protocol are:

• Invalid—A cache line in the invalid state does not hold a valid copy of the data. Valid copies of the data can be either in main memory or another processor cache.
• Exclusive—A cache line in the exclusive state holds the most recent, correct copy of the data. The copy in main memory is also the most recent, correct copy of the data. No other processor holds a copy of the data.
• Shared—A cache line in the shared state holds the most recent, correct copy of the data. Other processors in the system may hold copies of the data in the shared state, as well. If no other processor holds it in the owned state, then the copy in main memory is also the most recent.
• Modified—A cache line in the modified state holds the most recent, correct copy of the data. The copy in main memory is stale (incorrect), and no other processor holds a copy.
• Owned—A cache line in the owned state holds the most recent, correct copy of the data. The owned state is similar to the shared state in that other processors can hold a copy of the most recent, correct data. Unlike the shared state, however, the copy in main memory can be stale (incorrect). Only one processor can hold the data in the owned state—all other processors must hold the data in the shared state.

The first figure below shows the five different states of MOESI protocol. There are four valid states: M(odified) and E(xclusive) are not shared with other cache, while O(wned) and S(hared) with other caches. The second figure shows the state transitions of MOESI protocol.

AMD Special Coherency Considerations

In some cases, data can be modified in a manner that is impossible for the memory-coherency protocol to handle due to the effects of instruction prefetching. In such situations software must use serializing instructions and/or cache-invalidation instructions to guarantee subsequent data accesses are coherent. An example of this type of a situation is a page-table update followed by accesses to the physical pages referenced by the updated page tables. The following sequence of events shows what can happen when software changes the translation of virtual-page A from physical-page M to physical-page N:

1. Software invalidates the TLB entry. The tables that translate virtual-page A to physical-page M are now held only in main memory. They are not cached by the TLB.
2. Software changes the page-table entry for virtual-page A in main memory to point to physicalpage N rather than physical-page M.
3. Software accesses data in virtual-page A. During Step 3, software expects the processor to access the data from physical-page N. However, it is possible for the processor to prefetch the data from physical-page M before the page table for virtualpage A is updated in Step 2. This is because the physical-memory references for the page tables are different than the physical-memory references for the data. Because the physical-memory references are different, the processor does not recognize them as requiring coherency checking and believes it is safe to prefetch the data from virtual-page A, which is translated into a read from physical page M. Similar behavior can occur when instructions are prefetched from beyond the page table update instruction.

To prevent this problem, software must use an INVLPG or MOV CR3 instruction immediately after the page-table update to ensure that subsequent instruction fetches and data accesses use the correct virtual-page-to-physical-page translation. It is not necessary to perform a TLB invalidation operation preceding the table update.

References

1. Cache Coherence
2. Cache consistency & MESI Intel
3. A closer look at AMD's dual-core architecture
4. CSE 400 – Related Work: Instructions & Example
5. Trace-Driven Simulation of the MSI, MESI and Dragon Cache Coherence Protocols
6. Understanding the Detailed Architecture of AMD's 64 bit Core
7. MSI,MESI,MOESI sheet
8. AMD64 Architecture Programmer’s Manual
9. Intel PENTIUM