メモリコンシステンシモデル memory consistency model

Presentation on theme: "メモリコンシステンシモデル memory consistency model"— Presentation transcript:

1 メモリコンシステンシモデル memory consistency model

2 メモリコンシステンシモデル 問題の所在： 複数PE（命令列）のコンピュータでは プログラムの意図と違う結果となりうる
同一PEでの異なるメモリロケーションへの複数アクセス命令 ＞命令発行順序はプログラムに記述された順とは限らない 　　∵データ依存が無いから ＞プログラム記述順で発行さても完了がその順とは限らない 　　　read完了：値を読み終える write完了：書き込んだ値を他のPEが観察できる あるPEでの異なるメモリロケーションへの複数write命令の結果は，他のPEで異なる順に観察することがありうる （write atomicityが無い場合） プログラムの意図と違う結果となりうる

3 メモリコンシステンシモデル メモリコンシステンシモデル： メモリアクセス命令の実行完了の順序変更（リオーダリング）にどのような制限を前提とするか（どのような順序変更が行われうると覚悟しなければいけないか）を定める メモリアクセスのリオーダリングを制限するほど →直感的にプログラムを理解しやすい →プログラムの最適化や並列化の可能性が低減 同一メモリロケーションへのアクセス命令に関しては 同一PE内では命令間にデータ依存があるので発行／完了の順序が逆転することはない キャッシュコヒーレンスメカニズムにより複数write命令による変数の値の更新が全PEで同一に観察される

4 キャッシュコヒーレンシ（cache coherency）
分散キャッシュ：各PEにローカルキャッシュ →同一変数（メモリロケーション）の複数キャッシュ上で存在することを許すと → キャッシュコヒーレンシ問題が発生 PE1 PE2 PE3 PE4 PE1 PE2 PE3 PE4 主 記 憶 $ 主 記 憶 $ 主 記 憶 $ 主 記 憶 $ $ $ $ $ 相互結合ネットワーク 相互結合ネットワーク 主記憶

5 キャッシュコヒーレンシ 分散キャッシュの問題点 y=x*2 →PE1 z=x+1　→PE3 x=x*3　→PE1 zz=x+1 →PE3 0.同一の変数が複数のキャッシュ上にコピー可能とする PE1 PE2 PE3 PE4 $ $ $ $ 相互結合ネットワーク x:3

6 キャッシュコヒーレンシ 分散キャッシュの問題点 1.PE1がxをread read miss 主記憶からPE1のキャッシュ 上にxをコピー
read(x) PE1 PE2 PE3 PE4 x:3 $ $ $ 相互結合ネットワーク x:3

7 キャッシュコヒーレンシ 分散キャッシュの問題点 2.PE3がxをread read miss 主記憶からPE3のキャッシュ 上にxをコピー
read(x) PE1 PE2 PE3 PE4 x:3 $ x:3 $ 相互結合ネットワーク x:3

8 キャッシュコヒーレンシ 分散キャッシュの問題点 3.PE1がxに書き込み write hit PE1のキャッシュだけを書換える
4.PE3が再度xをread read hit　 xの古い値をreadしてしまう！ write(x) read(x) PE1 PE2 PE3 PE4 x:9 x:3 $ x:3 $ 相互結合ネットワーク x:3

9 キャッシュコヒーレンシ コヒーレンシが保たれている： (1)あるプロセッサでのwriteの結果が他のプロセッサからも観察できる
書き換え方式(write-update) write(x) read(x) PE1 PE2 PE3 PE4 x:9 x:3 $ x:3 x:9 $ 相互結合ネットワーク x:3 x:9

10 キャッシュコヒーレンシ コヒーレンシが保たれている： (1)あるプロセッサでのwriteの結果が他のプロセッサからも観察できる
無効化方式(write-invalidate) write(x) read(x) PE1 PE2 PE3 PE4 x:9 x:3 $ x:3 x:9 x:? $ 相互結合ネットワーク x:3 x:9

11 キャッシュコヒーレンシ コヒーレンシが保たれている： (2)複数のwriteの順序が全てのプロセッサで同一に観察できる（write atomicityが有る） write(x=9) write(x=5) PE1 PE2 PE3 PE4 x:9 x:3 x:5 $ x:5 x:3 x:9 x:3 x:5 x:9 $ 相互結合ネットワーク x:3 x:5 x:9

