CSE 803 Introduction to

Distributed Computing

1
 Distributed Shared Memory

 ➀ DSM
➁ Case study
➂ Design issues
➃ Implementation issues
2
 DISTRIBUTED SHARED MEMORY (DSM)

DSM: shared memory + multicomputer

Shared global address space

0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16

0 2 5 1 3 6 4 7 11 13 15 16

9 8 10 12 14

CPU 1 CPU 2 CPU 3 CPU 4

D ISTRIBUTED S HARED M EMORY

(DSM)
4
 SHARED ADDRESS SPACE

DSM consists of two components:

➀ Shared address space
➁ Replication and consistency of memory
objects
Shared address space:
Node 1 Node 2

0x1000 0x1000

0x2000 0x2000

Network

➜ Shared addresses are valid in all processes

4
 SHARED ADDRESS SPACE

Transparent remote access:

Node 1 Node 2

0x1000 0x1000

0x2000 0x2000

Network

Properties:
➜ Remote access is expensive compared to local memory
access
➜ Individual operations can have very low overhead
➜ Threads can distinguish between local and remote
access
5
 SHARED ADDRESS SPACE

Why DSM?:
➜ Shared memory model: easiest to program to
➜ Physical shared memory not possible on multicomputer
➜ DSM emulates shared memory

Benefits of DSM:
➜ Ease of programming (shared memory model)
➜ Eases porting of existing code
➜ Pointer handling
•Shared pointers refer to shared memory
•Share complex data (lists, etc.)
➜ No marshalling

6
 DSM IMPLEMENTATIONS

➜Most often implemented in user space (e.g., TreadMarks,

CVM)
➜User space: what’s needed from the kernel?
•User-level fault handler [e.g., Unix signals]
•User-level VM page mapping and protection [e.g., mmap()
and mprotect()]


•Message passing layer [e.g., socket API]

7
 DSM I MPLEMENTATIONS
Hardware:
➜ Multiprocessor
➜ Example: MIT Alewife, DASH

OS with hardware support:

➜ SCI network cards (SCI = Scalable Coherent Interconnect)
➜ SCI maps extended physical address space to remote
nodes
➜ OS maps shared virtual address space to SCI range

OS and Virtual Memory:

➜ Virtual memory (page faults, paging)
➜ Local address space vs Large address space

8
 DSM I MPLEMENTATIONS

Middleware:
➜ Library:
•Library routines to create/access shared memory
•Example: MPI-2, CRL
➜ Language
•Shared memory encapsulated in language
constructs
•Extend language with annotations
•Example: Orca, Linda, JavaSpaces, JavaParty,
Jackal

9
 DSM I MPLEMENTATIONS

➜
Typical
Most often implemented in user space (e.g., TreadMarks,
CVM)
Implementat
➜ User space: what’s needed from the kernel?
ion:
•User-level fault handler [e.g., Unix signals]
•User-level VM page mapping and protection [e.g., mmap() and
mprotect()]
•Message passing layer [e.g., socket API]

10
 DSM IMPLEMENTATIONS

Example: two processes

sharing memory pages:
0x100
Node 1

0x100
Node 2

0 0

Network

11
 DSM IMPLEMENTATIONS

Occurrence of
a read fault:
0x100
Node 1

0x100
Node 2

0 0

Fault!

Network

6
 DSM IMPLEMENTATIONS

Page migration
and replication:
0x100
Node 1

0x100
Node 2

0 0

Network

7
 DSM IMPLEMENTATIONS

Recovery
from read
0x100
Node 1

0x100
Node 2

fault:
0 0

Resum
e

Network

8
 DSM MODELS

Shared page (coarse-grained):

➜ Traditional model
➜ Ideal page size?
X False sharing
➜ Examples: Ivy, TreadMarks
Shared region (fine-grained):
➜ More fine grained than sharing pages
V  Prevent false sharing
X Not regular memory access (transparency)
➜ Examples: CRL (C Region Library), MPI-2 one-sided communication,
Shasta
15
 DSM MODELS

➜ Release and Entry based consistency

➜ Annotations
V Fine grained
X More complex for programmer
➜ Examples: Munin, Midway
Shared structure:
➜ Encapsulate shared data
➜ Access only through predefined procedures (e.g., methods)
 V Tightly integrated synchronisation

V Encapsulate (hide) consistency model

X Lose familiar shared memory model
➜ Examples: Orca (shared object), Linda (tuple space)
16
 DSM MODELS

Tuple
Space A Write A B Write B T Read T

