Firefly (cache coherence protocol)

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 causes invalidation, so the Invalid state is not listed here.

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:

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

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.

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

State Diagram for Firefly protocol.

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.

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.

• DEC Firefly
• DEC Systems Research Center
• Cache coherence
• MSI Protocol
• MESI Protocol
• Dragon protocol

• Hashemi, B. (2011-05-01). Simulation and Evaluation Snoopy Cache Coherence Protocols with Update Strategy in Shared Memory Multiprocessor Systems. 2011 Ninth IEEE International Symposium on Parallel and Distributed Processing with Applications Workshops (ISPAW). pp. 256–259. doi:10.1109/ISPAW.2011.68. ISBN 978-1-4577-0524-3.
• Eggers, S. J.; Katz, R. H. (1988-01-01). A Characterization of Sharing in Parallel Programs and Its Application to Coherency Protocol Evaluation. Proceedings of the 15th Annual International Symposium on Computer Architecture. ISCA '88. Los Alamitos, CA, USA: IEEE Computer Society Press. pp. 373–382. doi:10.1145/633625.52442. ISBN 978-0818608612.
• 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.
• Solihin, Yan (2015-10-09). Fundamentals of Parallel Multicore Architecture. Raleigh, North Carolina: Solihin Publishing and Consulting, LLC. ISBN 978-1-4822-1118-4.