The Firefly cache coherence

Cache coherence

In computing, cache coherence refers to the consistency of data stored in local caches of a shared resource.When clients in a system maintain caches of a common memory resource, problems may arise with inconsistent data. This is particularly true of CPUs in a multiprocessing system...

 protocol is the schema used in the DEC Firefly

DEC Firefly

The Firefly was a shared memory asymmetric multiprocessor workstation, developed by the Systems Research Center, a research organization within Digital Equipment Corporation. The first version built contained up to seven MicroVAX 78032 microprocessors...

 multiprocessor workstation, developed by DEC Systems Research Center

DEC Systems Research Center

The Systems Research Center was a research laboratory created by Digital Equipment Corporation in 1984, in Palo Alto, California....

. 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

MESI protocol

The MESI protocol is a widely used cache coherency and memory coherence protocol. It is the most common protocol which supports write-back cache...

.
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

Bus sniffing

Bus sniffing or Bus snooping is a technique used in distributed shared memory systems and multiprocessors to achieve cache coherence. Although there is one main memory, there are several caches , and unless preventative steps are taken, the same memory location may be loaded into two caches, and...

 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
  Bus contention
  Bus contention, in computer design, is an undesirable state of the bus in which more than one device on the bus attempts to place values on the bus at the same time. Most bus architectures require their devices follow an arbitration protocol carefully designed to make the likelihood of 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

MESI protocol

The MESI protocol is a widely used cache coherency and memory coherence protocol. It is the most common protocol which supports write-back cache...

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