Chapter 12: Distributed Shared Memory

1 Chapter 12: Distributed Shared MemoryAjay Kshemkalyani and Mukesh SinghalDistributed Computing: Principles, Algorithms, and SystemsCambridge University PressA. Kshemkalyani and M. Singhal ( Distributed Computing) Distributed Shared MemoryCUP 20081 / 48 Distributed Computing: Principles, Algorithms, and SystemsDistributed Shared Memory Abstractionscommunicate with Read/Write ops in Shared virtual spaceNo Send and Receive primitives to be used by applicationIUnder covers, Send and Receive used by DSM managerLocking is too restrictive; need concurrent accessWith replica management, problem of consistency arises!= weaker consistency models (weaker than von Neumann) reqdMemoryShared Virtual MemoryMemoryMemoryMemorymanagermanagerma nagerCPUCPUCPUM emoryMemoryprocessShared Virtual MemoryMemoryMemoryMemorymanagermanagerma nagerDistributed Shared Memory invocationresponseinvocationresponseinvo cationresponseprocessprocessA.

2 Kshemkalyani and M. Singhal ( Distributed Computing) Distributed Shared MemoryCUP 20082 / 48 Distributed Computing: Principles, Algorithms, and SystemsDistributed Shared Memory Abstractionscommunicate with Read/Write ops in Shared virtual spaceNo Send and Receive primitives to be used by applicationIUnder covers, Send and Receive used by DSM managerLocking is too restrictive; need concurrent accessWith replica management, problem of consistency arises!= weaker consistency models (weaker than von Neumann) reqdMemoryShared Virtual MemoryMemoryMemoryMemorymanagermanagerma nagerCPUCPUCPUM emoryMemoryprocessShared Virtual MemoryMemoryMemoryMemorymanagermanagerma nagerDistributed Shared Memory invocationresponseinvocationresponseinvo cationresponseprocessprocessA.

3 Kshemkalyani and M. Singhal ( Distributed Computing) Distributed Shared MemoryCUP 20082 / 48 Distributed Computing: Principles, Algorithms, and SystemsAdvantages/Disadvantages of DSMA dvantages:Shields programmer from Send/Receive primitivesSingle address space; simplifies passing-by-reference and passing complex datastructuresExploit locality-of-reference when a block is movedDSM uses simpler software interfaces, and cheaper off-the-shelf hardware. Hencecheaper than dedicated multiprocessor systemsNo Memory access bottleneck, as no single busLarge virtual Memory spaceDSM programs portable as they use common DSM programming interfaceDisadvantages:Programmers need to understand consistency models, to write correct programsDSM implementations use async message-passing, and hence cannot be moreefficient than msg-passing implementationsBy yielding control to DSM manager software, programmers cannot use their ownmsg-passing Kshemkalyani and M.

4 Singhal ( Distributed Computing) Distributed Shared MemoryCUP 20083 / 48 Distributed Computing: Principles, Algorithms, and SystemsAdvantages/Disadvantages of DSMA dvantages:Shields programmer from Send/Receive primitivesSingle address space; simplifies passing-by-reference and passing complex datastructuresExploit locality-of-reference when a block is movedDSM uses simpler software interfaces, and cheaper off-the-shelf hardware. Hencecheaper than dedicated multiprocessor systemsNo Memory access bottleneck, as no single busLarge virtual Memory spaceDSM programs portable as they use common DSM programming interfaceDisadvantages:Programmers need to understand consistency models, to write correct programsDSM implementations use async message-passing, and hence cannot be moreefficient than msg-passing implementationsBy yielding control to DSM manager software, programmers cannot use their ownmsg-passing Kshemkalyani and M.

5 Singhal ( Distributed Computing) Distributed Shared MemoryCUP 20083 / 48 Distributed Computing: Principles, Algorithms, and SystemsIssues in Implementing DSM SoftwareSemantics for concurrent access must be clearly specifiedSemantics replication? partial? full? read-only? write-only?Locations for replication (for optimization)If not full replication, determine location of nearest data for accessReduce delays, # msgs to implement the semantics of concurrent accessData is replicated or cachedRemote access by HW or SWCaching/replication controlled by HW or SWDSM controlled by Memory management SW, OS, language run-time systemA. Kshemkalyani and M. Singhal ( Distributed Computing) Distributed Shared MemoryCUP 20084 / 48 Distributed Computing: Principles, Algorithms, and SystemsIssues in Implementing DSM SoftwareSemantics for concurrent access must be clearly specifiedSemantics replication?

