Distributed Shared Memory: Pham Quoc Cuong & Phan Dinh Khoi Use Some Slides of James Deak - Njit

dce
2008
Distributed Shared Memory

Pham Quoc Cuong & Phan Dinh Khoi
Use some slides of James Deak -
NJIT
Computer Engineering 2008 Outline
• Introduction
• Design and Implementation
• Sequential consistency and Ivy – case
study
• Release consistency and Munin – case
study
• Other consistency models
Distributed Shared Memory ©2008, Pham Quoc Cuong – Phan Dinh Khoi 2
• Introduction
study
study
Computer Engineering 2008 Distributed Shared Memory
• Distributed Shared Memory (DSM) allows
programs running on separate computers to
share data without the programmer having to
deal with sending messages
• Instead underlying technology will send the
messages to keep the DSM consistent (or
relatively consistent) between computers
• DSM allows programs that used to operate on
the same computer to be easily adapted to
operate on separate computers
Computer Engineering 2008 Introduction
• Programs access what appears to them to be
normal memory
• Hence, programs that use DSM are usually
shorter and easier to understand than
programs that use message passing
• However, DSM is not suitable for all situations.
Client-server systems are generally less suited
for DSM, but a server may be used to assist in
providing DSM functionality for data shared
between clients
Computer Engineering 2008 The distributed shared memory abstraction
Distributed Shared Memory
(exists only virtually)
CPU 1 CPU 1 CPU 1

Memory Memory Memory
CPU n CPU n CPU n
Memory- Memory- Memory-

Mapping Mapping Mapping
Manager Manager Manager
Communication Network
Computer Engineering 2008 DSM History
• Memory mapped files started in the
MULTICS operating system in the 1960s
• One of the first DSM implementations was
Apollo. One of the first system to use
Apollo was Integrated shared Virtual
memory at Yale (IVY)
• DSM developed in parallel with shared-
memory multiprocessors
Computer Engineering 2008 DSM vs Message passing
DSM Message passing
Variables are shared directly Variables have to be marshalled

yourself
Processes can cause error to Processes are protected from

one another by altering data one another by having private
address spaces
Processes may execute with Processes must execute at the
non-overlapping lifetimes same time
Invisibility of communication’s Cost of communication is

cost obvious
• Introduction
study
study
Computer Engineering 2008 DSM implementations
• Hardware: Mainly used by shared-memory
multiprocessors. The hardware resolves LOAD
and STORE commands by communicating with
remote memory as well as local memory
• Paged virtual memory: Pages of virtual

memory get the same set of addresses for
each program in the DSM system. This only
works for computers with common data and
paging formats. This implementation does not
put extra structure requirements on the program
since it is just a series of bytes.
Computer Engineering 2008 DSM Implementations (continued)
• Middleware: DSM is provided by some
languages and middleware without
hardware or paging support. For this
implementation, the programming
language, underlying system libraries, or
middleware send the messages to keep
the data synchronized between programs
so that the programmer does not have to.
Computer Engineering 2008 Efficiency
• DSM systems can perform almost as well
as equivalent message-passing programs
for systems that run on about 10 or less
computers.
• There are many factors that affect the
efficiency of DSM, including the
implementation, design approach, and
memory consistency model chosen.
Computer Engineering 2008 Design approaches
• Byte-oriented: This is implemented as a
contiguous series of bytes. The language and
programs determine the data structures
• Object-oriented: Language-level objects are
used in this implementation. The memory is only
accessed through class routines and therefore,
OO semantics can be used when implementing
this system
• Immutable data: Data is represented as a group
of many tuples. Data can only be accessed
through read, take, and write routines
Computer Engineering 2008 Memory consistency
• To use DSM, one must also implement a
distributed synchronization service. This
includes the use of locks, semaphores, and
message passing
• Most implementations, data is read from local
copies of the data but updates to data must be
propagated to other copies of the data
• Memory consistency models determine when
data updates are propagated and what level of
inconsistency is acceptable
Computer Engineering 2008 Two processes accessing shared variables
Process 1 Process 2
br := b; a := a + 1;
ar := a; b := b + 1;
if(ar ≥ br) then
print ("OK");
Computer Engineering 2008 Memory consistency models
• Linearizability or atomic consistency is the
strongest model. It ensures that reads and
writes are made in the proper order. This results
in a lot of underlying messaged being passed.
 Variables can only be changed by a write operation
 The order of operations is consistent with the real
times at which the operations occurred in the actual
execution
• Sequential consistency is strong, but not as
strict. Reads and writes are done in the proper
order in the context of individual programs.
 The order of operations is consistent with the program
