This Vivio animation is designed to help you understand the Firefly cache coherency protocol. The protocol is described in "Firefly: A Multiprocessor Workstation" by Charles P. Thacker, Lawrence C. Stewart and Edwin H. Satterthwaite JR., IEEE Transactions on Computers Vol. 37, No. 8, August 1988. 

A multiprocessor system is depicted comprising main memory, 3 CPUs and their associated caches. 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. ~Shared & ~Dirty: cache line present in this cache ONLY and cache line identical to copy in memory. ~Shared & Dirty: cache line present in this cache ONLY, but copy in memory out of date (stale). Shared & ~Dirty: cache line in this cache and possibly other caches as well, all copies identical to copy in memory. Shared & Dirty: cache line in this cache and possibly other caches as well, but memory copy out of date (stale). Writes to Shared cache lines are write through whereas writes to ~Shared cache lines are write-back. If a cache observes a bus transaction which refers to a cache line which it, itself, contains, then it asserts the SHARED bus line. Firefly is an update cache coherency protocol.

Here's the state transition diagram for a cache line: 

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 sequences to try

Sequence 1 [from Reset]

1 CPU0: read a0 CPU0 reads a0 from cache - state S~D
2 CPU0: read a2 CPU0 reads  a2 from memory - state ~S~D
3 CPU0: write a2 CPU0 updates a2 in cache ONLY - state ~SD
4 CPU0: write a2 CPU0 updates a2 in cache ONLY - state ~SD
5 CPU1: read a2 CPU1 reads a2, CPU0 cache intervenes and supplies data - state SD [NB: memory NOT updated]
6 CPU1: write a2 CPU1 updates a2 in cache & writes through to memory and CPU0 cache - state S~D
7 CPU1: write a2 CPU1 updates a2 in cache & writes through to memory and CPU0 cache - state S~D
8

CPU1:  read a0

 CPU1 reads a0 from memory - state S~D [NB: shared with CPU2 cache]
9 CPU0:  write a2 CPU 0 updates a2 in cache & writes through to memory because it thinks that the cache line is shared - state ~S~D  [now realises that it is no longer shared]
10 CPU0:  write a2 CPU 0 updates a2 in cache ONLY - state ~SD

Sequence 2 [from Reset]

1 CPU0: read a2 CPU0 reads a2 from memory - state ~S ~D
2 CPU0: write a2 CPU0 updates a2 in cache ONLY - state ~SD
3 CPU0: write a2 CPU0 updates a2 in cache ONLY - state ~SD
4 CPU1: read a2 CPU1 reads a2, CPU0 cache intervenes and supplies data - state SD [NB: memory NOT updated]
5 CPU1: read a0 CPU1 flushes a2 to memory, CPU0 & CPU1 change to S~D [like a CPU1 write to a2 at this point], CPU1 then reads a0 from memory - state S~D [shared with CPU2 cache]
6 CPU0: write a2 CPU 0 updates a2 in cache & writes through to memory because it thinks that the cache line is shared - state ~S~D  [now realises that it is no longer shared]
7

CPU0: write a2

 CPU 0 updates a2 in cache ONLY - state ~SD
8 CPU0: write a0 CPU 0 flushes a2 to memory, reads a0 before writing since it's a write miss [shared with CPU1 & CPU2 S~D]  and then updates a0 in cache & writes through to the other caches and memory - state S~D