Write-once (cache coherence)

From Wikipedia, the free encyclopedia
Jump to: navigation, search

In cache coherency protocol literature, Write-Once was the first MESI protocol defined. It has the optimization of executing write-through on the first write and a write-back on all subsequent writes, reducing the overall bus traffic in consecutive writes to the computer memory. It was first described by James R. Goodman in [1] (1983). Cache coherence protocols are an important issue in Symmetric multiprocessing systems, where each CPU maintains a cache of the memory.

States[edit]

In this protocol, each block in the local cache is in one of these four states:

  • Invalid: This block has an incoherent copy of the memory.
  • Valid: This block has a coherent copy of the memory. The data may be possibly shared, but its content is not modified.
  • Reserved: The block is the only copy of the memory, but it is still coherent. No write-back is needed if the block is replaced.
  • Dirty: The block is the only copy of the memory and it is incoherent. This copy was written one or more times. This is the only state that generates a write-back when the block is replaced in the cache.

These states have exactly the same meanings as the four states of the MESI protocol (they are simply listed in reverse order), but this is a simplified form of it that avoids the Read for Ownership operation. Instead, all invalidation is done by writes to main memory.

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

 I   V   R   D 
 I  Green tickY Green tickY Green tickY Green tickY
 V  Green tickY Green tickY Red XN Red XN
 R  Green tickY Red XN Red XN Red XN
 D  Green tickY Red XN Red XN Red XN

Transitions[edit]

The protocol follows some transition rules for each event:

Write-Once Transition Diagram
The "WM" transition from the Invalid state is erroneous; the write must be written through to memory and so leaves the line in the Reserved state.
  • Read hit: The information is supplied by the current cache. No state change.
  • Read miss: The data is read from main memory. The read is snooped by other caches; if any of them have the line in the Dirty state, the read is interrupted long enough to write the data back to memory before it is allowed to continue. Any copies in the Dirty or Reserved states are set to the Valid state.
  • Write hit: If the information in the cache is in Dirty or Reserved state, the cache line is updated in place and its state is set to Dirty without updating memory. If the information is in Valid state, a write-through operation is executed updating the block and the memory and the block state is changed to Reserved. Other caches snoop the write and set their copies to Invalid.
  • Write miss: A partial cache line write is handled as a read miss (if necessary to fetch the unwritten portion of the cache line) followed by a write hit. This leaves all other caches in the Invalid state, and the current cache in the Reserved state.

This is a variant of the MESI protocol, but there is no explicit read-for-ownership or broadcast invalidate operation to bring a line into cache in the Exclusive state without performing a main memory write. Instead, the first write to a Valid (a.k.a. Shared) cache line performs a write through to memory, which implicitly invalidates other caches. After that, the line is in the Reserved (Exclusive) state, and further writes can be done without reference to main memory, leaving the cache line in the Dirty (Modified) state.

References[edit]

  • Archibald, J.; Baer, J. L. (November 1986). "Cache coherence protocols: Evaluation using a multiprocessor simulation model". ACM Trans. Comput. Syst. 4 (4): 273–298. doi:10.1145/6513.6514. 
  • Goodman, J. R. (1983). "Using cache memory to reduce processor-memory traffic". Proceedings of the 10th annual international symposium on Computer architecture - ISCA '83. International Symposium on Computer Architecture: Stockholm, Sweden, June 13–17, 1983. pp. 124–131. doi:10.1145/800046.801647. ISBN 0-89791-101-6.