Firefly (cache coherence protocol)
| Industry | Computer hardware research |
|---|---|
| Headquarters | United States |
| Products | DEC Firefly multiprocessor workstation |
The Firefly cache coherence mechanism is implemented in the DEC Firefly multiprocessor workstation, created by DEC Systems Research Center. It operates as a 3-State Write Update Cache Coherence Protocol. In contrast to the Dragon protocol, Firefly performs updates on both Main Memory and Local caches during Write Update Bus Transitions, eliminating the need to differentiate between Shared Clean and Shared Modified states as Dragon does.
States
Cache blocks exist in one of the following states:
- Valid-Exclusive (V): The block is valid, unmodified, and exclusively held by a single cache.
- Shared (S): The block is valid, unmodified, and may be present in multiple caches simultaneously.
- Dirty (D): This state indicates the block is unique to one cache and has been altered since being fetched from memory; only blocks in this state require write-back upon replacement.
These states are analogous to the Exclusive, Shared, and Modified states found in the MESI protocol. The Firefly protocol avoids invalidation through bus transactions; cache line invalidation occurs solely during eviction.
Processor-side Requests
Processor interactions with its cache are categorized into four request types:
- PrRdMiss: A read request for a block absent from the cache.
- PrRdHit: A read request for a block already present in the cache.
- PrWtHit: A write request targeting a block already cached.
- PrWtMiss: A write request for a block not currently cached.
Bus-Side Requests
Bus operations enforce coherence by monitoring processor requests: 1. BusRd: Signals a read miss initiated by another processor. 2. BusWr/BusUpdt: Indicates a write operation by another processor that requires caches to update their copies.
Transitions
The protocol utilizes a bus signal named CopiesExist to determine if other caches contain the requested block. All caches monitor memory operations and assert CopiesExist (C) when they possess the data.
Processor-Initiated Transitions
- Upon a processor read miss: If no other caches hold the block (C LOW), it is loaded into the Valid state; if copies exist elsewhere (C HIGH), it enters the Shared state. - When a write miss occurs: If no copies are present (C LOW), the block loads as Dirty; if copies exist (C HIGH), it loads as Shared and updates main memory accordingly. - A write hit while in the Valid state upgrades the block to Dirty without immediate memory write-through. - Write hits in the Dirty state maintain that state. - For write hits in the Shared state, if copies exist (C HIGH), it remains Shared; if no other copies are detected (!C), it transitions to Valid as the only valid copy. - Read hits do not alter the current cache state.
Bus-Initiated Transitions
When a block is in the Shared state and a BusRd or BusWr event occurs, it stays in Shared.
If another processor accesses a block in the Dirty state, it downgrades to Shared and updates main memory.
For blocks in the Valid state, a read request from another processor causes a transition to Shared. On snooping a write request, the block updates and shifts to Shared.
Differing from MESI, Firefly’s update protocol propagates writes by immediately updating all copies upon a processor’s write request (PrWr).
Comparison with Other Policies
1. Maintaining refreshed data copies within caches leads to fewer coherence misses compared to Write–Invalidate schemes.
2. Protocols based on updates demand greater bus bandwidth because they transmit new data values via BusUpdate signals, whereas invalidate protocols simply issue invalidation commands.
3. Continuous data modifications can cause outdated information to persist in caches, which might result in the removal of more valuable data.