Lecture 18: Multiprocessors 2: Snooping v. Directory Coherency, Memory Consistency ModelsReview: Parallel FrameworkReview : Small-Scale MP DesignsDistributed Directory MPsRevised Snoopy-Cache State MachineSnoop Cache ExtensionsExampleExample: Step 1Example: Step 2Example: Step 3Example: Step 4Example: Step 5CS 252 AdministriviaSnooping Coherncy Implementation ComplicationsImplementing Snooping CachesSlide 16Larger MPsDirectory ProtocolSlide 19Directory Protocol MessagesState Transition Diagram for an Individual Cache Block in a Directory Based SystemCPU -Cache State MachineState Transition Diagram for the DirectoryDirectory State MachineExample Directory ProtocolSlide 26Slide 27Slide 28Slide 29Slide 30Slide 31Slide 32Implementing a DirectorySynchronizationUninterruptable Instruction to Fetch and Update MemorySlide 36User Level Synchronization—Operation Using this PrimitiveAnother MP Issue: Memory Consistency ModelsMemory Consistency ModelReviewDAP Spr.‘98 ©UCB 1Lecture 18: Multiprocessors 2: Snooping v. Directory Coherency, Memory Consistency Models Professor David A. PattersonComputer Science 252Spring 1998DAP Spr.‘98 ©UCB 2Review: Parallel Framework•Layers:–Programming Model:»Multiprogramming : lots of jobs, no communication»Shared address space: communicate via memory»Message passing: send and recieve messages»Data Parallel: several agents operate on several data sets simultaneously and then exchange information globally and simultaneously (shared or message passing)–Communication Abstraction:»Shared address space: e.g., load, store, atomic swap»Message passing: e.g., send, recieve library calls»Debate over this topic (ease of programming, scaling) => many hardware designs 1:1 programming modelProgramming ModelCommunication AbstractionInterconnection SW/OS Interconnection HWDAP Spr.‘98 ©UCB 3Review : Small-Scale MP Designs•Memory: centralized with uniform access time (“uma”) and bus interconnect•Examples: Sun Enterprise 5000 , SGI Challenge, Intel SystemProDAP Spr.‘98 ©UCB 4Distributed Directory MPsDAP Spr.‘98 ©UCB 5Revised Snoopy-Cache State Machine•State machinefor CPU and bus requestsfor each memory block•Invalid stateif in memoryRemote Writeor Miss due toaddress conflictWrite back blockRemote Write or Miss due toaddress conflictInvalidShared(read/only)Exclusive(read/write)CPU ReadCPU Read hitPlace read misson busPlace Write Miss on busCPU WritePlace Write Miss on BusCPU read hitCPU write hitCPU WriteRemote ReadWrite back blockDAP Spr.‘98 ©UCB 6RemoteReadPlace Data on Bus?Snoop Cache ExtensionsExtensions: –Fourth State: Ownership–Shared-> Modified, need invalidate only (upgrade request), don’t read memoryBerkeley Protocol–Clean exclusive state (no miss for private data on write)MESI Protocol–Cache supplies data when shared state (no memory access)Illinois ProtocolRemote Writeor Miss due toaddress conflictWrite back blockRemote Write or Miss due toaddress conflictInvalidShared(read/only)Modified(read/write)CPU Read hitCPU Read Place read miss on busCPU Write Place Write Miss on busCPU WritePlace Write Miss on Bus?CPU read hitCPU write hitExclusive (read/only)CPU WritePlace Write Miss on Bus?CPU Read hitRemote ReadWrite back blockDAP Spr.‘98 ©UCB 7ExampleP1 P2 Bus Memorystep State Addr Value StateAddrValueActionProc.AddrValueAddrValueP1: Write 10 to A1P1: Read A1P2: Read A1P2: Write 20 to A1P2: Write 40 to A2Assumes initial cache state is invalid and A1 and A2 map to same cache block,but A1 ≠ A2Processor 1 Processor 2BusMemoryRemote Writeor MissWrite BackRemote Write or MissInvalidSharedExclusiveCPU Read hitRead miss on busWrite miss on busCPU WritePlace Write Miss on BusCPU read hitCPU write hitRemote Read Write BackDAP Spr.‘98 ©UCB 8Example: Step 1P1 P2 Bus Memorystep State Addr Value StateAddrValueActionProc.AddrValueAddrValueP1: Write 10 to A1 Excl. A1 10 WrMs P1 A1P1: Read A1P2: Read A1P2: Write 20 to A1P2: Write 40 to A2Assumes initial cache state is invalid and A1 and A2 map to same cache block,but A1 ≠ A2.Active arrow =Remote Writeor MissWrite BackRemote Write or MissInvalidSharedExclusiveCPU Read hitRead miss on busWrite miss on busCPU WritePlace Write Miss on BusCPU read hitCPU write hitRemote Read Write BackDAP Spr.‘98 ©UCB 9P1 P2 Bus Memorystep State Addr Value StateAddrValueActionProc.AddrValueAddrValueP1: Write 10 to A1 Excl. A1 10 WrMs P1 A1P1: Read A1 Excl. A1 10P2: Read A1P2: Write 20 to A1P2: Write 40 to A2Example: Step 2Assumes initial cache state is invalid and A1 and A2 map to same cache block,but A1 ≠ A2Remote Writeor MissWrite BackRemote Write or MissInvalidSharedExclusiveCPU Read hitRead miss on busWrite miss on busCPU WritePlace Write Miss on BusCPU read hitCPU write hitRemote Read Write BackDAP Spr.‘98 ©UCB 10Example: Step 3P1 P2 Bus Memorystep State Addr Value StateAddrValueActionProc.AddrValueAddrValueP1: Write 10 to A1 Excl. A1 10 WrMs P1 A1P1: Read A1 Excl. A1 10P2: Read A1 Shar. A1 RdMs P2 A1Shar. A1 10 WrBk P1 A1 10 10Shar. A1 10 RdDa P2 A1 10 10P2: Write 20 to A1 10P2: Write 40 to A2 1010Assumes initial cache state is invalid and A1 and A2 map to same cache block,but A1 ≠ A2.Remote Writeor MissWrite BackRemote Write or MissInvalidSharedExclusiveCPU Read hitRead miss on busWrite miss on busCPU WritePlace Write Miss on BusCPU read hitCPU write hitRemote Read Write BackA1DAP Spr.‘98 ©UCB 11Example: Step 4P1 P2 Bus Memorystep State Addr Value StateAddrValueActionProc.AddrValueAddrValueP1: Write 10 to A1 Excl. A1 10 WrMs P1 A1P1: Read A1 Excl. A1 10P2: Read A1 Shar. A1 RdMs P2 A1Shar. A1 10 WrBk P1 A1 10 10Shar. A1 10 RdDa P2 A1 10 10P2: Write 20 to A1 Inv. Excl. A1 20 WrMs P2 A1 10P2: Write 40 to A2 1010Assumes initial cache state is invalid and A1 and A2 map to same cache block,but A1 ≠ A2Remote Writeor MissWrite BackRemote Write or MissInvalidSharedExclusiveCPU Read hitRead miss on busWrite miss on busCPU WritePlace Write Miss on BusCPU read hitCPU write hitRemote Read Write BackA1DAP Spr.‘98 ©UCB 12Remote Writeor MissWrite BackRemote Write or MissInvalidSharedExclusiveCPU Read hitRead miss on busWrite miss on busCPU WritePlace Write Miss on BusCPU read hitCPU write hitRemote Read Write BackExample: Step 5P1 P2 Bus Memorystep State Addr Value StateAddrValueActionProc.AddrValueAddrValueP1: Write 10 to A1 Excl. A1 10 WrMs P1 A1P1: Read A1 Excl. A1 10P2: Read A1 Shar. A1 RdMs P2 A1Shar. A1 10 WrBk P1 A1 10 10Shar. A1 10 RdDa P2 A1 10 10P2: Write 20
View Full Document
Unlocking...