Introduction to Distributed Shared Memory Systems

Introduction to Software
Distributed Shared Memory
Systems
Chang-Yi Lin
2004 / 02 / 26
Outlines
What is a software DSM system?
 Message-passing vs. Shared-memory
 How does it work?
 Memory Consistency Models
 Cache Coherence
 Implementation Levels
 Granularity

What is a software DSM system?
A distributed-memory system (often called
a multicomputer) consist of multiple
independent processing nodes with local
memory modules, connected by a general
interconnection network.
 Global shared memory.

What is a software DSM system?
A DSM system logically implements the
shared-memory model on a physically
distributed-memory system.
 The DSM system hides the remote
communication mechanism from the
application writer, preserving the
programming ease and portability typical
of shared-memory systems.

Message-passing vs. Shared-memory
Two different programming type.
 Shared-memory programming is easier.

Message-passing vs. Shared-memory

Message-passing

Point-to-point communication
Message-passing vs. Shared-memory

Message-passing


buffers and data types
blocking and nonblocking
Message-passing vs. Shared-memory
Message-passing vs. Shared-memory

Pthread
Thread 1
Thread 2
Thread 3
Lock
A = A++;
unlock
Lock
A = A++;
unlock
Lock
A = A++;
unlock
How does it work?
Shared-memory applications
DSM system
Memory
Interconnection network
How does it work?
App
App
App
App
DSM
DSM
DSM
DSM
Mem
Mem
Mem
Mem
Interconnection network
How does it work?
Memory Consistency Models

What is Memory consistency?
在單機上 P1: w(x)1 R(x)1
---------------------------------- time
P1: w(x)1
P2:
R(x)?
---------------------------------------- time
在兩台機器上
Memory Consistency Models
A consistency model is essentially a
contract between the software and the
memory.
 If the software agrees to obey certain
rules, the memory promises to work
correctly.
 If the software violates these rules,
correctness of memory operation is no
longer guaranteed.

Memory Consistency Models
Strict consistency
 Sequential consistency (SC)
 Release consistency (RC)
 Scope consistency (ScC)

Memory Consistency Models

Strict consistency


Definition: any read to memory location x
returns the value stored by the most recent
write operation to x.
Impossible to DSM
P1: w(x)1
P2:
R(x)1
---------------------------------------- time
Memory Consistency Models

Sequential consistency (SC)


Definition: the result of any execution is the
same as if the operations of all processors
were executed in some sequential order, and
the operations of each individual processor
appear in this sequence in the order specified
by its program.
Any valid interleaving is acceptable behavior,
but all processes must see the same sequence
of memory reference.
Memory Consistency Models

Sequential consistency (SC)
P1
P2
P3
(A) a=1;
(B) Print(b,c);
(C) b=1;
(D) Print(a,c);
(E) c=1;
(F) Print(a,b);
(A)
(B)
(C)
(D)
(E)
(F)
(A)
(C)
(D)
(B)
(E)
(F)
(C)
(E)
(F)
(D)
(A)
(B)
(A)
(C)
(E)
(B)
(D)
(F)
Memory Consistency Models

Release Consistency (RC)

Two types of access



Ordinary access: read and write
Synchronization access: acquire lock, release lock
and barrier
Rules:


Before an ordinary access to a shared variable is
performed, all previous acquires done by the process
must have completed successfully.
Before a release is allowed to be performed, all
previous reads and writes done by the process must
have completed.
Memory Consistency Models

Release Consistency (RC)
Rule1:
…Acq(L1)…Rel(L1) … Acq(L5) …Acq(L3)…R(x)
Rule2:
Acq(L2) w(x) R(y) R(z) Rel(L2)
Example:
P1: Acq(L) w(x)1 w(x)2 Rel(L)
P2:
P3:
Acq(L) R(x)2 Rel(L)
R(x)?
Memory Consistency Models

Scope consistency (ScC)
Memory Consistency Models

Relaxing consistency permits temporary
inconsistencies (delayed updates)


Lazy release consistency (LRC) (TreadMarks,
CVM)
Scope consistency (ScC) (JIAJIA, JUMP)
Cache Coherence

Write invalidate


Suffer from false sharing
Write update


Too expansive when many replicas
Work best in application with tight sharing
Implementation Levels

Modifying OS kernel


Language level


Linda, Orca
User-level runtime library


IVY (SC): modifying the memory management unit
(MMU) of OS to map between the shared virtual memory
address space and the local memory.
Trademarks, CVM, JIAJIA, JUMP, Brazos
Combination of multiple implementation levels,
even hardware support

Munin, Midway, NCP2
Granularity

The choice of the block size depends on

the cost of communcation


1 byte message v.s. 1024 byte message
Locality of reference in the application
Most DSM systems use a page-based
granularity with 1K byte to 8K byte.
 Larger page size, better locality of
reference

系統
開發者
實作層次
顆粒度
一致性模型
一致性協定
IVY
Yale
函式庫＋作業系統
頁(1KB)
SC
WI
Munin
Rice
函式庫＋作業系統
可變
Eager RC
WU/WI
TreadMarks
Rice
函式庫
頁(4KB)
LRC
MW，WI
CVM
Maryland
函式庫
頁
LRC-MW，LRC-SW，
SC
WU
Midway
CMU
函式庫＋編譯器
可變
EC，PC，RC
WU
NCP2
UFRJ, Brail
函式庫＋硬體支援
頁(4KB)
EC，RC
WU/WI
Quarks
Utah
函式庫
region、頁
RC，SC
WU/WI，MW
softFLASH
Standford
作業系統
頁(16KB)
RC，DIRC
FLASH-like
Cashmere-2L
Rochester
函式庫
頁(8KB)
HLRC
WU
Brazos
Rice
函式庫
頁
ScC
Early update，
WU
Shasta
DEC WRL
編譯器
可變
SC
WI
Mermaid
Toronto
函式庫＋作業系統
頁(1KB，8KB)
SC
WI
Dsoftware DSM6K
IBM Research
作業系統
頁(4KB)
SC
WI
Mirage
UCLA
作業系統
512Bytes
SC
WI
JIAJIA
中國科學院
函式庫
頁(4KB)
ScC
WI
Simple-COMA
SICS(Sweden) and
SUN
作業系統
頁
SC
WI
Blizzard-S
Wisconsin
函式庫
快取行
SC
WI
Shrimp
Princeton
作業系統＋硬體支援
頁
AURC，SC
WU/WI
Linda
Yale
語言
可變
SC
Impl.dependent
Orca
Vrije Univ.,
Netherlands
語言
可變
同步相關
WU

Download Report