2/4/200408/29/2002 CS267 Lecure 5 1CS 267: Shared Memory Parallel Machines Katherine [email protected] http://www.cs.berkeley.edu/~yelick/cs26702/04/2004 CS267 Lecure 5 2Basic Shared Memory Architecture• Processors all connected to a large shared memory• Local caches for each processor• Cost: much cheaper to cache than main memory• Relatively easy to program, but hard to scale• Now take a closer look at structure, costs, limitsP1interconnect$memoryP2$Pn$02/04/2004 CS267 Lecure 5 3Outline• Historical perspective• Bus-based machines• Pentium SMP• IBM SP node• Directory-based (CC-NUMA) machine• Origin 2000• Global address space machines• Cray t3d and (sort of) t3e02/04/200460s Mainframe Multiprocessors• Enhance memory capacity or I/O capabilities by adding memory modules or I/O devices• How do you enhance processing capacity?• Add processors• Already need an interconnect between slow memory banks and processor + I/O channels• cross-bar or multistage interconnection networkProcI/ODevicesInterconnectProcMemIOCMem Mem MemIOCPIO IOPMMMM02/04/200470s Breakthrough: Caches• Memory system scaled by adding memory modules• Both bandwidth and capacity• Memory was still a bottleneck• Enter… Caches!• Cache does two things:• Reduces average access time (latency)• Reduces bandwidth requirements to memoryPmemory (slow)interconnectI/O DeviceorProcessorA: 17processor (fast)02/04/2004Technology PerspectiveDRAMYear Size Cycle Time1980 64 Kb 250 ns1983 256 Kb 220 ns1986 1 Mb 190 ns1989 4 Mb 165 ns1992 16 Mb 145 ns1995 64 Mb 120 ns1000:1! 2:1!Capacity SpeedLogic: 2x in 3 years 2x in 3 yearsDRAM: 4x in 3 years 1.4x in 10 yearsDisk: 2x in 3 years 1.4x in 10 years0501001502002503003501986 1988 1990 1992 1994 1996Ye a rSpecIntSpecFP02/04/2004 CS267 Lecure 5 7Approaches to Building Parallel MachinesP1SwitchMain memoryPn(Interleaved)(Interleaved)First-level $P1$Interconnection network$PnMemMemP1$Interconnection network$PnMemMemShared CacheCentralized MemoryDance Hall, UMADistributed Memory (NUMA)Scale02/04/2004 CS267 Lecure 5 880s Shared Memory: Shared Cachei80286i80486Pentiumi80386i8086i4004R10000R4400R3010SU MIPS1000100001000001000000100000001000000001965 1970 1975 1980 1985 1990 1995 2000 2005YearTransistorsi80x86M68KMIP S• Alliant FX-8 (early 80s)• eight 68020s with x-bar to 512 KB interleaved cache• Encore & Sequent• first 32-bit micros (N32032)• two to a board with a shared cacheP1SwitchMain memoryPn(Interleaved)(Interleaved)First-level $02/04/2004 CS267 Lecure 5 9Shared Cache: Advantages and DisadvantagesAdvantages• Cache placement identical to single cache• only one copy of any cached block• Fine-grain sharing is possible• Interference• One processor may prefetch data for another• Can share data within a line without moving lineDisadvantages• Bandwidth limitation• Interference• One processor may flush another processors data02/04/2004Limits of Shared Cache ApproachI/O MEM MEM° ° °PROCcachePROCcache° ° °Assume:1 GHz processor w/o cache=> 4 GB/s inst BW per processor (32-bit)=> 1.2 GB/s data BW at 30% load-storeNeed 5.2 GB/s of bus bandwidth per processor!• Typical bus bandwidth is closer to 1 GB/s5.2 GB/s140 MB/s02/04/2004 CS267 Lecure 5 11Approaches to Building Parallel MachinesP1SwitchMain memoryPn(Interleaved)(Interleaved)First-level $P1$Interconnection network$PnMemMemP1$Interconnection network$PnMemMemShared CacheCentralized MemoryDance Hall, UMADistributed Memory (NUMA)Scale02/04/2004 CS267 Lecure 5 12Intuitive Memory Model• Reading an address should return the last value written to that address• Easy in uniprocessors• except for I/O• Cache coherence problem in MPs is more pervasive and more performance critical• More formally, this is called sequential consistency:“A multiprocessor is sequentially consistent if the result of any execution is the same as if the operations of all the processors were executed in some sequential order, and the operations of each individual processor appear in this sequence in the order specified by its program.” [Lamport, 1979]02/04/2004 CS267 Lecure 5 13Sequential Consistency Intuition• Sequential consistency says the machine behaves as ifit does the followingmemoryP0 P1 P2 P302/04/2004 CS267 Lecure 5 14Memory Consistency SemanticsWhat does this imply about program behavior?• No process ever sees “garbage” values, I.e., ½ of 2 values• Processors always see values written by some some processor• The value seen is constrained by program order on all processors• Time always moves forward• Example:• P1 writes data=1, then writes flag=1• P2 reads flag, then reads datainitially: flag=0data=0data = 1flag = 1if flag=1…= dataIf P2 sees the new value of y, it must see the new value of xP1P2110010Then P2 may read dataIf P2 reads flag02/04/2004 CS267 Lecure 5 15If Caches are Not Coherent• p1 and p2 both have cached copies of data (as 0)• p1 writes data=1 • May “write through” to memory• p2 reads data, but gets the “stale” cached copy• This may happen even if it read an updated value of another variable, flag, that came from memorydata 0data 0data = 0p1 p2data 102/04/2004 CS267 Lecure 5 16Snoopy Cache-Coherence Protocols• Memory bus is a broadcast medium• Caches contain information on which addresses they store• Cache Controller “snoops” all transactions on the bus• A transaction is a relevant transaction if it involves a cache block currently contained in this cache• take action to ensure coherence• invalidate, update, or supply value• depends on state of the block and the protocolStateAddressDataP0$$PnMemMemmemory busmemory op from Pnbus snoop02/04/2004 CS267 Lecure 5 17Basic Choices in Cache Coherence•Cache may keep information such as:• Valid/invalid• Dirty (inconsistent with memory)• Shared (in another caches)•When a processor executes a write operation to shared data, basic design choices are:• With respect to memory:• Write through: do the write in memory as well as cache• Write back: wait and do the write later, when the item is flushed• With respect to other cached copies• Update: give all other processors the new value• Invalidate: all other processors remove from cache02/04/2004 CS267 Lecure 5 18Example: Write-thru Invalidate• Update and write-thru both use more memory bandwidth if there are writes to the same address• Update to the other caches•
View Full Document
Unlocking...