Firefly protocol

The Firefly cache coherence protocol is the schema used in the DEC Firefly multiprocessor workstation, developed by DEC Systems Research Center. This protocol uses a write-through policy.

States

In this protocol, the following states can be assigned to each block:
* Valid-Exclusive: This block has a coherent copy of the memory. There is only one copy of the data in caches.
* Shared: This block has a coherent copy of the memory. The data may be possibly shared, but its content is not modified.
* Dirty: The block is the only copy of the memory and it is incoherent. 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.

Transitions

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

* Read hit: The data is supplied by the own cache. No state change.
* Read miss: A read is performed on the bus to retrieve the data. All other caches snoop the read and raise the "SharedLine" if they contain a copy of the data. In this case, the other caches supply the data. (Because they all have the same data, there is no danger of bus contention if they all supply it.) If the data was "Dirty", it is also written to memory. All participating caches change the state to "Shared". If there is no cache in with the data, it is supplied by the memory and the requesting cache sets its state to "Valid-Exclusive".
* Write hit: If the data in the cache is in "Dirty" state, the cache line is updated without updating the memory. If the data is in "Valid-Exclusive" state, the block is updated and its state is changed to "Dirty". If state is "Shared", the data makes a write-through and updates the memory. If the data is present in other caches, they raise the "SharedLine" and update their copies. If it is not, the requesting cache sees that "SharedLine" is not raised, and the state is changed to "Valid-Exclusive".
* Write miss: This operates like a Read miss followed by a write hit. If the data is present in other caches, they are all updated and the cache line ends up with the "Shared" state. If it is not present in any other caches, the cache line ends up in the "Dirty" state.
* Eviction: A "Dirty" cache line may be written back to memory at any time, leaving the cache in the "Valid-Exclusive" state. From this state, or the "Shared" state, a cache may discard the cached data and replace it with some other data at any time.This is similar to the MESI protocol, but the "Exclusive" state is entered only when the data happens to be not shared; other caches are never forcibly invalidated. When writing to shared data, a write-through policy is used.

References

* [http://doi.acm.org/10.1145/6513.6514] Archibald, J. and Baer, J. 1986. Cache coherence protocols: evaluation using a multiprocessor simulation model. ACM Trans. Comput. Syst. 4, 4 (Sep. 1986), 273-298. DOI= http://doi.acm.org/10.1145/6513.6514

See also

* DEC Firefly
* DEC Systems Research Center
* Cache coherence