Dragon Protocol

In multi-processor systems, Dragon Protocol^[1] is an update based cache coherence protocol. This means that it directly updates all the cached values across multiple processors in order to perform write propagation. In contrast, the write invalidate based cache coherence protocols such as MSI and MESI handle cache write by a processor by invalidating the cached values across all the other processors. Update based protocols such as the dragon protocol perform efficiently when a write to a cache block is followed by several reads made by other processors, since the updated cache block is readily available across caches associated with all the processors. Such a scenario would have resulted in coherence misses in case of invalidate based processors. However performing write update could lead to capacity and conflict misses due to prolonged storage of stale data in the caches.

States

Each cache block resides in one of the four states: exclusive-clean, shared-clean, shared-modified and modify.

Exclusive-clean (E): This means that the cache block was first fetched by the current processor and has not been accessed by any other processor since.

Shared clean (Sc): This means that the cache block definitely exists in multiple processor’s caches, and that the current processor is not the last one to write the block. States E and Sc are maintained separately by the protocol to prevent read-write operations on cache blocks that are not shared, from inducing bus transactions, and hence slowing down the execution. This is a common occurrence in single threaded programs.

Shared modified (Sm): This means that the block exists in caches of multiple processors, and the current processor is the last one to modify the block. Consequently, the current processor is called the owner of the block. Unlike the invalidation protocols, the block doesn’t need to be up to date in the main memory, but only in the processor. It is the processor’s responsibility to update the main memory when the cache block is evicted.

Modify (M): This means that only one processor has the memory block, and also that it has modified the value since it has been brought in from the memory.

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

	E	Sc	Sm	M
E	N	N	N	N
Sc	N	Y	Y	N
Sm	N	Y	Y	N
M	N	N	N	N

Transactions

There are 4 processor transactions and 2 bus transactions.

Processor Read (PrRd): This happens when the processor completes a successful read on a certain cache block placed in its cache.

Processor Write (PrWr): This happens when the processor completes a successful write on a certain cache block placed in its cache. This makes the processor to be the latest to update the cache block.

Processor Read Miss (PrRdMiss): This happens when the processor fails to read a cache block from its cache, and needs to fetch the block from either the memory or another cache.

Processor Write Miss (PrRdMiss): This happens when the processor fails to write to a cache block from its cache, and needs to fetch the block from the memory or another cache and then write to it. This again makes the processor to be the latest to update the cache block.

Bus Read (BusRd): This happens when a processor requests the bus to fetch the latest value of the cache block, whether it be from the main memory or another processor’s cache.

Flush: This happens when a processor places an entire cache block on the bus. This is to reflect the changes made by the processor to the cached block in the main memory.

Bus Update (BusUpd): This happens when a processor modifies a cache block, and other processors need to an update in their respective cache blocks. This is unique to only write update protocols. BusUpd takes shorter time when compared to Flush operation, since writes made to caches are faster than to memory.

A shared line is also required to indicate whether a certain cache block is available in multiple caches. This is required because one of the caches could evict the block without needing to the update the other blocks. The shared line helps reduce memory and bus transactions in some cases where the block is available in only one cache and a bus update is hence, not required.

Transitions

Dragon Protocol - Processor Initiated Transactions

Processor initiated transitions

Based on the current state of the block and the transaction initiated by the processor, the cache block undergoes one of the following state transitions:

When a processor read-miss (PrRdMiss) occurs, and the cache block is not shared, the state transitions to Exclusive
When a processor read-miss (PrRdMiss) occurs, and the cache block is shared, the state transitions to state Shared Clean
When a processor write-miss (PrWrMiss) occurs, and the cache block is not shared, the state transitions to Modified
When a processor write-miss (PrWrMiss) occurs, and the cache block is shared, the state transitions to Shared Modified and the processor becomes the owner.
When there is a processor read (PrRd) hit, the state of the cache block does not change, and retains the value. This is because it is just a read command and it does not generate any bus transactions
If the cache block is in the Modified state, and the processor writes (PrWr) the block, there is no transition as the block is not being shared.
If the cache block is in the Shared Modified state when a write (PrWr) occurs and the shared line is asserted, a bus update (BusUpd) is generated to update the other cache block.
If the cache block is in the Shared Cleaned state when a write (PrWr) occurs and the shared line is asserted, a bus update (BusUpd) is generated to update the other cache block and the state changes to Shared Modified.
But if the cache block is in the Shared Clean state when a write (PrWr) occurs, but the shared line is not asserted, the state transitions to Modified, and no bus transactions are generated.
When the cache block is in Shared Modified state, and a processor writes (PrWr), but the shared line is not asserted, the state transitions to Modified.
When the block is in Exclusive state, and the processor writes (PrWr) to it, it will be changed to the Modified state.

Dragon protocol - Bus Initiated Transactions

Bus initiated transitions

Based on the current state of the block and the transaction initiated by the bus, the cache block undergoes one of the following state transitions:

If the cache block is in Modified, and a Bus Read (BusRd) is issued, a Flush is issued to update the main memory and the state transitions to Shared Clean, as the block is now in multiple caches.
If the cache block is in Shared Modified state, and a bus read (BusRd), a Flush is issued to update the main memory, and state remains the same.
If the cache block is in Shared Modified state, and a bus update (BusUpd) transaction is issued, the state transitions to Shared Clean, all the caches are updated.
If the cache block is in Shared Clean state, and it receives a bus read (BusRd) or a bus update (BusUpd) it continues to retain its state as the value is still shared. However, in the case of an Update, it will update the value in the cache block.

If the cache block is in the Exclusive state and a the bus reads the value (BusRd), the state will transition to Shared Clean, as the block is no longer only residing in one cache

References

^ Atkinson, Russell R.; McCreight, Edward M. (1987-01-01). "The Dragon Processor". Proceedings of the Second International Conference on Architectual Support for Programming Languages and Operating Systems. ASPLOS II. Los Alamitos, CA, USA: IEEE Computer Society Press: 65–69. doi:10.1145/36206.36185. ISBN 0818608056.

User:Tarunthokala/sandbox

Contents