CSE 8383 - Advanced Computer ArchitectureContentsMIMD Shared Memory SystemsShared MemorySingle Processor cachingCache Coherence PoliciesWriting in the cacheCache CoherenceSlide 9Write-invalidateWrite-UpdateSnooping ProtocolsWrite Invalidate Write ThroughWrite Through- Write Invalidate (cont.)Slide 15Example 1Complete the table (Write through write invalidate)Write Back- Write Invalidate (ownership)Write Back- Write Invalidate (ownership) (cont.)Ownership (cont.)Slide 21Example –2 Complete the table (Ownership)Write OnceWrite Once (cont.)Write Once (Cont.)Slide 26Write update and partial write throughWrite update and partial write through (cont.)Slide 29Slide 30Write Update Write BackWrite Update Write Back (cont.)Slide 33Slide 34Directory Based ProtocolsDirectory Based Protocols (cont.)What is a directory?Centralized vs. DistributedProtocol CategorizationFull Map DirectorySlide 41Limited DirectorySlide 43Chained DirectorySlide 45Centralized Directory InvalidateWrite by P3Scalable Coherent Interface (SCI)SCI ScenariosSCI Scenarios (Cont.)SCI – Sharing List AdditionSlide 52SCI-- Head Purging Other EntriesStanford Distributed Directory (SDD)SDD ScenariosSDD– List AdditionSDD Scenarios (cont.)Slide 58SDD- Write Miss List RemovalTask CreationSerial vs. Parallel ProcessCommunication via Shared dataSynchronizationBarriersCSE 8383 - Advanced Computer ArchitectureWeek-9Week of March 15, 2004engr.smu.edu/~rewini/8383ContentsMidtermProject ProposalsShared MemorySnooping ProtocolsDirectory Based ProtocolsShared Memory ProgrammingMIMD Shared Memory SystemsInterconnection NetworksM M M MP P P P PShared Memory Single address spaceCommunication via read & writeSynchronization via locksSingle Processor cachingPx x MemoryCacheHit: data in the cacheMiss: data is not in the cacheHit rate: hMiss rate: m = (1-h)Cache Coherence PoliciesWriting to Cache in 1 processor caseWrite ThroughWrite BackWriting in the cachePx xBeforeMemoryCachePx’ x’Write throughMemoryCachePx’ xWrite backMemoryCacheCache CoherenceP1xP2 P3 xPn xx-Multiple copies of x-What if P1 updates x?Cache Coherence PoliciesWriting to Cache in n processor caseWrite Update - Write ThroughWrite Invalidate - Write BackWrite Update - Write ThroughWrite Invalidate - Write BackWrite-invalidateP1xP2 P3 xxP1x’P2 P3 Ix’P1x’P2 P3 IxBefore Write ThroughWrite backWrite-UpdateP1xP2 P3 xxP1x’P2 P3 x’x’P1x’P2 P3 x’xBefore Write ThroughWrite backSnooping 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.Write 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.Write Through- Write Invalidate (cont.)State DescriptionValid[VALID]The copy is consistent with global memoryInvalid[INV]The copy is inconsistentWrite 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.Example 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 XComplete the table (Write through write invalidate) MemoryMemoryP’s P’s CacheCacheQ’sQ’sCacheCacheEventEventXXXXStateStateXXStateState00Original Original valuevalue55 11P reads P reads XX(Read (Read Miss)Miss)5555VALIDVALIDWrite 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.Write 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 inconsistentOwnership (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.Ownership (cont.)Write Hit If the copy is Exclusive (Read-Write), perform the write locally. If the state is Shared (Read-Only),