The Dragon 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 Xerox Dragon multiprocessor workstation, developed by Xerox PARC

Xerox PARC

PARC , formerly Xerox PARC, is a research and co-development company in Palo Alto, California, with a distinguished reputation for its contributions to information technology and hardware systems....

. This protocol uses a write-back policy.

States

In this protocol, the following states can be assigned to each block:

• Invalid: No data in cache block.
• Clean: Clean, only copy.
• Shared-Clean: Clean, might be shared.
• Dirty: Modified, only copy.
• Shared-Dirty: Modified, might be shared. This implies that there might be up-to-date other copies of the data (in Shared-Clean state) but that the memory copy is not up-to-date.

These five states correspond to the five states of the MOESI protocol

MOESI protocol

In computing, MOESI is a full cache coherency protocol that encompasses all of the possible states commonly used in other protocols. In addition to the four common MESI protocol states, there is a fifth "Owned" state representing data that is both modified and shared. This avoids the need to...

, although they are listed above in IESMO order.

For any given pair of caches, the permitted states of a given cache line are as follows (the states abbreviated in the order above):

	I	C	SC	D	SD
I
C
SC
D
SD

Transitions

In order to identify which transitions must be made, the protocol detects sharing using a special bus line named Shared. All accesses on the main memory bus are 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...

ed by all caches, which assert the Shared line when a snoop hit occurs. The following rules are then applied to the transitions:

• Read hit: The data is supplied by the local cache. No state change.
• Read miss: If there is any cache with a copy of the cache line, it indicates this with the Shared line and supplies the data to the requesting cache, which keeps a copy in the Shared-Clean state. The supplying cache leaves its copy of the line in the Shared-Dirty or Shared-Clean state, as appropriate. Otherwise fetch the data from main memory and mark the cache Clean.
• Write hit: If the data in the cache is in Dirty or Clean state, updated the cached data and mark Dirty. If the state is Shared-Clean or Shared-Dirty then update other caches. If the Shared line is asserted change the local cache to Shared-Dirty and all others to Shared-Clean, otherwise the local cache changes to Dirty.
• Write miss: If there is any cache with a copy, that cache supplies the data. The writer generates a write broadcast, the local cache changes to Shared-Dirty and all others to Shared-Clean. Otherwise main memory supplies the data, the local cache state changes to Dirty.