1Lecture 20: Coherence protocols• Topics: snooping and directory-based coherenceprotocols (Sections 4.1-4.3)2SMP ExampleProcessorACachesProcessorBCachesProcessorCCachesProcessorDCachesMain MemoryI/O SystemA: Rd XB: Rd XC: Rd XA: Wr XA: Wr XC: Wr XB: Rd XA: Rd XA: Rd YB: Wr XB: Rd YB: Wr XB: Wr Y3SMP ExampleA: Rd X B: Rd X C: Rd X A: Wr X A: Wr X C: Wr X B: Rd X A: Rd XA: Rd YB: Wr X B: Rd YB: Wr X B: Wr YA B C4SMP ExampleA: Rd X SB: Rd X S SC: Rd X S S SA: Wr X E I IA: Wr X E I IC: Wr X I I EB: Rd X I S SA: Rd X S S SA: Rd Y S (Y) S (X) S (X)B: Wr X S (Y) E (X) IB: Rd Y S (Y) S (Y) IB: Wr X S (Y) E (X) IB: Wr Y I E (Y) IA B C5Design Issues• Invalidate• Find data• Writeback / writethroughProcessorCachesProcessorCachesProcessorCachesProcessorCachesMain MemoryI/O System• Cache block states• Contention for tags• Enforcing write serialization6Cache Coherence Protocols• Directory-based: A single location (directory) keeps trackof the sharing status of a block of memory• Snooping: Every cache block is accompanied by the sharingstatus of that block – all cache controllers monitor theshared bus so they can update the sharing status of theblock, if necessary Write-invalidate: a processor gains exclusive access ofa block before writing by invalidating all other copies Write-update: when a processor writes, it updates othershared copies of that block7Example ProtocolRequest Source Block state ActionRead hit Proc Shared/excl Read data in cacheRead miss Proc Invalid Place read miss on busRead miss Proc Shared Conflict miss: place read miss on busRead miss Proc Exclusive Conflict miss: write back block, place read miss on busWrite hit Proc Exclusive Write data in cacheWrite hit Proc Shared Place write miss on busWrite miss Proc Invalid Place write miss on busWrite miss Proc Shared Conflict miss: place write miss on busWrite miss Proc Exclusive Conflict miss: write back, place write miss on busRead miss Bus Shared No action; allow memory to respondRead miss Bus Exclusive Place block on bus; change to sharedWrite miss Bus Shared Invalidate blockWrite miss Bus Exclusive Write back block; change to invalid8Performance Improvements• What determines performance on a multiprocessor: What fraction of the program is parallelizable? How does memory hierarchy performance change?• New form of cache miss: coherence miss – such a misswould not have happened if another processor did notwrite to the same cache line• False coherence miss: the second processor writes to adifferent word in the same cache line – this miss wouldnot have happened if the line size equaled one word9How do Cache Misses Scale?Compulsory Capacity Conflict CoherenceTrue FalseIncreasing cache capacityIncreasing processor countIncreasing block sizeIncreasing associativity10Simplifying Assumptions• All transactions on a read or write are atomic – on a writemiss, the miss is sent on the bus, a block is fetched frommemory/remote cache, and the block is marked exclusive• Potential problem if the actions are non-atomic: P1 sendsa write miss on the bus, P2 sends a write miss on the bus:since the block is still invalid in P1, P2 does not realize thatit should write after receiving the block from P1 – instead, itreceives the block from memory• Most problems are fixable by keeping track of more state:for example, don’t acquire the bus unless all outstandingtransactions for the block have completed11Directory-Based Cache Coherence• The physical memory is distributed among all processors• The directory is also distributed along with thecorresponding memory• The physical address is enough to determine the locationof memory• The (many) processing nodes are connected with ascalable interconnect (not a bus) – hence, messagesare no longer broadcast, but routed from sender toreceiver – since the processing nodes can no longersnoop, the directory keeps track of sharing state12Distributed Memory MultiprocessorsProcessor& CachesMemory I/OProcessor& CachesMemory I/OProcessor& CachesMemory I/OProcessor& CachesMemory I/OInterconnection networkDirectory Directory Directory Directory13Cache Block States• What are the different states a block of memory can havewithin the directory?• Note that we need information for each cache so thatinvalidate messages can be sent• The block state is also stored in the cache for efficiency• The directory now serves as the arbitrator: if multiple write attempts happen simultaneously, the directorydetermines the ordering14Directory-Based ExampleProcessor& CachesMemory I/OProcessor& CachesMemory I/OProcessor& CachesMemory I/OInterconnection networkDirectoryDirectoryX DirectoryY A: Rd XB: Rd XC: Rd XA: Wr XA: Wr XC: Wr XB: Rd XA: Rd XA: Rd YB: Wr XB: Rd YB: Wr XB: Wr Y15Directory Actions• If block is in uncached state: Read miss: send data, make block shared Write miss: send data, make block exclusive• If block is in shared state: Read miss: send data, add node to sharers list Write miss: send data, invalidate sharers, make excl• If block is in exclusive state: Read miss: ask owner for data, write to memory, senddata, make shared, add node to sharers list Data write back: write to memory, make uncached Write miss: ask owner for data, write to memory, senddata, update identity of new owner, remain exclusive16Title•
View Full Document
Unlocking...