EECC756 - ShaabanEECC756 - Shaaban#1 lec # 11 Spring2002 4-25-2002Shared Memory MultiprocessorsShared Memory Multiprocessors• Symmetric Multiprocessors (SMPs):– Symmetric access to all of main memory from any processor.• Currently Dominate the high-end server market:– Building blocks for larger systems; arriving to desktop.• Attractive as high throughput servers and for parallelprograms:– Fine-grain resource sharing.– Uniform access via loads/stores.– Automatic data movement and coherent replication incaches.• Normal uniprocessor mechanisms used to access data(reads and writes).– Key is extension of memory hierarchy to support multipleprocessors.EECC756 - ShaabanEECC756 - Shaaban#2 lec # 11 Spring2002 4-25-2002Supporting Programming ModelsSupporting Programming Models• Address translation and protection in hardware(hardware SAS).• Message passing using shared memory buffers:• Can offer very high performance since no OS involvementnecessary.• The focus here is on supporting a coherent sharedaddress space.MultiprogrammingShared address spaceMessage passingProgramming modelsCommunication abstractionUser/system boundaryCompilationor libraryOperating systems supportCommunication hardwarePhysical communication mediumHardware/software boundaryEECC756 - ShaabanEECC756 - Shaaban#3 lec # 11 Spring2002 4-25-2002Shared Memory Multiprocessors VariationsShared Memory Multiprocessors VariationsI/O devicesMemP1$$PnP1SwitchMain memoryPn(Interleaved)(Interleaved)P1$Interconnection network$PnMemMem(b) Bus-based shared memory(c) Dancehall(a) Shared cacheFirst-level $BusP1$Interconnection network$PnMemMem(d) Distributed-memoryEECC756 - ShaabanEECC756 - Shaaban#4 lec # 11 Spring2002 4-25-2002Caches And Cache Coherence InCaches And Cache Coherence InShared Memory MultiprocessorsShared Memory Multiprocessors• Caches play a key role in all shared memoryMultiprocessor system variations:– Reduce average data access time.– Reduce bandwidth demands placed on shared interconnect.• Private processor caches create a problem:– Copies of a variable can be present in multiple caches.– A write by one processor may not become visible to others:• Processors accessing stale value in their private caches.– Process migration.– I/O activity.– Cache coherence problem.– Software and/or software actions needed to ensure write visibilityto all processors thus maintaining cache coherence.EECC756 - ShaabanEECC756 - Shaaban#5 lec # 11 Spring2002 4-25-2002Data Sharing/Process MigrationData Sharing/Process MigrationCache Coherence ProblemsCache Coherence Problems• See handout• Figure 7.12 in Advanced ComputerArchitecture: Parallelism, Scalability,Programmability, Kai Hwang.EECC756 - ShaabanEECC756 - Shaaban#6 lec # 11 Spring2002 4-25-2002I/O Operation Cache InconsistencyI/O Operation Cache Inconsistency• See handout• Figure 7.13 in Advanced ComputerArchitecture: Parallelism, Scalability,Programmability, Kai Hwang.EECC756 - ShaabanEECC756 - Shaaban#7 lec # 11 Spring2002 4-25-2002Shared cache Multiprocessor Systems:Shared cache Multiprocessor Systems:– Low-latency sharing and prefetching across processors.– Sharing of working sets.– No coherence problem (and hence no false sharing either).– But high bandwidth needs and negative interference (e.g.conflicts).– Hit and miss latency increased due to intervening switch andcache size.– Used in mid 80s to connect a few of processors on a board (Encore,Sequent).– Today: Promising for multiprocessor on a chip (for small-scalesystems or nodes).• Dancehall:– Not a popular design: Resources are uniformly costly to access forall processors.• Distributed memory:– Most popular design to build scalable systems (i.e. MPPs).EECC756 - ShaabanEECC756 - Shaaban#8 lec # 11 Spring2002 4-25-2002A Coherent Memory System: IntuitionA Coherent Memory System: Intuition• Reading a location should return latest value written (byany process).• Easy to achieve in uniprocessors:– Except for I/O: Coherence between I/O devices and processors.– Infrequent so software solutions work:• Uncacheable memory, uncacheable operations, flush pages, passI/O data through caches.• The same should hold when processes run on differentprocessors:– E.g. as if the processes were interleaved on a uniprocessor.• Coherence problem much more critical in multiprocessors:– Pervasive.– Performance-critical.– Must be treated as a basic hardware design issue.EECC756 - ShaabanEECC756 - Shaaban#9 lec # 11 Spring2002 4-25-2002Example Cache Coherence ProblemExample Cache Coherence Problem– Processors see different values for u after event 3.– With write back caches, a value updated in cache may not havebeen written back to memory:• Processes even accessing main memory may see very stale value.– Unacceptable to program correct execution.I/O devicesMemoryP1$ $$P2P312345u = ?u = ?u:5u:5u:5u = 7EECC756 - ShaabanEECC756 - Shaaban#10 lec # 11 Spring2002 4-25-2002Basic DefinitionsBasic DefinitionsExtend definitions in uniprocessors to multiprocessors:• Memory operation: a single read (load), write (store) or read-modify-write access to a memory location.– Assumed to execute atomically w.r.t each other.• Issue: A memory operation issues when it leaves processor’s internalenvironment and is presented to memory system (cache, buffer …).• Perform: operation appears to have taken place, as far as processorcan tell from other memory operations it issues.– A write performs w.r.t. the processor when a subsequent read by theprocessor returns the value of that write or a later write.– A read perform w.r.t the processor when subsequent writes issuedby the processor cannot affect the value returned by the read.• In multiprocessors, stay same but replace “the” by “a” processor– Also, complete: perform with respect to all processors.– Still need to make sense of order in operations from differentprocesses.EECC756 - ShaabanEECC756 - Shaaban#11 lec # 11 Spring2002 4-25-2002Shared Memory Access PrimitivesShared Memory Access Primitives• A load by processor Pi is performed with respect toprocessor Pk at a point in time when the issuing of a storeto the same location by Pk cannot affect the valuereturned by the load.• A store by Pi is considered performed with respect to Pkat one time when a load from the same address by Pkreturns the value by this