Write-once (cache coherency)

From Wikipedia, the free encyclopedia

For other uses, see Write once.

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

[edit] States

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 more than once. This is the only state that generates a write-back when the block is replaced in the cache.

[edit] Transitions

The protocol follows some transition rules for each event:

Write-Once Transition Diagram
Write-Once Transition Diagram
  • Read hit: The information is supplied by the own cache. No state change.
  • Read miss: If there is any cache with a copy in Dirty state, the cache with that copy sends its data to the other cache and executes a write-back to the main memory. If there is no cache in Dirty state, the data are supplied by the memory. In both cases, all copies of the data in any cache are set to the Valid state.
  • Write hit: If the information in the cache is in Dirty or Reserved state, the block are updated and its state is set to Dirty without update the 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. All other existing copies are set to Invalid.
  • Write miss: If there is any cache with a copy in Dirty state, the cache with that copy sends its data to the other cache and invalidate itself. If there is no cache in Dirty state, the data are supplied by the memory. In both cases, all copies of the data in any cache are set to the Invalid state.

[edit] References

  • [2] Archibald, J. and Baer, J. 1986. Cache coherence protocols: evaluation using a multiprocessor simulation model. ACM Trans. Comput. Syst. 4, 4 (Sep. 1986), 273-298. DOI= http://doi.acm.org/10.1145/6513.6514
  • [3] Goodman, J. R. 1983. Using cache memory to reduce processor-memory traffic. In Proceedings of the 10th Annual international Symposium on Computer Architecture (Stockholm, Sweden, June 13 - 17, 1983). International Conference on Computer Architecture. IEEE Computer Society Press, Los Alamitos, CA, 124-131. URL= http://portal.acm.org/citation.cfm?id=800046.801647