Scalable Cache Coherent SystemsFunctionality Expected In A Cache Coherent SystemBus-Based CoherenceScalable Cache CoherenceApproach #1: Hierarchical SnoopingHierarchical Snoopy Cache CoherenceBus Hierarchies with Centralized MemoryBus Hierarchies with Centralized Memory Advantages and DisadvantagesBus Hierarchies with Distributed MemoryScalable Approach #2: DirectoriesOrganizing DirectoriesBasic Operation of Centralized DirectoryDistributed, Flat, Memory-based SchemesBasic Operation of Distributed, Flat, Memory-based DirectoryReducing Storage Overhead of Distributed Memory-based DirectoriesFlat, Cache-based SchemesScaling Properties of Cache-based SchemesHow Hierarchical Directories WorkHow to Find Directory InformationHow Is Location of Copies Stored?Summary of Directory OrganizationsSummary of Directory ApproachesApproach #3: A Popular Middle Ground Two-level “Hierarchy”Example Two-level HierarchiesAdvantages of Multiprocessor NodesDisadvantages of Coherent MP NodesEECC756 - ShaabanEECC756 - Shaaban#1 lec # 14 Spring2002 5-9-2002Scalable Cache Coherent SystemsScalable Cache Coherent Systems•Scalable distributed shared memory machines Assumptions: –Processor-Cache-Memory nodes connected by scalable network.–Distributed shared physical address space.–Communication assist must interpret network transactions, forming shared address space.•For a system with shared physical address space:–A cache miss must be satisfied transparently from local or remote memory depending on address.–By its normal operation, cache replicates data locally resulting in a potential cache coherence problem between local and remote copies of data.–A coherency solution must be in place for correct operation.•Standard snoopy protocols studied earlier do not apply for lack of a bus or a broadcast medium to snoop on.•For this type of system to be scalable, in addition to latency and bandwidth scalability, the cache coherence protocol or solution used must also scale as well.EECC756 - ShaabanEECC756 - Shaaban#2 lec # 14 Spring2002 5-9-2002Functionality Expected In A Cache Coherent SystemFunctionality Expected In A Cache Coherent System•Provide a set of states, a state transition diagram, and actions representing the cache coherence protocol used.•Manage coherence protocol:(0) Determine when to invoke the coherence protocol(a) Find source of information about state of cache line in other caches•Whether need to communicate with other cached copies(b) Find out the location or locations of other copies if any.(c) Communicate with those copies (invalidate/update).•(0) is done the same way on all cache coherent systems:–State of the local cache line is maintained in the cache.–Protocol is invoked if an “access fault” occurs on the line.•Different approaches distinguished by (a) to ( c ).EECC756 - ShaabanEECC756 - Shaaban#3 lec # 14 Spring2002 5-9-2002Bus-Based CoherenceBus-Based Coherence•All of (a), (b), (c) done through broadcast on the bus:–Faulting processor sends out a “search”. –Others respond to the search probe and take necessary action.•This approach could be done in a scalable network too:–Broadcast to all processors, and let them respond.–Conceptually simple, but broadcast doesn’t scale with p:•Bus bandwidth doesn’t scale.•On a scalable network (e.g MINs) , every fault may lead to at least p network transactions.EECC756 - ShaabanEECC756 - Shaaban#4 lec # 14 Spring2002 5-9-2002Scalable Cache CoherenceScalable Cache Coherence•A scalable cache coherence approach may have similar cache line states and state transition diagrams as in bus-based coherence protocols.•However, different additional mechanisms other than broadcasting must be devised to manage the coherence protocol.•Two possible approaches:–Approach #1: Hierarchical Snooping.–Approach #2: Directory-based cache coherence.–Approach #3: A combination of the above two approaches.EECC756 - ShaabanEECC756 - Shaaban#5 lec # 14 Spring2002 5-9-2002Approach #1: Hierarchical SnoopingApproach #1: Hierarchical Snooping•Extend snooping approach: A hierarchy of broadcast media:–Tree of buses or rings (KSR-1).–Processors are in the bus- or ring-based multiprocessors at the leaves.–Parents and children connected by two-way snoopy interfaces:•Snoop both buses and propagate relevant transactions.–Main memory may be centralized at root or distributed among leaves.•Issues (a) - (c) handled similarly to bus, but not full broadcast. –Faulting processor sends out “search” bus transaction on its bus.–Propagates up and down hierarchy based on snoop results.•Problems: –High latency: multiple levels, and snoop/lookup at every level.–Bandwidth bottleneck at root.•This approach has, for the most part, been abandoned.EECC756 - ShaabanEECC756 - Shaaban#6 lec # 14 Spring2002 5-9-2002Hierarchical Snoopy Cache CoherenceHierarchical Snoopy Cache CoherenceSimplest way: hierarchy of buses; snoopy coherence at each level.–or rings.• Consider buses. Two possibilities:(a) All main memory at the global (B2) bus.(b) Main memory distributed among the clusters.(a)(b)P PL1L1L2B1P PL1L1L2B1B2Main Memory (Mp)P PL2L1L1B1MemoryP PL1L1B1L2MemoryB2EECC756 - ShaabanEECC756 - Shaaban#7 lec # 14 Spring2002 5-9-2002Bus Hierarchies with Centralized MemoryBus Hierarchies with Centralized MemoryB1 follows standard snoopy protocol.Need a monitor per B1 bus: –Decides what transactions to pass back and forth between buses.–Acts as a filter to reduce bandwidth needs.Use L2 cache:• Much larger than L1 caches (set associative). Must maintain inclusion.• Has dirty-but-stale bit per line.• L2 cache can be DRAM based, since fewer references get to it.P PL1L1L2B1P PL1L1L2B1B2Main Memory (Mp)EECC756 - ShaabanEECC756 - Shaaban#8 lec # 14 Spring2002 5-9-2002Bus Hierarchies with Centralized MemoryBus Hierarchies with Centralized Memory Advantages and DisadvantagesAdvantages and Disadvantages•Advantages:–Simple extension of bus-based scheme.–Misses to main memory require single traversal to root of hierarchy.–Placement of shared data is not an issue.•Disadvantages:–Misses to local data (e.g., stack) also traverse hierarchy.–Higher traffic and latency.–Memory at global bus must be highly interleaved for bandwidth.EECC756 - ShaabanEECC756 - Shaaban#9 lec # 14 Spring2002 5-9-2002Bus Hierarchies with