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.

The coherence of caches is obtained if the following conditions are met:

1. A read made by a processor P to a location X that follows a write by the same processor P to X, with no writes of X by another processor occurring between the write and the read instructions made by P, X must always return the value written by P. This condition is related with the program order preservation, and this must be achieved even in monoprocessed architectures.
2. A read made by a processor P1 to location X that follows a write by another processor P2 to X must return the written value made by P2 if no other writes to X made by any processor occur between the two accesses. This condition defines the concept of coherent view of memory. If processors can read the same old value after the write made by P2, we can say that the memory is incoherent.
3. Writes to the same location must be sequenced. In other words, if location X received two different values A and B, in this order, by any two processors, the processors can never read location X as B and then read it as A. The location X must be seen with values A and B in that order.

Bus sniffing is the process where the individual caches monitor address lines for accesses to memory locations that they have cached. When a write operation is observed to a location that a cache has a copy of, the cache controller invalidates its own copy of the snooped memory location.

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