Firefly (cache coherence protocol)

The Firefly cache coherence protocol is the schema used in the DEC Firefly multiprocessor workstation, developed by DEC Systems Research Center. This protocol is a 3 State Write Update Cache Coherence Protocol. Unlike the Dragon protocol, the Firefly protocol updates the Main Memory as well as the Local caches on Write Update Bus Transition. Thus the Shared Clean and Shared Modified States present in case of Dragon Protocol, are not distinguished between in case of Firefly Protocol.

States

In this protocol, the following states can be assigned to each block:

Valid-Exclusive(V): The cache block is valid, clean and only resides in one cache.
Shared(S): The cache block is valid, clean and may reside in multiple caches.
Dirty(D): The block is the only copy of the memory and it is dirty i.e. its value has been modified since being brought from the memory. This is the only state that generates a write-back when the block is replaced in the cache.

These states correspond to the Exclusive, Shared, and Modified states of the MESI protocol. This protocol never triggers an invalidation (via a bus transaction), so the Invalid state is not listed here. Only evictions will cause a cache line to go invalid.

Processor-side Requests

Processor-side requests or CPU requests are the accesses that the processor makes to its own caches. These may be classified into 4 types of requests namely:

PrRdMiss: Processor side request to read a cache block that does not reside in the cache.
PrRdHit: Processor side request to read a cache block that already resides in the cache.
PrWtHit: Processor side request to write to a cache block that already resides in the cache.
PrWtMiss: Processor side request to write to a cache block that does not reside in the cache.

Bus-Side Requests

Bus-side requests are the requests generated in response to the processor - side requests to maintain cache coherence. These are snooped by the snooper of caches and memory and appropriate action is taken. These are classified into two types in the Firefly protocol, namely:

1. BusRd: Request that indicates there is a read request to a cache block made by another processor and that processor doesn't have the data.

2. BusWr/BusUpdt: Request that indicates there is a write request to a cache block made by another processor and all other caches must update their copies of the block.

Transitions

In order to identify which transitions must be made, the protocol detects sharing using a special bus line named CopiesExist. All other caches snoop all memory operations and raise the CopiesExist(C) if they detect a "snoop hit", i.e. if they have a copy of the data in their own cache.

An arrow that goes from nowhere to a state represents a newly loaded block.

Processor-Initiated Transitions

In case of processor read miss to a block, and if there is no copy of the block in any other cache, CopiesExist (C) line is checked and C is LOW, then the block is placed in the cache and state is set as Valid. If there is already a copy in some caches (C is HIGH), then the block is placed in the cache in the Shared state.

On a write miss to a block, if there is no copy of the block in any cache (C is LOW), the block is placed in the cache in the Dirty state. If there is already a copy of the block in some caches (C is HIGH), then the block is placed in the cache in the state Shared state and the changes are reflected in the memory.

If a block is already cached in the Valid state, a processor write hit changes the state to Dirty state as no other cache has the copy of data. This write is not written through to memory.

If a block is cached in the Dirty state and a processor write hit occurs, then the state remains as Dirty state.

If the block is in Shared state and there's a processor write hit, and if there is already a copy in some caches (C), the block stays in Shared state. If there is no copy of the block in any cache (!C), the block is written in Valid state as it is the only ‘valid’ copy present in caches.

If there's a CPU read hit, the block stays in whatever state it is already in—just like in the Dragon protocol.

Bus-Initiated Transitions

If the block is in Shared State, and there's a BusRd or BusWr request, the block stays in Shared state.

If the block is in Dirty State, and another processor reads or writes it, request from another processor, it transitions into Shared state and changes are reflected in main memory.

If the block is in Valid State and another processor reads it, it transitions into Shared state. If another processor write request is snooped, the block will be updated, and since it is now being shared, it also moves into Shared state.

Unlike MESI, in the Firefly update protocol, write propagation is ensured by directly updating all other copies on a write request by the processors (PrWr).

Comparison with other Policies

1. Due to the fact that updated copies of the data exist in caches, there are fewer coherence misses than in Write – Invalidate policies.

2. Higher bus bandwidth is required than in invalidate protocols because invalidate protocols just send a signal/command on the bus which is snooped at other processors, causing them to invalidate their own copies of the data. In update protocols, by contrast, the new data value has to be sent along with the BusUpdate signal to allow memory and other caches to snoop and update their data.

3. Updating the data on every write causes some no-longer-needed data to remain in the cache, which may cause some ‘useful’ data to be evicted.

References

Hashemi, B. (2011-05-01). "Simulation and Evaluation Snoopy Cache Coherence Protocols with Update Strategy in Shared Memory Multiprocessor Systems". 2011 IEEE Ninth International Symposium on Parallel and Distributed Processing with Applications Workshops. pp. 256–259. doi:10.1109/ISPAW.2011.68. ISBN 978-1-4577-0524-3. S2CID 2093087.
Eggers, S. J.; Katz, R. H. (1988-01-01). A characterization of sharing in parallel programs and its application to coherency protocol evaluation. ISCA '88. Vol. 16. Los Alamitos, CA, USA: IEEE Computer Society Press. pp. 373–382. doi:10.1145/633625.52442. ISBN 978-0818608612. {{cite book}}: |journal= ignored (help)
Archibald, James; Baer, Jean-Loup (1986-09-01). "Cache Coherence Protocols: Evaluation Using a Multiprocessor Simulation Model". ACM Trans. Comput. Syst. 4 (4): 273–298. doi:10.1145/6513.6514. ISSN 0734-2071. S2CID 713808.