COMP 206: Computer Architecture and ImplementationOutlineCache CoherenceExample of Cache CoherenceExample of Cache Coherence (contd)Two “Snoopy” ProtocolsNotation: Write-Through CacheNotation: Write-Back CacheThree-State Write-Invalidate ProtocolUnderstanding the ProtocolState Diagram of Cache Block (Part 1)State Diagram of Cache Block (Part 2)Comparison with Single WB CacheCorrectness of Three-State ProtocolAdding More Bits to ProtocolsMESI ProtocolState Diag. of MESI Cache Block (Part 1)State Diag. of MESI Cache Block (Part 2)Comparison with Three-State ProtocolComments on Write-Invalidate Protocols1COMP 206:COMP 206:Computer Architecture and Computer Architecture and ImplementationImplementationMontek SinghMontek SinghMon, Nov 14, 2005Mon, Nov 14, 2005Topic: Topic: Cache CoherenceCache Coherence2OutlineOutlineCache CoherenceCache CoherenceReading: HP3 Section 6.3 & Appendix IReading: HP3 Section 6.3 & Appendix I3Cache CoherenceCache CoherenceCommon problem with multiple copies of Common problem with multiple copies of mutable information (in both hardware and mutable information (in both hardware and software)software)““If a datum is copied and the copy is to match the If a datum is copied and the copy is to match the original at all times, then all changes to the original original at all times, then all changes to the original must cause the copy to be must cause the copy to be immediatelyimmediately updated or updated or invalidated.” (Richard L. Sites, co-architect of DEC invalidated.” (Richard L. Sites, co-architect of DEC Alpha)Alpha)1 2 3 4A A A C- A B BCopy becomes staleCopies diverge;hard to recover from1 2 3 4A A A B- A B BWrite update1 2 3 4A A A -- A B BWrite invalidate4Example of Cache CoherenceExample of Cache CoherenceI/O in uniprocessor with primary unified cacheI/O in uniprocessor with primary unified cacheMM copy and cache copy of memory block not always coherentMM copy and cache copy of memory block not always coherentWT cacheWT cacheMM copy stale while write update to MM in transitMM copy stale while write update to MM in transitWB cacheWB cacheMM copy stale while cache copy DirtyMM copy stale while cache copy DirtyInconsistency of no concern if no one reads/writes MM copyInconsistency of no concern if no one reads/writes MM copyIf I/O directed to main memory, need to maintain coherenceIf I/O directed to main memory, need to maintain coherence INPUT OUTPUT WT WB WB WT Block in cache Invalidate cache block, then I/O writes MM Evict block, then I/O writes MM Evict block, then I/O reads MM (MM not stale) I/O reads MM Block not in cache I/O writes MM I/O writes MM I/O reads MM I/O reads MM5Example of Cache Coherence Example of Cache Coherence (contd)(contd)Uniprocessor with a split primary cacheUniprocessor with a split primary cacheI-cache contains instructionI-cache contains instructionD-cache contains dataD-cache contains dataOften contents are disjointOften contents are disjointIf self-modifying code is allowed, then same cache If self-modifying code is allowed, then same cache block may appear in both caches, and consistency block may appear in both caches, and consistency must be enforcedmust be enforcedMS-DOS allows self-modifying codeMS-DOS allows self-modifying codeStrong motivation for unified caches in Intel i386 and i486Strong motivation for unified caches in Intel i386 and i486Pentium has split primary cache, and supports SMC by Pentium has split primary cache, and supports SMC by enforcing coherence between I and D cachesenforcing coherence between I and D cachesCoordinating primary and secondary caches in Coordinating primary and secondary caches in uniprocessoruniprocessorShared memory multiprocessorsShared memory multiprocessors6Two “Snoopy” ProtocolsTwo “Snoopy” ProtocolsWe will discuss two protocolsWe will discuss two protocolsA simple three-state protocolA simple three-state protocolSection 6.3 & Appendix I of HP3Section 6.3 & Appendix I of HP3The MESI protocolThe MESI protocolIEEE standardIEEE standardUsed by many machines, including Pentium and PowerPC Used by many machines, including Pentium and PowerPC 601601Snooping:Snooping:monitor memory bus activity by individual cachesmonitor memory bus activity by individual cachestaking some actions based on this activitytaking some actions based on this activityintroduces a fourth category of miss to the 3C model: introduces a fourth category of miss to the 3C model: coherence missescoherence missesFirst, we need some notation to discuss the First, we need some notation to discuss the protocolsprotocols7Notation: Write-Through CacheNotation: Write-Through Cache(State) Read hit Write hit Read miss Write miss (CPU inputs) Invalid N/A N/A Valid Valid (Next state) N/A N/A Bus read miss Bus write miss (Action) Valid Valid Valid Valid Valid (Next state) CPU reads cache -Bus write -CPU writes cache Bus read miss Bus write miss (Action)8Notation: Write-Back CacheNotation: Write-Back Cache(State) Read hit Write hit Read miss Write miss (CPU inputs) Invalid N/A N/A Clean Dirty (Next state) N/A N/A Bus read miss Bus write miss (Action) Clean Clean Dirty Clean Dirty (Next state) CPU reads cache CPU writes cache Bus read miss Bus write miss (Action) Dirty Dirty Dirty Clean Dirty (Next state) CPU reads cache CPU writes cache -Evict block -Bus read miss Evict block Bus write miss (Action)9Three-State Write-Invalidate Three-State Write-Invalidate ProtocolProtocolMinor modification of WB cacheMinor modification of WB cacheAssumptionsAssumptionsSingle bus and MMSingle bus and MMTwo or more CPUs, each with WB cacheTwo or more CPUs, each with WB cacheEvery cache block in one of three states: Every cache block in one of three states: InvalidInvalid, , CleanClean, , DirtyDirty (called Invalid, Shared, Exclusive in Figure 6.10 of (called Invalid, Shared, Exclusive in Figure 6.10 of HP3)HP3)MM copies of blocks have no stateMM copies of blocks have no stateAt any moment, a single cache owns bus (is bus At any moment, a single cache owns bus (is bus master)master)Bus master does not obey bus commandBus master does not obey bus commandAll misses (reads or writes) serviced byAll misses (reads or writes) serviced byMM if all cache copies are MM if all cache copies are CleanCleanthe only the only