12 キャッシュコヒーレンシ 通常，キャッシュコヒーレンシを保つようハードウェアを構成する
共有メモリ+共有バスでのスヌープ（のぞき見方式）キャッシュ 分散共有メモリでのデレクトリ方式（登録簿方式）キャッシュ コヒーレンスが保たれているとは同一変数へのwriteに関して： PEでのwriteの結果が他のPEでも観察できる 複数のwriteの結果が全てのプロセッサで同一順序に観察できる（最後のwriteが一意に決まる）

13 Sequential consistency （SC）
並列プログラムにおける各PEのプログラムの命令記述順序を保持したまま，全PEのプログラムをマージして一つの逐次プログラムとする場合，そのようなプログラムは複数考えられる． これらのプログラムを，「先行する命令が完了してから次の命令を実行する（writeはatomicに実行）」，というように逐次実行した結果の集合をAとする（命令列が複数あるので結果も複数）． 元の並列プログラムを並列実行した結果が必ずAの集合の要素となる場合，そのような実行をSequential Consistencyな実行とする．またそのように実行するシステムをSequential Consistencyなシステムとする．

14 Sequential consistency （SC）
a=1,b=2に初期化 PE1：　 PE2： a=10; print　b; b=20; print a; print　b; print a; a=10; b=20; a=10; b=20; print　b; print a; 全マージプログラム print　b; a=10; print a; b=20; print　b; a=10; b=20; print a; a=10; print　b; print a; b=20; a=10; print　b; b=20; print a;

15 Sequential consistency （SC）
print b, print aはこの順序を維持するとする SCでは結果(4)はありえない a=1,b=2に初期化 PE1：　 PE2： a=10; print　b; b=20; print a; 実行結果 (1) (2) (3) (4) print　b; print a; a=10; b=20; print　b; a=10; print a; b=20; print　b; a=10; b=20; print a; a=10; print　b; print a; b=20; a=10; print　b; b=20; print a; a=10; b=20; print　b; print a;

16 Sequential consistency （SC）
直感に合う 制限がきつすぎる コード最適化がほとんどできない メモリアクセスレイテンシを隠蔽できない 並列プログラムの意味を保つためにはそこまで制限をきつくする必要はない SCの制限を緩和したコンシステンシモデルの必要性

17 TSO,PC SCの制限を以下のように緩和したモデル 1)Total Store Ordering （TSO）
あるプロセッサでのWriteが完了とは，他の全プロセッサで，そのWriteされた値のReadが可能な状態になること． TSO,PC SCの制限を以下のように緩和したモデル 各PEにおいて，read は，先行するwriteの完了を待たずに，完了可能とする （write間/read間の実行順序は保たれる） 　1)Total Store Ordering （TSO） writeはSCと同様アトミックに実行 　2)Processor Consistency （PC） TSOと同様だが，さらにwriteはアトミックではないとする 先行するwriteがキャッシュミスした際などのレイテンシを隠蔽可能．ストアバッファの利用． あるプロセッサでのReadが完了とは，他のプロセッサで，そのReadする値のWriteが不可能な状態になること．

18 TSO,PC read が，先行するwriteの完了を待たずに完了可能とすると・・・ a=flag=0に初期化 PE1： PE2：
write間およびread（printはreadと同じ）間の実行順序が保たれるのでSCと同じ結果 a=flag=0に初期化 PE1：　　　　　　　　　PE2： a=1; while(flag==0) ; flag=1; print a;

19 TSO,PC read が，先行するwriteの完了を待たずに完了可能とすると・・・ a=1,b=2に初期化 PE1： PE2：
write間およびread（printはreadと同じ）間の実行順序が保たれるのでSCと同じ結果 a=1,b=2に初期化 PE1：　 PE2： a=10; print　b; b=20; print a;

20 TSO,PC read が，先行するwriteの完了を待たずに完了可能とすると・・・ print b; a=1,b=2に初期化
SCでは「2,10」「1,20」「10,20」「20,10」はあっても　 「1，2」や「2,1」のプリントはありえない TSOとPCではreadの完了がwriteの完了を待たなくて良いため, 「1，2」や「2,1」の結果もありうる a=1,b=2に初期化 PE1：　 PE2： a=10; b=20; print b; print a; print　b; print a; a=10; b=20;

