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 Application B アドレス変換 ページ単位（4096Bなど） ページ保護 Read Write eXecute

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

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

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

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

Preliminary 2.1: True Sharing Hit read Miss read Invalid write

Preliminary 2.2: False Sharing Miss read Invalid write

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

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

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

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

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

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

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への書き込みが見える