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.
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:
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 |
Sequence 3 [from Reset] CS3021/3421 Exam, Hilary Term 2017
| 1 | CPU0: reads a0 | CPU0 reads a0 from its cache state S~D (unchanged) |
| 2 | CPU0: reads a2 | CPU0 reads a2 from memory into its cache (replaces a0) state ~S~D |
| 3 | CPU0: write a2 | CPU0 writes a2 to its cache ONLY state ~SD |
| 4 | CPU1: write a2 | CPU0 writes a2 to its cache ONLY state ~SD (unchanged) |
| 5 | CPU1: read a2 | CPU1 reads a2 from memory into its cache CPU0 intervenes to supply data memory NOT updated (feature of Firefly protocol) state SD state of corresponding data in CPU0 cache also updated to SD |
| 6 | CPU2: read a2 | CPU2 reads a2 from memory into its cache CPU0 and CPU1 intervene to supply data state SD (copy of a2 now in all 3 caches in the SD state) |
| 7 | CPU0: write a2 | CPU0 writes through a2 and updates cached copies and memory state S~D (unchanged) |
| 8 | CPU0: write a2 | CPU0 writes through a2 and updates cached copies and memory state S~D (unchanged) |
| 9 | CPU0: read a0 | CPU0 read a0 from memory into its cache (replaces a2) state ~S~D |
| 10 | CPU1: read a0 | CPU1 reads a0 from memory into its cache (replaces a2) state S~D state of corresponding data in CPU0 cache also updated to S~D |
| 11 | CPU2: write a2 | CPU2 writes through a2 and updates cached copies and memory as it thinks cache line is shared state ~S~D (as no other CPU asserts the SHARED bus signal) |
| 12 | CPU2: write a2 | CPU2 updates cache ONLY state ~SD |