Invalidation based Protocols When write W is performed w r t any processor all previous writes in bus order have completed makes the write visible i e write is performed may be actually observed by a read miss only later write hit made visible performed when block updated in writer s cache Only one RdX can succeed at a time for a block serialized by bus Tells others about impending write obtains exclusive ownership note replaced block that is not in modified state can be dropped Writeback transactions also but not caused by memory operation and quite incidental to coherence protocol Read and Read exclusive bus transactions drive coherence actions Store to non dirty data generates a read exclusive bus transaction i e without bus transaction Must first get block in exclusive state before writing into it Even if already in valid state need transaction so called a write miss Exclusive means can modify without notifying anyone else since it caused a bus transaction 35 33 If read obtains value of write W W guaranteed to have completed Writes and read misses to all locations serialized by bus into bus order Extend arguments used for coherence Provides SC not just coherence SC in Write through Example Extend cache controller and exploit bus provides serialization Owner responsible for supplying block upon a request for it Exclusive only cache with a valid copy main memory may be too Set of states New update bus transaction In invalidation protocols they would miss and cause more transactions Also only the word written is transferred not whole block Single bus transaction to update several caches can save bandwidth Other processors don t miss on next access reduced latency In invalidation first write gets exclusive ownership others local Multiple writes by same processor cause multiple update transactions Detailed tradeoffs more complex Disadvantages Advantages A write operation updates values in other caches Update based Protocols Invalidation versus Update based protocols Design space Dirty state now also indicates exclusive ownership Focus on protocols for write back caches No need to change processor main memory cache Design Space for Snooping Protocols 36 34 and clears out copies that won t be used again single bus transaction to update all copies No multiple useless updates even to dead copies Yes readers will not miss if they had a copy previously Already have latest data can use upgrade BusUpgr instead of BusRdX I BusRdX BusRdX Flush BusRd Flush PrRd BusRd S M PrWr Replacement changes state of two blocks outgoing and incoming Write to shared block PrWr BusRdX PrRd BusRd PrWr BusRdX PrRd State Transition Diagram Some systems provide both or even hybrid Need to look at program behavior and hardware complexity Invalidation protocols much more popular more later Update Yes readers will take a miss No multiple writes without additional traffic 39 37 Is a block written by one processor read by others before it is rewritten Invalidation Basic question of program behavior Invalidate versus Update PrWr write PrRd read BusRd asks for copy with no intent to modify BusRdX asks for copy with intent to modify BusWB updates memory Satisfying Coherence Update state perform bus transaction flush value onto bus 38 40 sequence of such writes between two bus xactions for the block must come from same processor say P in serialization the sequence appears between these two bus xactions reads by P will seem them in this order w r t other bus transactions reads by other processors separated from sequence by a bus xaction which places them in the serialized order w r t the writes so reads by all processors see writes in same order Write that don t appear on the bus Write performed in writer s cache before it handles other transactions so ordered in same way even w r t writer Reads that appear on the bus ordered wrt these All writes that appear on the bus BusRdX ordered by the bus Write serialization Write propagation is clear Actions Bus Transactions Processor Events Invalid I Shared S one or more Dirty or Modified M one only States Basic MSI Writeback Inval Protocol Mj subsequent to Mi if I follows in program order on same processor ii Mj generates bus xaction that follows the memory operation for Mi Writes from other processors by the previous bus xaction P issued Writes from P by program order MESI 4 state Invalidation Protocol e g even in sequential program BusRd I S followed by BusRdX or BusUpgr S M Reading and modifying data is 2 bus xactions even if noone sharing needs shared signal on bus wired or line asserted in response to BusRd I E on PrRd if noone else has copy invalid exclusive or exclusive clean only this cache has copy but not modified shared two or more caches may have copies modified dirty States Main memory is up to date so cache not necessarily owner Add exclusive state write locally without xaction but not modified Problem with MSI protocol 43 41 Write completion can detect when write appears on bus Write atomicity if a read returns the value of a write that write has already become visible to all others already can reason different cases 2 Show sufficient conditions are satisfied In segment between two bus transactions any interleaving of ops from different processors leads to consistent total order In such a segment writes observed by processor P serialized as follows Bus imposes total order on bus xactions for all locations Between xactions procs perform reads writes locally in program order So any execution defines a natural partial order 1 Appeal to definition Satisfying Sequential Consistency good for mostly read data what about migratory data I read and write then you read and write then X reads and writes better to go to I state so I don t have to be invalidated on your write Sequent Symmetry and MIT Alewife use adaptive protocols Synapse transitioned to I state S assumption that I ll read again soon rather than other will write PrRd BusRd S I PrRd BusRd S BusRdX Flush BusRdX Flush BusRdX Flush BusRd Flush PrRd BusRd Flush S PrRd E BusRd Flush 42 44 BusRd S means shared line asserted on BusRd transaction Flush if cache to cache sharing see next only one cache flushes data MOESI protocol Owned state exclusive but memory not valid PrWr BusRdX PrWr BusRdX PrWr M PrRd PrWr MESI State Transition Diagram Choices can affect performance of memory system later Depends on expectations of access patterns BusRd observed in M state what transitition to make Lower level Protocol Choices