This VivioJS animation is designed to help you understand the write-once cache coherency protocol. The protocol was first described by James Goodman in "Using Cache Memory to Reduce Processor-Memory Traffic" presented at the 10th International Symposium of Computer Architecture (ISCA 1983).

A multiprocessor system is depicted comprising main memory, 3 CPUs and their associated caches. For simplicity, main memory contains 4 locations a0, a1, a2 and a3. The caches are direct mapped and contain two sets - addresses a0 and a2 map to set 0 and a1 and a3 map 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.

No canvas support
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 and 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. Valid: cache line present in this cache and possibly other caches as well, all copies identical to copy in memory. Reserved: cache line present in this cache ONLY and cache line identical to copy in memory. Dirty: cache line present in this cache ONLY, but memory copy out of date (stale). Writes to Valid and Invalid cache lines are write through whereas writes to Reserved and Dirty cache lines are write-back.

Here is the state transition diagram for a cache line:

writeOnce state transition digram

The animation can be reset by pressing the "reset" button in the bottom right hand corner and this help information is displayed by pressing the "help" button.

Sample sequence to try [from Reset]


1 CPU0: read a0 CPU0 reads a0 from memory - state V
2 CPU0: read a0 CPU0 reads a0 from cache - state V
3 CPU1: read a0 CPU1 reads a0 from memory - state V
4 CPU0: write a0 CPU0 updates a0 in cache and writes through to a0 in memory; other caches invalidate their copies of a0 [CPU1] - state R
5 CPU0: write a0 CPU0 updates a0 in cache ONLY - state D
6 CPU0: write a0 CPU0 updates a0 in cache ONLY - state D
7 CPU1: read a0 CPU1 reads a0, CPU0 cache intervenes and supplies data to cache and memory - state V
8 CPU2: read a2 CPU2 reads a2 from memory - state V
9 CPU0: write a2 as its a write miss CPU0 reads a2 from memory first [shared with CPU2]; updates a2 in cache and writes through to a2 in memory, other caches invalidate their copies of a2 [CPU2] - state R
10 CPU0: write a2 CPU0 updates a2 in cache ONLY - state D
11 CPU0: write a0 CPU0 flushes a2 to memory; as its a write miss CPU0 reads a0 from memory first; updates a0 in cache and writes through to a0 in memory, other caches invalidate their copies [none] - state R