order in which each individual client executed them
Computer Engineering 2008 Memory consistency models (continued)
• Coherence has significantly weaker consistency.
It ensures writes to individual memory locations
are done in the proper order, but writes to
separate locations can be done in improper
order
• Weak consistency requires the programmer to
use locks to ensure reads and writes are done in
the proper order for data that needs it
Computer Engineering 2008 Interleaving under sequential consistency
Process 1
Time Process 2
read
br := b;
a := a + 1;
ar := a;
b := b + 1;
if(ar ≥ br) then
print ("OK"); write
Computer Engineering 2008 Update options
• Write-update: Each update is multicast to
all programs. Reads are performed on
local copies of the data
• Write-invalidate: A message is multicast to
each program invalidating their copy of the
data before the data is updated. Other
programs can request the updated data
Computer Engineering 2008 DSM using write-update
if(a=7) then
a := 7; b := b+1;
b := 7; ...
if(b=8) then
print("after"); updates
time
time
if(b=a) then
print("before");
time
Computer Engineering 2008 Granularity
• Granularity is the amount of data sent with each
update
• If granularity is too small and a large amount of
contiguous data is updated, the overhead of
sending many small messages leads to less
efficiency
• If granularity is too large, a whole page (or more)
would be sent for an update to a single byte,
thus reducing efficiency
Computer Engineering 2008 Data items laid out over pages
A B
page n page n + 1
Computer Engineering 2008 Trashing
• Thrashing occurs when network resources
are exhausted, and more time is spent
invalidating data and sending updates
than is used doing actual work
• Based on system specifics, one should
choose write-update or write-invalidate to
avoid thrashing
• Introduction
study
study
Computer Engineering 2008 Sequential consistency and Ivy case study
• This model is page-based
• A single segment is shared between programs
• The computers are equipped with a paged
memory management unit
• The DSM restricts data access permissions
temporarily in order to maintain sequential
consistency
• Permissions can be none, read-only, or read-
write
Computer Engineering 2008 System model for page-based DSM
Process accessing
paged DSM segment
Kernel redirects
page faults to
Kernel
user-level
handler
Pages transferred over network
Computer Engineering 2008 Write-update
• If a program tries to do more than it has
permission for, a page fault occurs and the
program is block until the page fault is resolved
• If writes can be buffered, write-updated is used
Computer Engineering 2008 Write-invalidate
• If writes cannot be buffered, write-invalidate is
used
• The invalidation message acts as requesting a
lock on the data
• When one program is updating the data it has
read-write permissions and everyone else has
no permissions on that page
• At all other times, all have read-only access to
the page
Computer Engineering 2008 State transitions under write-invalidation
Single writer Multiple reader
R
P W writes; P R1, PR2,..PRn read;
none read none write
W
(invalidation)
W R
(invalidation)
Note: R = read fault occurs; W = write fault occurs.
Computer Engineering 2008 Terminology
• copyset (p): the set of process that have a
copy of page p
• owner(p): a process with the most up-to-
date version of a page p
Computer Engineering 2008 Write page-fault handling
• Process PW attempts to write a page p to which it
does not have permission
 The page p is transferred to Pw if it has not an up-to-
date read-only copy
 An invalidate message is sent to all member of
copyset(p)
 copyset(p) = {Pw}
 owner(p) = Pw
Computer Engineering 2008 Read page-fault handling
• If a process PR attempts to read a page p for
which it does not have permissions
 The page is copied from owner(p) to PR
 If current owner is a single writer => its access
permission for p is set to read-only
 Copyset(p) = copyset(p) {PR}
Computer Engineering 2008 Problems with invalidation protocols
• How to locate owner(p) for a given page p
• Where to store copyset(p)
Computer Engineering 2008 Central manager and associated messages
Faulting process Current owner
3. Page
1. page no., access (R/W) 2. requestor, page no., access
Page Owner
no.
Manager
......... ........
Computer Engineering 2008 Alternative manager strategy
• A central manager may become a performance
bottleneck
• There are a three alternatives:
 Fixed distributed page management where on
program will manage a set of pages for its lifetime
(even if it does not own them)
 Multicast-based management where the owner of a
page manages it, read and write requests are
multicast, only the owner answers
 Dynamic distributed management where each
program keeps a set of the probable owner(s) of each
page
Computer Engineering 2008 Dynamic distributed manager
• Initially each process is supplied with accurate
page locations
transfers invalidation
p p
probOwner(p) probOwner(p)
Pi Pj Pi Pj
request read request
Pi Pj Pi Pj
probOwner(p) probOwner(p)
granted read
Forward request
Computer Engineering 2008 Updating probOwner pointers
B C D E
Owner
Owner
(a) probOwner pointers just before process A takes a page fault for a page owned by E
B C D E
Owner
Owner A
(b) Write fault: probOwner pointers after A's write request is forwarded
B C D E
Owner
Owner
(c) Read fault: probOwner pointers after A's read request is forwarded
• Introduction
study
study
Computer Engineering 2008 Release consistency and Munin case study
• Be weaker than sequential consistency,

