Hardware Reference
In-Depth Information
write misses. If the word is
read
soon, it will be loaded by the read miss anyway;
little is gained by loading it on the write miss.
As with many simple solutions, this one is inefficient. Every write operation
goes to memory over the bus, so with a modest number of CPUs, the bus will still
become a bottleneck. To keep the bus traffic within bounds, other cache protocols
have been devised. They all have the property that not all writes go directly
through to memory. Instead, when a cache line is modified, a bit is set inside the
cache noting that the cache line is correct but memory is not. Eventually, such a
dirty line has to be written back to memory, but possibly after many writes have
been made to it. This type of protocol is known as a
write-back protocol
.
The MESI Cache Coherence Protocol
One popular write-back cache coherence protocol is called
MESI
, after the ini-
tials of the names of the four states (M, E, S, and I) that it uses (Papamarcos and
Patel, 1984). It is based on the earlier
write-once protocol
(Goodman, 1983). The
MESI protocol is used by the Core i7 and many other CPUs for snooping on the
bus. Each cache entry can be in one of the following four states:
1. Invalid - The cache entry does not contain valid data.
2. Shared - Multiple caches may hold the line; memory is up to date.
3. Exclusive- No other cache holds the line; memory is up to date.
4. Modified - The entry is valid; memory is invalid; no copies exist.
When the CPU is initially booted, all cache entries are marked invalid. The
first time memory is read, the line referenced is fetched into the cache of the CPU
reading memory and marked as being in the E (exclusive) state, since it is the only
copy in a cache, as illustrated in Fig. 8-28(a) for the case of CPU 1 reading line
A
.
Subsequent reads by that CPU use the cached entry and do not go over the bus.
Another CPU may also fetch the same line and cache it, but by snooping, the origi-
nal holder (CPU 1) sees that it is no longer alone and announces on the bus that it
also has a copy. Both copies are marked as being in the S (shared) state, as shown
in Fig. 8-28(b). In other words, the S state means that the line is in one or more
caches for reading and memory is up to date. Subsequent reads by a CPU to a line
it has cached in the S state do not use the bus and do not cause the state to change.
Now consider what happens if CPU 2 writes to the cache line it is holding in S
state. It puts out an invalidate signal on the bus, telling all other CPUs to discard
their copies. The cached copy now goes to M (modified) state, as shown in
Fig. 8-28(c). The line is not written to memory. It is worth noting that if a line is
in E state when it is written, no bus signal is needed to invalidate other caches be-
cause it is known that no other copies exist.
Next consider what happens if CPU 3 reads the line. CPU 2, which now owns
the line, knows that the copy in memory is not valid, so it asserts a signal on the
