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

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

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

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

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

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

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

キャッシュコヒーレンシ 分散キャッシュの問題点 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

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

キャッシュコヒーレンシ コヒーレンシが保たれている： (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

キャッシュコヒーレンシ コヒーレンシが保たれている： (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

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

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

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;

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) 2 2 20 20 1 10 10 1 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;

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

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が不可能な状態になること．

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;

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;

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;

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;

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

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

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

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;

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;

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

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;

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

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

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)

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

ERC,LRC 前出の例題 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; ERC,LRCどちらでも動作する

ERC,LRC 前出の例題 a=b=flag=0に初期化 PE1： PE2： a=1; e=100; b=2; while(flag==0); flag=1; acq(L); rel(L); print a; c=d; print b; LRCでは動作しない

ソフトウェア分散共有メモリ　 SDSM: Software Distributed Shared Memory

分散共有メモリ 各PEに物理的に分散しているメモリを，プログラムからはひとつの共有メモリ（単一アドレス空間）として見せる技術 ハードウェアのキャッシュコヒーレンスによるもの CC-NUMAなどハードウェア自体が分散共有メモリタイプ ソフトウェアによるもの クラスタなどハードウェアは分散メモリタイプ 共有変数モデルでプログラミング可能 →メッセージパッシングの必要なし

ソフトウェア分散共有メモリ 各PEに物理的に分散したメモリ上で仮想的に共有メモリを提供 1980年代中期からシステムが出始める データの所在やアクセスの仕方を考慮する必要なし 1980年代中期からシステムが出始める 性能が上がらず普及せず 昨今のクラスタコンピューティングブームで見直されている 仮想記憶システムを利用（page-based DSM） Shared Virtual Memory(SVM) ページ単位（～4Kbyte)でコンシステンシ（一貫性）制御 アクセスデータがローカルメモリ上にない場合 → ページフォルト発生 他ノードかディスクから必要なページをフェッチ

ソフトウェア分散共有メモリ ページ転送機構：ページ共有と一貫性制御（無効化) ページ要求 無効化 PE1 PE2 PE3 read ミス x,y,z read(x) read(x) write(y)

ソフトウェア分散共有メモリ ページ転送機構：ページ共有と一貫性制御（一括書戻） ページ要求 書き戻し PE1 PE2 PE3 read ミス x,y,z read(x) read(x) write(y) write(x) sync

ソフトウェア分散共有メモリ コンシステンシ制御の単位が粗粒度のための利点 欠点 空間的局所性を利用可能 コンシステンシ制御オーバーヘッドが相対的に小さい 欠点 フォールスシェアリング（false sharing）による性能低下 異なるPEが異なる変数へ頻繁にアクセスする際，その変数群が同じページにマップされていると，PEがそのページを取り合う diff作成によるmultiple-writerプロトコルで対処できる

ソフトウェア分散共有メモリ false sharing 無効化 PE1 PE2 PE3 x,y write(x) write(y)

ソフトウェア分散共有メモリ IVY @Yale TreadMarks @Rice APOLLO AEGIS （DOMAIN/OS） 最初のソフトウェアDSM シーケンシャルコンシステンシを実装． TreadMarks @Rice LRCとMultiple-Writerを実装し性能を向上 APOLLO AEGIS （DOMAIN/OS） ネットワークワイドでのオブジェクト（ファイル）管理 単一階層記憶（ファイルを仮想記憶空間にマップ） ネットワークワイドでのデマンドページング Munin, JIAJIA, SCASH, Shasta, Midway, etc... メモリコンシステンシモデルの違い ページ配置（home based or not），ページ粒度

Multiple-Writer Protocol 同一ページへ複数PEが同時期に書込みできる PEは書き込みを始める際にページの元の状態をTwinとしてコピーを保存しておく 書き込みを行なった後，次の同期時点でTwinと書き込みを行ったページの差分（diff）を求める そのページを要求する他のノードにdiffを渡す そのページを要求するノードはdiffを集めページに反映させてからそのページにアクセスする diffの集積とページへの反映方法 diff分散方式：ページ要求時に各プロセッサからdiffを集め回る（Tread Marks） home based: 各ページのホームを決めておいて同期時にそこへ集積する（JIAJIA）

Multiple-Writer Protocol home based ページ要求 P0 P1 P2 write ミス home x,y,z write(x) twin作成

Multiple-Writer Protocol home based ページ要求 P0 P1 P2 write ミス home x,y,z write(y) twin作成

Multiple-Writer Protocol home based P0 P1 P2 home x,y,z diff作成 diff作成

高性能コンピューティング論Ⅰ 高性能コンピューティングのキーテクノロジである並列処理に関して，その原理と利用技術（主にソフトウエア）の視点から解説