Distributed Computing
Second Edition
Sunita Mahajan
Seema Shah
© Oxford University Press 2013. All rights reserved.
Chapter 8
Distributed Shared
Memory
© Oxford University Press 2013. All rights reserved.
OUTLINE
• Introduction
• Basic concepts of
DSM
• Hardware DSM
• Design issues in DSM
• Issues in
implementing DSM
systems
• Heterogeneous and
other DSM systems
© Oxford University Press 2013. All rights reserved.
Introduction
© Oxford University Press 2013. All rights reserved.
IPC Paradigms
• Message passing
• Shared memory
• Multi computer systems are easier to build but harder to
program while multiprocessor systems are complex to build
but easier to program
• Distributed Shared Memory systems (DSM) are both easy to
program and easy to build
© Oxford University Press 2013. All rights reserved.
Basic Concepts of DSM
© Oxford University Press 2013. All rights reserved.
DSM
• A DSM system provides a logical abstraction of shared
memory which is built using a set of interconnected nodes
having physically distributed memories.
© Oxford University Press 2013. All rights reserved.
DSM Architecture-1
• DSM
– Ease of programming and portability
– Scalable with very high computing power
© Oxford University Press 2013. All rights reserved.
DSM Architecture-2
• Cluster based architecture
© Oxford University Press 2013. All rights reserved.
Comparison of IPC Paradigms
© Oxford University Press 2013. All rights reserved.
Types of DSMs
• Hardware level DSM
• Software level DSM
• Hybrid level DSM
© Oxford University Press 2013. All rights reserved.
Advantages of DSM
• Simple abstraction
• Improved portability of distributed application programs
• Provides better performance in some applications
• Large memory space at no extra cost
• Better than message passing systems
© Oxford University Press 2013. All rights reserved.
Hardware DSM
© Oxford University Press 2013. All rights reserved.
Hardware Architectures
• On chip memory
• Bus based multiprocessor
• Ring based multiprocessor
• Switched multiprocessor
© Oxford University Press 2013. All rights reserved.
On Chip Memory
© Oxford University Press 2013. All rights reserved.
Bus-based Multiprocessor
• Use bus arbitration mechanism
© Oxford University Press 2013. All rights reserved.
Consistency Protocols
© Oxford University Press 2013. All rights reserved.
Cache Consistency Protocol
• Properties
– Consistency is achieved since all caches do us snooping
– Protocol is built into MMU
– The algorithm is performed in one memory cycle
© Oxford University Press 2013. All rights reserved.
Memnet DSM Architecture
• Shred memory
– Private areas
– Shared areas
© Oxford University Press 2013. All rights reserved.
Memnet: Node Memory
© Oxford University Press 2013. All rights reserved.
Comparison
• The major difference between bus based and ring based
multiprocessors is that the former are tightly coupled while
the latter are loosely coupled.
• Ring based multiprocessors are almost hardware
implementation of DSM.
© Oxford University Press 2013. All rights reserved.
Switched Multiprocessor
• Multiple clusters interconnected by a bus offer better
scalability
• Example : Dash system
© Oxford University Press 2013. All rights reserved.
Design Issues In DSM
© Oxford University Press 2013. All rights reserved.
DSM Design Issues
• Granularity of sharing
• Structure of data
• Consistency models
• Coherence protocols
© Oxford University Press 2013. All rights reserved.
Granularity
• False sharing
• Thrashing
© Oxford University Press 2013. All rights reserved.
DSM Structure
• Organization of data items in the shared memory
© Oxford University Press 2013. All rights reserved.
Consistency Models
• Refers to how recent the shared memory updates are visible
to all the other processes running on different machines
© Oxford University Press 2013. All rights reserved.
Strict Consistency
• Strongest form of consistency
© Oxford University Press 2013. All rights reserved.
Sequential Consistency
• All processors in the system observe the same ordering of
reads and writes which are issued in sequence by the
individual processors
© Oxford University Press 2013. All rights reserved.
Causal Consistency
• Weakening of sequential consistency for better concurrency
• Causally related operation is the one which has influenced the
other operation
© Oxford University Press 2013. All rights reserved.
PRAM Consistency
• Pipelined Random Access Memory consistency
• Write operations performed by a single process are seen by all
other processes in the order in which they were performed
just as if these write operations were performed by a single
process in a pipeline.
• Write operations performed by different processes may be
seen by different processes in different orders.
© Oxford University Press 2013. All rights reserved.
Processor Consistency
• Adheres to the PRAM consistency
• Constraint on memory coherence
• Order in which the memory operations are seen by two
processors need not be identical, but the order of writes
issued by each processor must be preserved
© Oxford University Press 2013. All rights reserved.
Weak Consistency
• Use a special variable called the synchronization variable
© Oxford University Press 2013. All rights reserved.
Properties of the Weak
Consistency Model
• Access to synchronization variables is sequentially consistent
• Only when all previous writes are completed everywhere,
access to synchronizations variable is allowed
• Until all previous accesses to synchronization variables are
performed, no read write data access operations will be
allowed.
© Oxford University Press 2013. All rights reserved.
Release Consistency
• Synchronization variables: acquire and release
• Use barrier mechanism
© Oxford University Press 2013. All rights reserved.
Eager Release Consistency
© Oxford University Press 2013. All rights reserved.
Lazy Release Consistency
© Oxford University Press 2013. All rights reserved.
Entry Consistency
• Use acquire and release at the start and end of each critical
section, respectively.
• Each ordinary shared variable is associated with some
synchronization variable such as a lock or barrier.
• Entry consistency (EC) is similar to LRC but more relaxed;
shared data is explicitly associated with synchronization
primitives and is made consistent when such an operation is
performed
© Oxford University Press 2013. All rights reserved.
Scope Consistency
• A scope is a limited view of memory with respect to which
memory references are performed
© Oxford University Press 2013. All rights reserved.
Comparison of Consistency
Models-1
• Most common: sequential consistency model
© Oxford University Press 2013. All rights reserved.
Comparison of Consistency
Models-2
• Based on efficiency and programmability
© Oxford University Press 2013. All rights reserved.
Coherence Protocols
• Specifies how the rules set by the memory consistency model
are to be implemented
© Oxford University Press 2013. All rights reserved.
Coherence Algorithms
• Maintain consistency among replicas
© Oxford University Press 2013. All rights reserved.
Multiple Reader/ Multiple
Writer Algorithm
• Uses twin and diff creation technique
© Oxford University Press 2013. All rights reserved.
Write Protocols for Consistency
• Write Update (WU)
• Write Invalidate (WI) protocols
© Oxford University Press 2013. All rights reserved.
Issues in Implementing
DSM Systems
© Oxford University Press 2013. All rights reserved.
Issues
• Thrashing
• Responsibility of DMS management
• Replication v/s migration
• Replacement strategy
© Oxford University Press 2013. All rights reserved.
Thrashing
• False sharing
• Techniques to reduce
thrashing:
– Application controlled
lock
– Pin the block to a node
for specific time
– Customize algorithm to
shared data usage
pattern
© Oxford University Press 2013. All rights reserved.
Responsibility for DSM
Management
• Algorithms for data location and consistency management
– Centralized manager algorithm
– Broadcast algorithm
– Fixed Distributed manager algorithm
– Dynamic distributed manager algorithm
© Oxford University Press 2013. All rights reserved.
Centralized Manager Algorithm
© Oxford University Press 2013. All rights reserved.
Broadcast Algorithm
Replicates
© Oxford University Press 2013. All rights reserved.
Fixed Distributed Manager
Algorithm
© Oxford University Press 2013. All rights reserved.
Dynamic Distributed Manager
Algorithm
© Oxford University Press 2013. All rights reserved.
Replication Versus Migration
Strategies
• Replication strategy • Non Replicated and Non
– No replication Migrating Block- NRNMB
• Non Replicated, Migrating
– Replication Block- NRMB
• Replicated, Migrating Block-
RMB
• Replicated Non Migrating
• Migration strategy
Block-RNMB
– No migration
– Migration
Replacement Strategy
© Oxford University Press 2013. All rights reserved.
Heterogeneous and Other
DSM Systems
© Oxford University Press 2013. All rights reserved.
Issues in Building Heterogeneous
DSM Systems
• Data compatibility and conversion
– DSM as a collection of source language objects
• Block size selection
– Largest page size
– Smallest page size
– Intermediate page size
© Oxford University Press 2013. All rights reserved.
Approaches to DSM Design
• Based on data caching management DSM is managed by
1. Operating system
1. MMU Hardware
1. Language runtime system
© Oxford University Press 2013. All rights reserved.