but cheaper to implement
• Reduce overhead
• Used semaphores, locks, and barriers to
achieve enough consistency
Computer Engineering 2008 Memory accesses
• Types of memory accesses:
 Competing accesses
• They may occur concurrently – there is no
enforced ordering between them
• At least one is a write
 Non-competing or ordinary accesses
• All read-only access, or enforced ordering
Computer Engineering 2008 Competing Memory Access
• Competing memory accesses are divided
into two categories:
 Synchronization accesses are concurrent and
contribute to synchronization
 Non-synchronization accesses are concurrent
but do not contribute to synchronization
Computer Engineering 2008 Release consistency requirements
• To achieve release consistency, the
system must:
 Preserve synchronization with locks
 Gain performance by allowing asynchronous
memory operations
 Limit the overlap between memory operations
Computer Engineering 2008 Release consistency requirements
• One must acquire appropriate permissions
before performing memory operations
• All memory operations must be performed
before releasing memory
• Acquiring permissions and releasing
memory
Computer Engineering 2008 Munin
• Munin had programmers use acquireLock,
releaseLock, and waitAtBarrier
• Munin sends updates/invalidations when locks
are released
 An alternative has the update/invalidation sent when
the lock is next acquired
Computer Engineering 2008 Processes executing on a release-consistent DSM
Process 1:
acquireLock(); // enter critical section
a := a + 1;
b := b + 1;
releaseLock(); // leave critical section
Process 2:
acquireLock(); // enter critical section
print ("The values of a and b are: ", a, b);
releaseLock(); // leave critical section
Computer Engineering 2008 Munin: Sharing annotations
• The following are options with Munin on the data
item level:
 Using write-update or write-invalidate
 Whether several copies of data may exist
 Whether to send updates/invalidate immediately
 Whether a data has a fixed owner, and whether that
data can be modified by several at once
 Whether the data can be modified at all
 Whether the data is shared by a fixed set of programs
Computer Engineering 2008 Munin: Standard annotations
• Read-only: Initialized, but not allow to be updated
• Migratory: Programs access a particular data item in turn
• Write-shared: Programs access the same data item, but
write to different parts of the data item
• Producer-consumer:
 One program write to the data item
 A fixed set of programs read it
• Reduction: The data is always locked, read, updated,
and unlocked
• Result: Several programs write to different parts of one
data item. One program reads it
• Conventional: Data is managed using write-invalidate
• Introduction
study
study
Computer Engineering 2008 Other consistency models
• Casual consistency – The happened –
before relationship can be applied to read
and write operations
• Pipelining RAM – Programs apply write
operations through pipelining
• Processor consistency – Pipelining RAM
plus memory coherent
Computer Engineering 2008 Other consistency models
• Entry consistency – Every shared data item is
paired with a synchronization object
• Scope consistency – Locks are applied
automatically to data objects instead of relying
on programmers to apply locks
• Weak consistency – Guarantees that previous
read and write operations complete before
acquire or release operations
Computer Engineering 2008 Summary
study
study

Distributed Shared Memory: Pham Quoc Cuong & Phan Dinh Khoi Use Some Slides of James Deak - Njit

Uploaded by

Copyright:

Available Formats

Distributed Shared Memory: Pham Quoc Cuong & Phan Dinh Khoi Use Some Slides of James Deak - Njit

Uploaded by

Document Information

Original Title

Copyright

Available Formats

Share this document

Share or Embed Document

Sharing Options

Did you find this document useful?

Is this content inappropriate?

Copyright:

Available Formats

Distributed Shared Memory: Pham Quoc Cuong & Phan Dinh Khoi Use Some Slides of James Deak - Njit

Uploaded by

Copyright:

Available Formats

dce

Distributed Shared Memory

CPU 1 CPU 1 CPU 1

CPU n CPU n CPU n

Memory- Memory- Memory-

Variables are shared directly Variables have to be marshalled

Processes can cause error to Processes are protected from

Invisibility of communication’s Cost of communication is

• Paged virtual memory: Pages of virtual

Pages transferred over network

Single writer Multiple reader

Note: R = read fault occurs; W = write fault occurs.

Faulting process Current owner

1. page no., access (R/W) 2. requestor, page no., access

request read request

• Be weaker than sequential consistency,

You might also like