Advanced Computer Architecture CSE 8383Snooping ProtocolsWrite Invalidate Write ThroughWrite Through- Write Invalidate (cont.)Slide 5Example 1Complete the table (Write through write invalidate)Write Back- Write Invalidate (ownership)Write Back- Write Invalidate (ownership) (cont.)Ownership (cont.)Slide 11Example –2 Complete the table (Ownership)Write OnceWrite Once (cont.)Write Once (Cont.)Slide 16Write update and partial write throughWrite update and partial write through (cont.)Slide 19Slide 20Write Update Write BackWrite Update Write Back (cont.)Slide 23Slide 24Computer Science and EngineeringCopyright by Hesham El-RewiniAdvanced Computer Advanced Computer ArchitectureArchitectureCSE 8383CSE 8383March 21, 2006March 21, 2006Session 17Session 17Computer Science and EngineeringCopyright by Hesham El-RewiniSnooping ProtocolsSnooping protocols are based on watching Snooping protocols are based on watching bus activities and carry out the appropriate bus activities and carry out the appropriate coherency commands when necessary. coherency commands when necessary. Global memory is moved in blocks, and each Global memory is moved in blocks, and each block has a state associated with it, which block has a state associated with it, which determines what happens to the entire determines what happens to the entire contents of the block. The state of a block contents of the block. The state of a block might change as a result of the operations might change as a result of the operations Read-Miss, Read-Hit, Write-Miss, and Read-Miss, Read-Hit, Write-Miss, and Write-Hit. Write-Hit.Computer Science and EngineeringCopyright by Hesham El-RewiniWrite Invalidate Write ThroughMultiple processors can read block Multiple processors can read block copies from main memory safely until copies from main memory safely until one processor updates its copy. At this one processor updates its copy. At this time, all cache copies are invalidated time, all cache copies are invalidated and the memory is updated to remain and the memory is updated to remain consistent. consistent.Computer Science and EngineeringCopyright by Hesham El-RewiniWrite Through- Write Invalidate (cont.)State DescriptionValid[VALID]The copy is consistent with global memoryInvalid[INV]The copy is inconsistentComputer Science and EngineeringCopyright by Hesham El-RewiniWrite Through- Write Invalidate (cont.)Event ActionsRead Hit Use the local copy from the cache.Read Miss Fetch a copy from global memory. Set the state of this copy to Valid. Write Hit Perform the write locally. Broadcast an Invalid command to all caches. Update the global memory.Write MissGet a copy from global memory. Broadcast an invalid command to all caches. Update the global memory. Update the local copy and set its state to Valid.Replace Since memory is always consistent, no write back is needed when a block is replaced.Computer Science and EngineeringCopyright by Hesham El-RewiniExample 1CPCQMX = 5X = 5•P reads XP reads X•Q reads X Q reads X •Q updates XQ updates X•Q reads XQ reads X•Q updates XQ updates X•P updates XP updates X•Q reads XQ reads XComputer Science and EngineeringCopyright by Hesham El-RewiniComplete the table (Write through write invalidate) MemoryMemoryP’s P’s CacheCacheQ’sQ’sCacheCacheEventEventXXXXStateStateXXStateState00Original Original valuevalue55 11P reads P reads XX(Read (Read Miss)Miss)5555VALIDVALIDComputer Science and EngineeringCopyright by Hesham El-RewiniWrite Back- Write Invalidate (ownership)A valid block can be owned by memory and A valid block can be owned by memory and shared in multiple caches that can contain shared in multiple caches that can contain only the shared copies of the block. Multiple only the shared copies of the block. Multiple processors can safely read these blocks from processors can safely read these blocks from their caches until one processor updates its their caches until one processor updates its copy. At this time, the writer becomes the copy. At this time, the writer becomes the only owner of the valid block and all other only owner of the valid block and all other copies are invalidated. copies are invalidated.Computer Science and EngineeringCopyright by Hesham El-RewiniWrite Back- Write Invalidate (ownership) (cont.)State DescriptionShared (Read-Only) [RO]Data is valid and can be read safely. Multiple copies can be in this stateExclusive (Read-Write) [RW]Only one valid cache copy exists and can be read from and written to safely. Copies in other caches are invalidInvalid[INV]The copy is inconsistentComputer Science and EngineeringCopyright by Hesham El-RewiniOwnership (cont.)Event ActionRead Hit Use the local copy from the cache.Read Miss: If no Exclusive (Read-Write) copy exists, then supply a copy from global memory. Set the state of this copy to Shared (Read-Only). If an Exclusive (Read-Write) copy exists, make a copy from the cache that set the state to Exclusive (Read-Write), update global memory and local cache with the copy. Set the state to Shared (Read-Only) in both caches.Computer Science and EngineeringCopyright by Hesham El-RewiniOwnership (cont.)Write Hit If the copy is Exclusive (Read-Write), perform the write locally. If the state is Shared (Read-Only), then broadcast an Invalid to all caches. Set the state to Exclusive (Read-Write).Write Miss Get a copy from either a cache with an Exclusive (Read-Write) copy, or from global memory itself. Broadcast an Invalid command to all caches. Update the local copy and set its state to Exclusive (Read-Write).Block ReplacementIf a copy is in an Exclusive (Read-Write) state, it has to be written back to main memory if the block is being replaced. If the copy is in Invalid or Shared (Read-Only) states, no write back is needed when a block is replaced.Computer Science and EngineeringCopyright by Hesham El-RewiniExample –2Complete the table (Ownership) MemoryMemoryP’s P’s CacheCacheQ’sQ’sCacheCacheEventEventXXXXStateStateXXStateState00Original Original valuevalue55 11P reads P reads XX(Read (Read Miss)Miss)5555ROROComputer Science and EngineeringCopyright by Hesham El-RewiniWrite OnceThis write-invalidate protocol, which This write-invalidate protocol, which was proposed by Goodman in 1983 uses was proposed by Goodman in 1983 uses a combination of write-through and a