21 TSO,PC read が，先行するwriteの完了を待たずに完了可能とすると・・・ a=b=0に初期化 PE1： PE2： PE3:
PCではwriteがatomicでないため，aが0とプリントされる可能性もある PCでは，PE2にはa=1が伝わっていてもPE3には伝わっていない可能性あり a=b=0に初期化 PE1： PE2： PE3: a=1; while(a==0); while(b==0); b=1; print a;

22 TSO,PC TSO，PCでSCを保証するには同期メカニズムが必要
readが，先行するwriteの完了を待つようにする 例）メモリバリア命令 writeのatomicityを保証する（PCの場合） PSO（Partial Store Ordering, Sun Sparc） writeが，先行するwriteの完了を待たずに完了可能

23 WC,RC さらに制限を以下のように緩和したモデル
readもwriteも，先行するreadやwriteの完了を待たずに完了することができる 　1)Weak Consistency（WC） 2)Release Consistency（RC）

24 WC Weak Consistency プログラム中に「同期命令」を挿入する．
同期命令は，それより先に記述されているreadやwriteの完了後でなければ発行できない 同期命令より後に記述されているreadやwriteは，その同期命令完了後でなければ発行できない 同期命令間のreadやwriteは任意にリオーダリングできる 同期命令自体はSCを満たさなければならない

25 WC Weak Consistency a=b=flag=0に初期化 PE1： PE2： a=1; e=100;
二つのprintの順番は入れ替えられる可能性があるので「1,2」または「2,1」とプリントされうる．a,bとも0とプリントされることは無い a=b=flag=0に初期化 PE1：　　　　　　　　　 PE2： a=1; e=100; b=2; while(flag==0(sync)); flag=1(sync); print a; c=d; print b;

26 WC Weak Consistency a=b=flag=0に初期化 PE1： PE2： a=1; e=100;
c=d;はflag=1;が終了してから出ないと実行できない．この二つの命令は特に順序関係は必要ないのに... 同様にwhileはe=100;が完了してから出ないと実行できない．特に順序関係は必要ないのに...そこで a=b=flag=0に初期化 PE1：　　　　　　　　　 PE2： a=1; e=100; b=2; while(flag==0(sync)); flag=1(sync); print a; c=d; print b;

27 RC Release Consistency 同期命令を「獲得命令」と「解放命令」の二つに分ける
獲得命令の後に記述されているreadやwrite命令は獲得命令完了後でなければ発行できない 獲得命令は，それより前に記述されているreadやwriteの完了を待つ必要は無い 解放命令は，それより前に記述されているreadやwrite命令の完了後でなければ発行できない 解放命令後に記述されているreadやwriteは解放命令の完了を待つ必要は無い 獲得命令はreadに対応させ，解放命令はwriteに対応させ，これらはPCに従う それ以外は任意にリオーダリング可能

28 RC Release Consistency a=b=flag=0に初期化 PE1： PE2： a=1; e=100;
c=d;はflag=1;の完了を待たずに発行可能 while;はe=100;の完了を待たずに発行可能 a=b=flag=0に初期化 PE1：　　　　　　　　　 PE2： a=1; e=100; b=2; acq(L); flag=1; while(flag==0); rel(L); print a; c=d; print b;

29 ERC,LRC Eager Release Consistency Lazy Release Consistency
解放命令より前に記述されているwrite命令の結果は，解放命令を実行した時点でコピーを持っているプロセッサに一括して送付される writeの粒度を大きくできる Lazy Release Consistency 解放命令より前に記述されているwrite命令の結果は，その解放命令に対応する獲得命令が実行された時点でそれを実行したプロセッサにのみ一括して送付される writeによるトラフィックを軽減することができる どちらもソフトウェアDSMで利用される

30 ERC,LRC ERC PE1 PE2 PE3 PE4 x x aq(L) x= 書込みがあっても何もしない rl(L) 無効化 無駄な通信
read miss／page copy =x rl(L)

31 ERC,LRC ERC LRC PE1 PE2 PE3 PE4 PE1 PE2 PE3 PE4 x x x aq(L) aq(L) x x=
rl(L) rl(L) 何もしない 無効化 aq(L) aq(L) =x =x read miss／page copy rl(L) rl(L)

32 ERC,LRC ロックマネージャ ERC P0 P1 P2 P3 x x aq(L) x= rl(L) aq(L) =x rl(L)