Lazy Release Consistency

Presentation on theme: "Lazy Release Consistency"— Presentation transcript:

1 Lazy Release Consistency
東京大学大学院 情報理工学系研究科 電子情報学専攻 坂井修一研究室 修士１年 豊島 隆志

2 Background: “Why” Orchestration models Shared Address Space Model
共有メモリをサポートした複雑なハードウェアが必要 × プログラムが簡単 ○ Message-Passing Model 特殊な追加ハードウェアを必要としない ○ プログラムが複雑・面倒 × Shared Virtual Memory - SVM 特殊な追加ハードウェアを必要としない ○ プログラムが簡単 ○ ソフトウェアで共有メモリを実装

3 Preliminary 1: Memory Management Unit - MMU
Application A Main Memory Application B アドレス変換 ページ単位（4096Bなど） ページ保護 Read Write eXecute

4 Shared Virtual Memory Main Memory A Main Memory B Query & Answer
Thread A Thread B write read write

5 Implementation As page fault handler Inter-System Communication
ページのドメイン、コヒーレンスを管理 Inter-System Communication 最低限Message Passingができれば良い ページ情報の交換 ページデータの転送

6 Problems Overheads Large Granularity 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 : <usec Shared Virtual Memory : 数百usec～msec

7 Preliminary 2: Sharing Miss
他のデバイスからの書き込みが原因で起こるミス False Sharing 厳密には競合していないが、大きな単位でまとめて管理していたために起こしてしまったミス True Sharing 仮に最小単位で管理していたとしても起きる、厳密にアドレスが競合しているミス

8 Preliminary 2.1: True Sharing
Hit read Miss read Invalid write

9 Preliminary 2.2: False Sharing
Miss read Invalid write

10 Consistency Model Sequential Consistency - SC Relaxed Consistency – RC
転送コストが高く、特にSVMでは現実的ではない Relaxed Consistency – RC Eager Release Consistency - ERC write notices on release Lazy Release Consistency - LRC write notices on acquire

11 Relaxed Consistency - RC
Sync PU 0 read y read y read y read y read y PU 1 write x write x write x write x write x

12 RC on Hardware Coherent Machines
False Sharing False Sharing False Sharing False Sharing False Sharing Sync. PU 0 read y read y read y read y read y write notice ack. write notice ack. write notice ack. write notice ack. write notice ack. PU 1 write x write x write x write x write x ack. latency

13 RC/Delayed Consistency
False Sharing False Sharing False Sharing Sync. PU 0 read y read y read y read y read y write notice ack. write notice ack.x2 write notice ack.x2 buffering buffering PU 1 write x write x write x write x write x

14 RC/Eager Release Consistency
PU 0 read y read y read y read y read y False Sharing False Sharing release release PU 1 write x write x write x write x write x release release PU 2 read y False Sharing

15 RC/Lazy Release Consistency
PU 0 read y read y read y read y read y False Sharing acquire w.n. PU 1 write x write x write x write x write x acquire w.n. PU 2 read y False Sharing

16 LRCではここで初めてptrへの書き込みが見える
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への書き込みが見える