This VivioJS 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 and a3. The caches are direct mapped and contain two sets - addresses a0 and a2 map to set 0 and addresses 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. ~Shared and ~Dirty: cache line present in this cache ONLY and cache line identical to copy in memory. ~Shared and Dirty: cache line present in this cache ONLY, but copy in memory out of date (stale). Shared and ~Dirty: cache line in this cache and possibly other caches as well, all copies identical to copy in memory. Shared and 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 is the state transition diagram for a cache line:

firefly state transition diagram

The animation can be reset by pressing the reset button in the top right hand corner.

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 and writes through to memory and CPU0 cache - state S~D
7 CPU1: write a2 CPU1 updates a2 in cache and 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 and 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 and 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 and 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 and CPU2 S~D] and then updates a0 in cache and writes through to the other caches and memory - state S~D