Lazy Release Consistency
東京大学大学院 情報理工学系研究科 電子情報学専攻
坂井修一研究室
修士１年 46424 豊島 隆志
Background: “Why”

Orchestration models

Shared Address Space Model


共有メモリをサポートした複雑な
ハードウェアが必要
×
プログラムが簡単
○


Message-Passing Model


特殊な追加ハードウェアを必要とし
ない
○
プログラムが複雑・面倒
×
Shared Virtual Memory - SVM


特殊な追加ハードウェアを必要とし
ない
○
プログラムが簡単
○
ソフトウェアで共有メモリを実装
Preliminary 1: Memory Management Unit - MMU
Application A

アドレス変換


Main Memory
ページ単位（4096Bなど）
ページ保護



Read
Write
eXecute
Application B
Shared Virtual Memory
Main Memory A
Main Memory B
Thread A
Thread B
Query
&
Answer
write
read
write
Implementation

As page fault handler


ページのドメイン、コヒーレンスを管理
Inter-System Communication

最低限Message Passingができれば良い


ページ情報の交換
ページデータの転送
Problems

Overheads




Page fault handler invocation
kernel land ⇔ user land switch
Message passing
Large Granularity

Poor spatial locality cause fragmentation

Useless data transfer
 for word, by page

False sharing
Hardware Shared Memory
Shared Virtual Memory
: <usec
: 数百usec～msec
Preliminary 2: Sharing Miss
他のデバイスからの書き込みが原因で起こるミス

False Sharing


厳密には競合していないが、大きな単位でまとめて管理
していたために起こしてしまったミス
True Sharing

仮に最小単位で管理していたとしても起きる、厳密にアド
レスが競合しているミス
Preliminary 2.1: True Sharing
Hit
read
Invalid
read
Miss
write
Preliminary 2.2: False Sharing
read
Miss
Invalid
write
Consistency Model

Sequential Consistency - SC


転送コストが高く、特にSVMでは現実的ではない
Relaxed Consistency – RC

Eager Release Consistency - ERC


write notices on release
Lazy Release Consistency - LRC

write notices on acquire
Relaxed Consistency - RC
PU 0
read y
read y
read y
read y
read y
Sync
PU 1
write x
write x write x
write x
write x
RC on Hardware Coherent Machines
False
Sharing
PU 0
read y
False
Sharing
False
Sharing
read y
read y
False
Sharing
read y
False
Sharing
read y
Sync.
PU 1
write x
write x write x
ack. latency
write x
write x
RC/Delayed Consistency
False
Sharing
PU 0
read y
read y
read y
Sync.
buffering
False
Sharing
False
Sharing
read y
read y
buffering
PU 1
write x
write x write x
write x
write x
RC/Eager Release Consistency
PU 0
read y
read y
read y
read y
read y
False
Sharing
False
Sharing
PU 1
write x
write x write x
write x
write x
PU 2
read y
False
Sharing
RC/Lazy Release Consistency
PU 0
read y
read y
read y
read y
read y
False
Sharing
PU 1
write x
write x write x
write x
write x
PU 2
read y
False
Sharing
RC, ERC vs LRC

writeが伝わるのは同期地点ではなく、acquire地点
Lock L1;
ptr = non_null_ptr_val;
Unlock L1;
While (ptr == null) {};
Lock L1;
a = ptr;
Unlock L1;
LRCではここで初めてptrへ
の書き込みが見える