http://www.scss.tcd.ie/~jones/vivio/caches/MESIHelp.htm
| Vivio 5.1 - A
Tool For Creating Interactive Reversible E-Learning
Animations for the WWW |
|
| MESI
Cache Coherency Protocol |
|
This Vivio
animation is
designed to help you understand the MESI cache
coherency protocol.
A multiprocessor system
is depicted comprising 3 CPUs with local caches and
main memory. For simplicity, main memory contains 4
locations a0, a1, a2 & a3. The caches are direct
mapped and contain two sets - addresses a0 & a2
map to set 0 and a1 & a3 to set 1.
NB: in order to simplify
this animation, the size of a cache line and that of a
CPU read/write operation are identical. On a write
miss, however, the CPU reads memory even though it
will completely overwrite it as this behaviour mirrors
that of real caches where the size of the cache line
will usually be larger than that of a CPU read/write
operation.
|
NB:
click on diagram to activate Vivio
animation
|
Each CPU contains
buttons which initiate read or write transactions on
the specified memory location. A "CPU write" writes an
incrementing value (initially 1) to "memory".
The idea is to press the
buttons and see if you can follow the actions and
state transitions which occur. It is possible to
introduce bugs into the animation by pressing the "bug
free" button in the bottom right hand corner. See if
you can find out just exactly what the bugs are!
The direction of the
traffic on the address and data busses are indicated
by blue & red arrows respectively. The cache lines
and memory location involved in the transaction are
coloured green. Stale memory locations are coloured
gray.
A cache line can be in
one of 4 states. INVALID: cache line NOT
present in cache. EXCLUSIVE: cache line
present in this cache ONLY and identical to copy in
memory.MODIFIED: cache line
present in this cache ONLY and memory copy out of date
(stale). SHARED: cache
line in this cache and other
caches, ALL copies identical to memory copy. Writes
to SHARED cache lines
are write through whereas writes to EXCLUSIVE cache lines
are write-back. If a cache observes a bus transaction
for an address which it contains, it asserts the
SHARED bus line. MESI is an invalidate cache coherency
protocol.
Here is the state
transition diagram for a cache line:
![]()
Sample sequence to
try [from RESET]
| 1 |
CPU0: read a0 |
CPU0 reads
a0 from memory [not shared] - state E |
| 2 |
CPU0: read a0 |
CPU0 reads a0 from
cache - state E |
| 3 |
CPU0: write a0 |
CPU0
updates a0 in cache ONLY - state M |
| 4 |
CPU0: write a0 |
CPU0
updates a0 in cache ONLY - state M |
| 5 |
CPU1: read a0 |
CPU1 reads
a0, CPU0 cache intervenes and supplies data
to cache and memory - state S |
| 6 |
CPU1: write a0 |
CPU1
updates a0 in cache & memory and
invalidates all other caches with address a0
- state E |
| 7 |
CPU1: write a0 |
CPU1
updates a0 in cache ONLY - state M |
| 8 |
CPU0: write a0
|
CPU0 reads
a0, CPU1 cache intervenes and supplies data
to cache and memory (S), CPU0 then writes to
a0 in cache & memory invalidating all
other caches with address a0 - state E |
| 9 |
CPU0: write a2 |
CPU0 reads
a2 from memory (E) and then writes to a2 -
state M |
| 10 |
CPU0: write a0 |
CPU0
flushes a2 to memory, reads a2 from memory
(E) and then writes to a0 - state M |
|
|
