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 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 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
- 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