C
:
Look for
Insert a Insert a tuple that
copy of A copy of B matches T

B A Return C
A (and optionally
remove it)
B
Tuple instance B C

A JavaSpace

11
 LINDA EXAMPLE

main() {
...
eval("function", f()) ;
eval("function", f()) ;
...
for (i=0; i<100; i++)
out("data", i) ;
...
} f(){
in("data", ?x) ; y =
g(x) ;
out("function", x, y) ;
}

What’s good about this?

16
 APPLICATIONS OF DSM

➜ Scientific parallel computing

• Bioinformatics (gene sequence analysis)
• Simulations (climate modeling, economic modeling)
• Data processing (physics, astronomy)
➜ Graphics (image processing, rendering)
➜ Data server (distributed FS, Web server)

➜ Data storage

19
 DSM ENVIRONMENTS

➜ Multiprocessor
• NUMA
➜ Multicomputer
• Supercomputer
• Cluster
• Network of Workstations

• Wide-area

20
 REQUIREMENTS OF DSM

Transparency:
➜ Location, migration, replication, concurrency
Reliability:
➜ Computations depend on availability of data
Performance:
➜ Important in high-performance computing
➜ Important for transparency
Scalability:

➜ Important in wide-area
➜ Important for large computations

21
 REQUIREMENTS OF DSM

➜ Access to DSM should be consistent

➜ According to a consistency model
Programmability:
➜ Easy to program
➜ Communication transparency

22
 CASE STUDY

TreadMarks:
➜ 1992 Rice University
➜ Page based DSM library
➜ C, C++, Java, Fortran
➜ Lazy release consistency model
➜ Heterogeneous environment

23
 DESIGN ISSUES

Granularity
➜ Page based, Page size: minimum system page size
Replication
➜ Lazy release consistency
Scalability
➜ Meant for cluster or NOW (Network of Workstations)
Synchronisation primitives
➜ Locks (acquire and release), Barrier
Heterogeneity


➜ Limited (doesn’t address endianness or mismatched word sizes)

Fault Tolerance
➜ Research
No Security 24
 USING TREADMARKS
Compiling:
➜ Compile
➜ Link with TreadMarks libraries
Starting a TreadMarks Application:
App -- -h host1 -h host2 -h host3 -h host4

Anatomy of a TreadMarks Program:

➜Starting remote processes
Tmk_startup(argc,argv);
 ➜Allocating and sharing memory
shared = (struct shared*) Tmk_Malloc(sizeof(shared));
Tmk_distribute(&shared, sizeof(shared));

25
 USING TREADMARKS

➜Barriers
Tmk_barrier(0);

➜Acquire/Release
Tmk_lock_acquire(0); shared->sum+= mySum;
Tmk_lock_release(0);

U SING 20
TREAD M ARKS
 T READ M ARKS I MPLEMENTATION
Consistency Protocol:
➜ Multiple writer
➜ Twins
➜ Reduce false sharing
R RW twin
x=1 x=1
P1
x(0) P x(0) x(0)
1

1. Write causes page 2. After page

fault fault

RW twin RW
x=1
P1 P1 diff
x(1) x(0) x(1)
x
0 1

3. Write is 4. At release or
executed barrier

21
 USING TREADMARKS

• ➜ Modified pages invalidated at acquire

• ➜ Page is updated at access time
• ➜ Updates are transferred as diffs
• Lazy Diffs:
• ➜ Normally make diffs at release time
• ➜ Lazy: make diffs only when they are requested
• Communication:
• ➜ UDP/IP or AAL3/4 (ATM)
• ➜ Light-weight, user-level protocols to ensure message delivery
• ➜ Use SIGIO for message receive notification

22
 TREADMARKS
IMPLEMENTATION

➜ Know who has diffs because of invalidations

➜ Each page has a statically assigned manager
Modification Detection:
➜ Page Fault
➜ If page is read-only then do consistency protocol
➜ If not in local memory, get from manager
Memory Management:
➜ Garbage collection of diffs

23
 TREADMARKS
IMPLEMENTATION

➜ Processes set up communication channels between

themselves
➜ Register SIGIO handler for communication
➜ Allocate large block of memory
•Same (virtual) address on each machine
•Mark as non-accessible
•Assign manager process for each page, lock, barrier (round
robin)
➜ Register SEGV handler

24
 READING LIST

Distributed Shared Memory: A Survey of Issues and Algorithms An

overview of DSM and key issues as well as older DSM
implementations.

TreadMarks: Shared Memory Computing on Networks of

Workstations An overview of TreadMarks, design decisions and
implementation.

25