6 Partial? full? read-only? write-only?Locations for replication (for optimization)If not full replication, determine location of nearest data for accessReduce delays, # msgs to implement the semantics of concurrent accessData is replicated or cachedRemote access by HW or SWCaching/replication controlled by HW or SWDSM controlled by Memory management SW, OS, language run-time systemA. Kshemkalyani and M. Singhal ( Distributed Computing) Distributed Shared MemoryCUP 20084 / 48 Distributed Computing: Principles, Algorithms, and SystemsComparison of Early DSM SystemsType of DSME xamplesManagementCachingRemote accesssingle-bus multiprocessorFirefly, Sequentby MMUhardware controlby hardwareswitched multiprocessorAlewife, Dashby MMUhardware controlby hardwareNUMA systemButterfly, CM*by OSsoftware controlby hardwarePage-based DSMIvy, Mirageby OSsoftware controlby softwareShared variable DSMM idway, Muninby languagesoftware controlby softwareruntime systemShared object DSML inda, Orcaby languagesoftware controlby softwareruntime systemA.

7 Kshemkalyani and M. Singhal ( Distributed Computing) Distributed Shared MemoryCUP 20085 / 48 Distributed Computing: Principles, Algorithms, and SystemsMemory Coherencesimemory operations byPi(s1+s2+..sn)!/(s1!s2!..sn!) possible interleavingsMemory coherence model defines which interleavings are permittedTraditionally, Read returns the value written by the most recent Write Most recent Write is ambiguous with replicas and concurrent accessesDSM consistency model is acontractbetween DSM system and applicationprogrammerop1responseresponse invocationresponseresponseinvocationinvo cationinvocationprocesslocal Memory managerop3opkop2A. Kshemkalyani and M. Singhal ( Distributed Computing) Distributed Shared MemoryCUP 20086 / 48 Distributed Computing: Principles, Algorithms, and SystemsStrict Consistency/Linearizability/Atomic ConsistencyStrict consistency1A Read should return the most recent value written, per a global time operations that overlap per the global time axis, the following must operations appear to be atomic and sequentially processors see the same order of events, equivalent to the global timeordering of non-overlapping Memory managerop3opkop2 Sequential invocations and responses to each Read or Write Kshemkalyani and M.

8 Singhal ( Distributed Computing) Distributed Shared MemoryCUP 20087 / 48 Distributed Computing: Principles, Algorithms, and SystemsStrict Consistency / Linearizability: Examples2 Write(x,4)Write(y,2)Write(x,4)Write(y,2) Read(y,2)Read(y,2)Read(x,4)Read(x,0)Writ e(x,4)Write(y,2)Read(x,0)Read(y,0)(b) Sequentially consistent and linearizable(c) Not sequentially consistent (and hence not linearizable)(a)Sequentially consistent but not linearizablePPPPPP12211 Initial values are zero. (a),(c) not linearizable. (b) is linearizableA. Kshemkalyani and M. Singhal ( Distributed Computing) Distributed Shared MemoryCUP 20088 / 48 Distributed Computing: Principles, Algorithms, and SystemsLinearlzability: ImplementationSimulating global time axis is full replication, and total order broadcast support.

9 ( Shared var)int:x;(1) When the Memory Manager receives aReadorWritefrom application:(1a)totalorderbroadcasttheRe adorWriterequest to all processors;(1b)awaitown request that was broadcast;(1c)performpending response to the application as follows(1d)caseRead: return value from local replica;(1e)caseWrite: write to local replica and return ack to application.(2) When the Memory Manager receives atotalorderbroadcast(Write, x, val) from network:(2a)writevalto local replica ofx.(3) When the Memory Manager receives atotalorderbroadcast(Read, x) from network:(3a)no Kshemkalyani and M. Singhal ( Distributed Computing) Distributed Shared MemoryCUP 20089 / 48 Distributed Computing: Principles, Algorithms, and SystemsLinearizability: Implementation (2)When a Read in simulated at other processes, there is a do Reads participate in total order broadcasts?

10 Reads need to be serialized other Reads and all Write operations. Seecounter-example where Reads do not participate in total order (x,4)Read(x,0)Write(x,4)P_iP_jP_ktotal orderA. Kshemkalyani and M. Singhal ( Distributed Computing) Distributed Shared MemoryCUP 200810 / 48 Distributed Computing: Principles, Algorithms, and SystemsLinearizability: Implementation (2)When a Read in simulated at other processes, there is a do Reads participate in total order broadcasts?Reads need to be serialized other Reads and all Write operations. Seecounter-example where Reads do not participate in total order (x,4)Read(x,0)Write(x,4)P_iP_jP_ktotal orderA. Kshemkalyani and M. Singhal ( Distributed Computing) Distributed Shared MemoryCUP 200810 / 48 Distributed Computing: Principles, Algorithms, and SystemsSequential ConsistencySequential result of any execution is the same as if all operations of the processors wereexecuted insomesequential operations of each individual processor appear in this sequence in the localprogram interleaving of the operations from the different processors is possible.