Unformatted text preview:

33SC in Write-through ExampleProvides SC, not just coherenceExtend arguments used for coherence•Writes and read misses to all locations serialized by bus into bus order•If read obtains value of write W, W guaranteed to have completed–since it caused a bus transaction•When write W is performed w.r.t. any processor, all previous writes inbus order have completed34Design Space for Snooping ProtocolsNo need to change processor, main memory, cache …•Extend cache controller and exploit bus (provides serialization)Focus on protocols for write-back cachesDirty state now also indicates exclusive ownership•Exclusive: only cache with a valid copy (main memory may be too)•Owner: responsible for supplying block upon a request for itDesign space• Invalidation versus Update-based protocols• Set of states35Invalidation-based ProtocolsExclusive means can modify without notifying anyone else•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 missStore to non-dirty data generates a read-exclusive bus transaction•Tells others about impending write, obtains exclusive ownership–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 busRead and Read-exclusive bus transactions drive coherence actions•Writeback transactions also, but not caused by memory operation andquite incidental to coherence protocol–note: replaced block that is not in modified state can be dropped36Update-based ProtocolsA write operation updates values in other caches•New, update bus transactionAdvantages•Other processors don’t miss on next access: reduced latency–In invalidation protocols, they would miss and cause more transactions•Single bus transaction to update several caches can save bandwidth–Also, only the word written is transferred, not whole blockDisadvantages•Multiple writes by same processor cause multiple update transactions–In invalidation, first write gets exclusive ownership, others localDetailed tradeoffs more complex37Invalidate versus UpdateBasic question of program behavior•Is a block written by one processor read by others before it is rewritten?Invalidation:•Yes => readers will take a miss•No => multiple writes without additional traffic–and clears out copies that won’t be used againUpdate:•Yes => readers will not miss if they had a copy previously–single bus transaction to update all copies•No => multiple useless updates, even to dead copiesNeed to look at program behavior and hardware complexityInvalidation protocols much more popular (more later)•Some systems provide both, or even hybrid38Basic MSI Writeback Inval ProtocolStates•Invalid (I)•Shared (S): one or more•Dirty or Modified (M): one onlyProcessor Events:•PrRd (read)•PrWr (write)Bus Transactions•BusRd: asks for copy with no intent to modify•BusRdX: asks for copy with intent to modify•BusWB: updates memoryActions•Update state, perform bus transaction, flush value onto bus39State Transition Diagram•Write to shared block:–Already have latest data; can use upgrade (BusUpgr) instead of BusRdX•Replacement changes state of two blocks: outgoing and incomingPrRd/—PrRd/—PrWr/BusRdXBusRd/—PrWr/—SMIBusRdX/FlushBusRdX/—BusRd/FlushPrWr/BusRdXPrRd/BusRd40Satisfying CoherenceWrite propagation is clearWrite serialization?•All writes that appear on the bus (BusRdX) ordered by the bus–Write performed in writer’s cache before it handles other transactions, soordered in same way even w.r.t. writer•Reads that appear on the bus ordered wrt these•Write that don’t appear on the bus:–sequence of such writes between two bus xactions for the block must comefrom 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, whichplaces them in the serialized order w.r.t the writes–so reads by all processors see writes in same order41Satisfying Sequential Consistency1. Appeal to definition:•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–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•In segment between two bus transactions, any interleaving of ops fromdifferent processors leads to consistent total order•In such a segment, writes observed by processor P serialized as follows–Writes from other processors by the previous bus xaction P issued–Writes from P by program order2. Show sufficient conditions are satisfied•Write completion: can detect when write appears on bus•Write atomicity: if a read returns the value of a write, that write hasalready become visible to all others already (can reason different cases)42Lower-level Protocol ChoicesBusRd observed in M state: what transitition to make?Depends on expectations of access patterns•S: assumption that I’ll read again soon, rather than other will write–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• Synapse transitioned to I state• Sequent Symmetry and MIT Alewife use adaptive protocolsChoices can affect performance of memory system (later)43MESI (4-state) Invalidation ProtocolProblem with MSI protocol•Reading and modifying data is 2 bus xactions, even if noone sharing–e.g. even in sequential program–BusRd (I->S) followed by BusRdX or BusUpgr (S->M)Add exclusive state: write locally without xaction, but not modified•Main memory is up to date, so cache not necessarily owner•States–invalid–exclusive or exclusive-clean (only this cache has copy, but not modified)–shared (two or more caches may have copies)–modified (dirty)•I -> E on PrRd if noone else has copy–needs “shared” signal on bus: wired-or line asserted in response to BusRd44MESI State Transition Diagram•BusRd(S) means shared line asserted on BusRd


View Full Document

TAMU ECEN 676 - ch5_2

Documents in this Course
ch4_3

ch4_3

8 pages

ch3_2

ch3_2

23 pages

Load more
Download ch5_2
Our administrator received your request to download this document. We will send you the file to your email shortly.
Loading Unlocking...
Login

Join to view ch5_2 and access 3M+ class-specific study document.

or
We will never post anything without your permission.
Don't have an account?
Sign Up

Join to view ch5_2 2 2 and access 3M+ class-specific study document.

or

By creating an account you agree to our Privacy Policy and Terms Of Use

Already a member?