Carnegie MellonSchool of Computer Science1ArchitectureMemory Consistency ModelsAdam Wierman Daniel NeillAdve, Pai, and Ranganathan. Recent advances in memory consistency models for hardware shared-memory systems, 1999.Gniady, Falsafi, and Vijaykumar. Is SC+ILP=RC?, 1999.Hill. Multiprocessors should support simple memory consistency models, 1998.Carnegie MellonSchool of Computer Science2ArchitectureMemory consistency models• The memory consistency model of a shared-memory system determines the order in which memory operations will appear to execute to the programmer.– Processor 1 writes to some memory location…– Processor 2 reads from that location…– Do I get the result I expect?• Different models make different guarantees; the processor can reorder/overlap memory operations as long as the guarantees are upheld.Tradeoff between programmabilityand performance!Carnegie MellonSchool of Computer Science3ArchitectureCode example 1Data1 = 64Data2 = 55Flag = 1while (Flag != 1) {;}register1 = Data1 register2 = Data2P2P1initially Data1 = Data2 = Flag = 0What should happen?Carnegie MellonSchool of Computer Science4ArchitectureCode example 1Data1 = 64Data2 = 55Flag = 1while (Flag != 1) {;}register1 = Data1 register2 = Data2P2P1initially Data1 = Data2 = Flag = 0What could gowrong?Carnegie MellonSchool of Computer Science5ArchitectureThree models of memory consistency• Sequential Consistency (SC):– Memory operations appear to execute one at a time, in some sequential order.– The operations of each individual processor appear to execute in program order.• Processor Consistency (PC):– Allows reads following a write to execute out of program order (if they’re not reading/writing the same address!)– Writes may not be immediately visible to other processors, but become visible in program order.• Release Consistency (RC):– All reads and writes (to different addresses!) are allowed to operate out of program order.Carnegie MellonSchool of Computer Science6ArchitectureCode example 1Data1 = 64Data2 = 55Flag = 1while (Flag != 1) {;}register1 = Data1 register2 = Data2P2P1initially Data1 = Data2 = Flag = 0Does it work under:• SC (no relaxation)?• PC (Write→Read relaxation)?• RC (all relaxations)?Carnegie MellonSchool of Computer Science7ArchitectureCode example 2Flag1 = 1register1 = Flag2if (register1 == 0)critical sectionP2P1initially Flag1 = Flag2 = 0Flag2 = 1register2 = Flag1if (register2 == 0)critical sectionWhat should happen?Carnegie MellonSchool of Computer Science8ArchitectureCode example 2Flag1 = 1register1 = Flag2if (register1 == 0)critical sectionP2P1initially Flag1 = Flag2 = 0Flag2 = 1register2 = Flag1if (register2 == 0)critical sectionWhat could gowrong?Carnegie MellonSchool of Computer Science9ArchitectureCode example 2Flag1 = 1register1 = Flag2if (register1 == 0)critical sectionP2P1initially Flag1 = Flag2 = 0Flag2 = 1register2 = Flag1if (register2 == 0)critical sectionDoes it work under:• SC (no relaxation)?• PC (Write→Read relaxation)?• RC (all relaxations)?Carnegie MellonSchool of Computer Science10ArchitectureThe performance/programmability tradeoffIncreasing performanceIncreasing programmabilityCarnegie MellonSchool of Computer Science11ArchitectureProgramming difficulty• PC/RC include special synchronization operations to allow specific instructions to execute atomically and in program order.• The programmer must identify conflicting memory operations, and ensure that they are properly synchronized.• Missing or incorrect synchronization → program gives unexpected/incorrect results.• Too many unnecessary synchronizations → performance reduced (no better than SC?)Idea: normally ensure sequential consistency;allow programmer to specify when relaxation possible?Carnegie MellonSchool of Computer Science12ArchitectureCode example 1, revisitedData1 = 64Data2 = 55Flag = 1while (Flag != 1) {;}register1 = Data1 register2 = Data2P2P1initially Data1 = Data2 = Flag = 0MEMBAR (ST-ST)MEMBAR (LD-LD)Programmer adds synchronization commands…… and now it works as expected!Carnegie MellonSchool of Computer Science13ArchitecturePerformance of memory consistency models• Relaxed memory models (PC/RC) hide much of memory operations’ long latencies by reorderingand overlapping some or all memory operations.– PC/RC can use write buffering.– RC can be aggressively out of order.• This is particularly important:– When cache performance poor, resulting in many memory operations.– In distributed shared memory systems, when remote memory accesses may take much longer than local memory accesses.• Performance results for straightforward implementations: as compared to SC, PC and RC reduce execution time by 23% and 46% respectively (Adve et al).Carnegie MellonSchool of Computer Science14ArchitectureThe big questionHow can SC approach theperformance of RC?Carnegie MellonSchool of Computer Science15ArchitectureCompilerOptimizationsHardwareOptimizationsHow can SC approach RC?2 TechniquesCarnegie MellonSchool of Computer Science16ArchitectureHardwareOptimizationsWhat can SC do?Can SC haveper-processor caches?Can SC havenon-bindingprefetching?Can SC havemultithreading?Can SC use awrite buffer?YESYESYESNOSC cannot reorder memory operationsbecause it might cause inconsistency.Carnegie MellonSchool of Computer Science17ArchitectureHardwareOptimizationsSpeculation with SCSC only needs to appear to do memory operations in order1. Speculatively perform all memory operations2. Roll back to “sequentially consistent”state if constraints are violatedThis emulates RC as longas rollbacks are infrequent.Carnegie MellonSchool of Computer Science18ArchitectureHardwareOptimizationsSpeculation with SCSC only needs to appear to do memory operations in order1. Speculatively perform all memory operations2. Roll back to “sequentially consistent”state if constraints are violated• Must allow both loads and stores to bypass each other• Needs a very large speculative state• Don’t introduce overhead to the pipelineCarnegie MellonSchool of Computer Science19ArchitectureHardwareOptimizationsSpeculation with SCSC only needs to appear to do memory operations in order1. Speculatively perform all memory operations2. Roll back to “sequentially consistent”state if constraints are violated• Must detect violations quickly• Must be able to roll back quickly• Rollbacks can’t happen oftenCarnegie MellonSchool of Computer
View Full Document
Unlocking...