Firefly protocol
From Wikipedia, the free encyclopedia
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.
Contents |
[edit] 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.
This protocol never causes invalidation, so the Invalid state is not listed here.
[edit] Transitions
In order to identify which transitions must be made, the protocol detects sharing using a special bus line named SharedLine. The following rules are then applied to the transitions:
- Read hit: The data is supplied by the own cache. No state change.
- Read miss: If there is any cache with a copy of the block, the cache with that copy sends its data to the requesting cache and raises the SharedLine. All caches that contains a copy of the block sends the data on the bus. All theses caches and also the requesting cache change the states to Shared, writing-back its content if the old state was Dirty. If there is no cache in with the data, it is supplied by the memory and the requesting cache change its state to Valid-Exclusive.
- Write hit: If the data in the cache is in Dirty state, the block are 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 and all other copies of the data. If there are more copies, the SharedLine is raised, otherwise the requesting cache realize that there isn't any other copy and the state is changed to Valid-Exclusive.
- Write miss: If there is any cache with a copy, the cache with that copy sends its data to the other cache and the requesting cache sends the new data to the bus. All other caches and also the main memory updates the block. All the caches containing a copy and also the requesting cache change the states to Shared. If there isn't any cache containing the requested data, the main memory sends the data to the cache. Then the block is updated in the cache and its state is changed to Dirty.
[edit] References
- [1] 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
