Parallel and distributed
computing
COMP3139
Agenda
• Distributed Shared Memory
• DSM W orking
• DSM Types
• DSM Advantages
• DSM Algorithms
Distributed Shared Memory
Distributed Shared
Memory (DSM)
• Distributed Shared Memory
(DSM) is a memory architecture
where physically separate
memory units are accessible to
multiple processors in a
network.
• As if they were a single,
unified memory space.
Distributed Shared Memory
• DSM allows distributed systems to share data across different
nodes without needing explicit communication through messages.
• This abstraction simplifies the development of distributed
applications.
• It hides the complexity of managing local memory and data
synchronization across multiple machines.
How DSM Works?
1. Memory Abstraction : DSM, the physically distributed memory across
multiple nodes is made to appear as a single, global shared memory to the
programs.
• Each node in the system can access this shared memory directly, like
how they would access local memory.
2. Data Access and Consistency: Each processor (or node) can read from
and write to the shared memory.
• When a node requests data from shared memory, the DSM system
determines whether the data is available locally or needs to be fetched
from another node
How DSM Works?
For consistency, DSM employs
protocols that ensure that the
same memory location reflects
the correct and up-to-date data
across all nodes.
DSM Working
3. Page- Based or Objec t-Based DSM:
• Page-Bas ed DSM: Memory is divided int o pages, and DSM systems track which node
has the most updated version of a page.
• When a node access es a page not pres ent locally, it is fetched from the node that
holds it.
• Object-Bas ed DSM: Instead of dealing with memory pages, objects or dat a structures
are shared,
• Only the nec essary obj ect or part of memory is fetched and synchronized bet wee n
nodes.
DSM Working
4. Memory Consistency Models:
DSM uses different consistency models to maintain data coherence across nodes:
• Strict Consistency: All nodes see every memory write instantaneously, but it can
be slow.
• Release Consistency: Only enforce consistency when synchronization operations
(like locks) are performed.
• Weak Consistency: Does not guarantee immediate consistency but provides
flexibility in synchronization.
Types of Distributed shared memory
1. On- Chip Memory:
• The data is present in the CPU portion of the chip.
• Memory is directly connected to address lines.
• On-Chip Memory DSM is expensive and complex.
2. Bus - Based Mult iprocessors :
• A set of parallel wires called a bus acts as a connection between CPU and memory.
• accessing of s ame memor y simultaneously by multiple CPUs is pr event ed by using
some algorithms
• Cache memory is used to reduce network traffic.
Types of DSM
3. Ring-Based Multiprocessors:
• There is no global centralized memory present
in Ring-based DSM.
• All nodes are connected via a token passing
ring.
• In ring-bases DSM a single address line is
divided into the shared area.
Advantages of DSM
• Simplified Programming Model:
• DSM allows developers to write parallel
programs using familiar shared memory models,
• without needing to deal with complex message-
passing protocols in distributed environments.
• This reduces the learning curve and the
complexity of program development.
Advantages of DSM
• Transparency:
• DSM hides the underlying details of memory
distribution and communication.
• From the programmer's perspective, the
distributed system behaves like a shared
memory system,
• Making it easier to design and implement
distributed applications.
Advantages of DSM
• Scalability:
• DSM enables systems to scale more effectively.
• As new nodes are added to the system, their memory can be
integrated into the shared memory space,
• Allowing for distributed applications to handle larger datasets
and more intensive computations.
• Process migration simplified: They all share the address space
so one process can easily be moved to a different machine.
Advantages of DSM
• Dat a Coher ence :
• Thr ough various consistency models, DSM ensur es that dat a remai ns
coherent across nodes.
• This reduces t he chances of dat a duplication err ors or out dat ed data being
accessed by any node.
• I mpr oved Res ource Ut ilization :
• Allows to shar e memory resources mor e eff ectively, which can lead t o
bett er load bal ancing and reduc ed bottlenecks in distribut ed computing
environments.
Advantages of DSM
• Flexibility in System Design:
DSM systems can be built on heterogeneous
networks, meaning nodes with different
operating systems.
• Architectures can still participate in a
distributed shared memory system, providing
flexibility for expanding systems.
Algorithm for implementing Distributed
Shared Memory
The central issues in implementing DSM are:
• How to keep track of location of remote data.
• How to overcome communication overheads and delays involved in
execution of communication protocols in system for accessing
remote data.
• How to make shared data concurrently accessible at several nodes to
improve performance.
Algorithm for implementing DSM
1. Central Server Algorithm:
• A central server maintains all shared data.
• It services read requests from other nodes by
returning the data items to them and write
requests by updating the data and returning
acknowledgement messages.
• Time-out can be used in case of failed
acknowledgement while sequence number can be
used to avoid duplicate write requests.
Central Server Algorithm
• It is simpler to implement but the central server
can become bottleneck.
• To overcome this shared data can be distributed
among several servers.
• This distribution can be by address or by using a
mapping function to locate the appropriate
server.
Migration Algorithm:
• In contrast to central server algo where every
data access request is forwarded to location of
data.
• Data is shipped to location of data access
request which allows subsequent access to be
performed locally.
Migration Algorithm:
• It allows only one node to access a shared data at a time and the
whole block containing data item migrates instead of individual item
requested.
• It is susceptible to thrashing where pages frequently migrate between
nodes while servicing only a few requests.
• This algo provides an opportunity to integrate DSM with virtual
memory provided by operating system at individual nodes.
Read Replication Algorithm:
• This extends the migration algorithm by
replicating data blocks and allowing multiple
nodes to have read access or one node to have
both read write access.
• It improves system performance by allowing
multiple nodes to access data concurrently.
Read Replication Algorithm:
• The write operation in this is expensive as all copies of a shared
block at various nodes will either must invalidated.
• Updated with the current value to maintain consistency of shared
data block.
• DSM must keep track of location of all copies of data blocks in this.
Full Replication Algorithm:
• It is an extension of read replication algorithm
which allows multiple nodes to have both read
and write access to shared data blocks.
• Since many nodes can write shared data
concurrently, the access to shared data must be
controlled to maintain it’s consistency.
Full Replication Algorithm:
• To maintain consistency, it can use a gap free sequences in
which all nodes wishing to modify shared data will send the
modification to sequencer
• which will then assign a sequence number and multicast the
modification with sequence number to all nodes that have a copy
of shared data item.
THANK YOU