TECHNIQUES FOR REDUCING CONSISTENCY-RELATED COMMUNICATION IN DISTRIBUTED SHARED-MEMORY SYSTEMSINTRODUCTIONWhy bother with DSM?Conventional parallel architectureToday’s architectureLimitations of cluster approachDistributed shared memoryDistributed shared memoryCharacterizing a DSM (I)False SharingCharacterizing a DSM (II)Characterizing a DSM (III)MUNINKey featuresSW RELEASE CONSISTENCY (I)SW RELEASE CONSISTENCY (II)SW RELEASE CONSISTENCY (III)SW RELEASE CONSISTENCY (IV)Munin Implementation (I)Munin Implementation (II)FOUR CONSISTENCY PROTOCOLSSlide 22ImplementationWRITE-SHARED PROTOCOL (I)ExampleWRITE-SHARED PROTOCOL (II)UPDATE TIME-OUT MECHANISMSlide 28CONCLUSIONS (I)CONCLUSIONS (II)FURTHER DEVELOPMENTSTECHNIQUES FOR REDUCING CONSISTENCY-RELATED COMMUNICATION IN DISTRIBUTED SHARED-MEMORY SYSTEMSJ. B. CarterUniversity of UtahJ. K. Bennett and W. ZwaenepoelRice UniversityINTRODUCTION•Distributed shared memory is a software abstraction allowing a set of workstations connected by a LAN to share a single paged virtual address space• Key issue in building a software DSM is minimizing the amount of data communication among the workstation memoriesWhy bother with DSM?•Key idea is to build fast parallel computers that–are cheaper than conventional architectures–are convenient to use•Conventional parallel computer architecture was the shared memory multiprocessorCPUShared memoryConventional parallel architectureCACHE CACHE CACHE CACHECPU CPU CPUToday’s architecture•Clusters of workstations are much more cost effective–No need to develop complex bus and cache structures–Can use off-the-shelf networking hardware•Gigabit Ethernet •Myrinet (1.5 Gb/s)–Can quickly integrate newest microprocessorsLimitations of cluster approach•Communication within a cluster of workstation is through message passing–Much harder to program than concurrent access to a shared memory•Many big programs were written for shared memory architectures–Converting them to a message passing architecture is a nightmareDistributed shared memory DSM = one shared global address spacemain memoriesDistributed shared memory•DSM makes a cluster of workstations look like a shared memory parallel computer–Easier to write new programs–Easier to port existing programs•Key problem is that DSM only provides the illusion of having a shared memory architecture–Data must still move back and forth among the workstationsCharacterizing a DSM (I)•Four important issues:1. Size of transfer units (level of granularity)•Big units are more efficient– Virtual memory pages•Can have false sharing whenever page contains different variables that are accessed at the same time by different processorsFalse Sharingaccesses xaccesses yx ypage containing x and y will move back and forthbetween main memories of workstationsCharacterizing a DSM (II)2. Consistency model•Strict consistency is not possible•Various authors have proposed weak consistency models–Cheaper to implement–Harder to use in a correct fashionCharacterizing a DSM (III)3. Portability of programs•Some DSMs allow programs written for a multiprocessor architecture to run on a cluster of workstations without any modifications (dusty decks)•More efficient DSMs require more changes4. Portability of DSM•Some DSMs require specific OS featuresMUNIN•Developed at Rice University•Based on software objects (variables)•Uses the processor virtual memory to detect access to the shared objects•Includes several techniques for reducing consistency-related communication•Only runs on top of V kernelKey features•Software release consistency: only requires the memory to be consistent at specific synchronization points,•Multiple consistency protocols: allow the user to select the best consistency protocols for each data item,•Write-shared protocols: reduce false sharing,•An update-with-timeout mechanismSW RELEASE CONSISTENCY (I)•Well-written parallel programs use locks to achieve mutual exclusion when they access shared variables–P(&mutex) and V(&mutex)–lock(&csect) and unlock(&csect) –request ( ) and release( )•Unprotected accesses can produce unpredictable resultsSW RELEASE CONSISTENCY (II)•SW release consistency will only guarantee correctness of operations within a request/release pair•No need to propagate new values of shared variables until the release•Must guarantee that workstation has received the most recent values of all shared variables when it completes a requestSW RELEASE CONSISTENCY (III)shared int x;request( );x = 1;release ( );// propagate x=1shared int x;request( );// wait for new value of xx++;release ( );// propagate x=2SW RELEASE CONSISTENCY (IV)•Munin uses eager release: new values of shared variables are propagated at release time–Lazy release delays propagation until a request is issued (Threadmarks)•A workstation issuing a request gets the current values of all shared variables–Shared variables are not associated to a particular critical section (as in Midway)Munin Implementation (I)•Three kinds of variables: 1. Ordinary variables: can only be accessed by the process that created them2. Shared data variables: should always be accessed from within critical regions3. Synchronization variables:•locks, barriers or condition variables•must be accessed through special library procedures .Munin Implementation (II)•When a processor modifies shared data inside a critical region, all update messages are buffered and delayed until the processor leaves the critical region•Processes accessing shared data variables outside critical regions do it at their own risks–Same as with shared memory model–Risk is higherFOUR CONSISTENCY PROTOCOLS1. Conventional shared variables: –Replicated on demand –Single writer/multiple readers policy uses an invalidation-based protocol 2. Read-only variables: –Replicated on demand–Any attempt to modify them will result in a runtime errorFOUR CONSISTENCY PROTOCOLS3. Migratory variables:–Migrated among the processes accessing them–Every process accessing them will always get full read and write access4. Write-shared variables:–Can be updated concurrently because different portions of the page are accessedImplementation•Programmer uses annotations to specify any of the last three consistency protocols–Read-only variables–Migratory variables–Write-shared variables•Incorrect annotations may result in inefficient performance or