メモリコンシステンシモデル memory consistency model 1 メモリコンシステンシモデル • 問題の所在: 複数PE(命令列)のコンピュータでは – 同一PEでの異なるメモリロケーションへの複数アクセス命令 >命令発行順序はプログラムに記述された順とは限らない ∵データ依存が無いから >プログラム記述順で発行さても完了がその順とは限らない read完了:値を読み終える write完了:書き込んだ値を他のPEが観察できる – あるPEでの異なるメモリロケーションへの複数write命令の結 果は,他のPEで異なる順に観察することがありうる (write atomicityが無い場合) • プログラムの意図と違う結果となりうる 2 メモリコンシステンシモデル • メモリコンシステンシモデル: メモリアクセス命令の実行完了の順序変更(リオーダリ ング)にどのような制限を前提とするか(どのような順序 変更が行われうると覚悟しなければいけないか)を定め る • メモリアクセスのリオーダリングを制限するほど →直感的にプログラムを理解しやすい →プログラムの最適化や並列化の可能性が低減 • 同一メモリロケーションへのアクセス命令に関しては – 同一PE内では命令間にデータ依存があるので発行/完了の 順序が逆転することはない – キャッシュコヒーレンスメカニズムにより複数write命令による 変数の値の更新が全PEで同一に観察される 3 キャッシュコヒーレンシ(cache coherency) • 分散キャッシュ:各PEにローカルキャッシュ →同一変数(メモリロケーション)の複数キャッシュ上で 存在することを許すと → キャッシュコヒーレンシ問題が発生 PE1 主 記 憶 $ PE2 主 記 憶 $ PE3 主 記 憶 $ 主 記 憶 相互結合ネットワーク PE4 PE1 PE2 PE3 PE4 $ $ $ $ $ 相互結合ネットワーク 主記憶 4 キャッシュコヒーレンシ • 分散キャッシュの問題点 y=x*2 →PE1 z=x+1 →PE3 x=x*3 →PE1 zz=x+1 →PE3 0.同一の変数が複数のキャッシュ 上にコピー可能とする PE1 PE2 PE3 PE4 $ $ $ $ 相互結合ネットワーク x:3 5 キャッシュコヒーレンシ • 分散キャッシュの問題点 1.PE1がxをread read miss 主記憶からPE1のキャッシュ 上にxをコピー read(x) PE1 PE2 PE3 PE4 x:3 $ $ $ 相互結合ネットワーク x:3 6 キャッシュコヒーレンシ • 分散キャッシュの問題点 2.PE3がxをread read miss 主記憶からPE3のキャッシュ 上にxをコピー read(x) PE1 PE2 PE3 PE4 x:3 $ x:3 $ 相互結合ネットワーク x:3 7 キャッシュコヒーレンシ • 分散キャッシュの問題点 3.PE1がxに書き込み write hit PE1のキャッシュだけを書換える read(x) write(x) PE1 PE2 PE3 PE4 x:3 x:9 $ x:3 $ 相互結合ネットワーク 4.PE3が再度xをread read hit xの古い値をreadしてしまう! x:3 8 キャッシュコヒーレンシ • コヒーレンシが保たれている: read(x) write(x) (1)あるプロセッサでのwriteの PE1 PE2 PE3 PE4 結果が他のプロセッサからも 観察できる – 書き換え方式(write-update) x:9 x:3 $ x:9 x:3 $ 相互結合ネットワーク x:9 x:3 9 キャッシュコヒーレンシ • コヒーレンシが保たれている: read(x) write(x) (1)あるプロセッサでのwriteの PE1 結果が他のプロセッサからも 観察できる x:3 x:9 – 無効化方式(write-invalidate) PE2 PE3 PE4 $ x:9 x:3 x:? $ 相互結合ネットワーク x:9 x:3 10 キャッシュコヒーレンシ • コヒーレンシが保たれている: write(x=5) write(x=9) (2)複数のwriteの順序が全て PE1 のプロセッサで同一に観察で x:3 x:5 きる(write atomicityが有る) x:9 PE2 PE3 PE4 $ x:9 x:3 x:5 x:5 x:3 $ x:9 相互結合ネットワーク x:9 x:3 x:5 11 キャッシュコヒーレンシ • 通常,キャッシュコヒーレンシを保つようハードウェアを 構成する – 共有メモリ+共有バスでのスヌープ(のぞき見方式)キャッシュ – 分散共有メモリでのデレクトリ方式(登録簿方式)キャッシュ • コヒーレンスが保たれているとは同一変数へのwriteに 関して: – PEでのwriteの結果が他のPEでも観察できる – 複数のwriteの結果が全てのプロセッサで同一順序に観察で きる(最後のwriteが一意に決まる) 12 Sequential consistency (SC) • Sequential Consistency(SC) – 並列プログラムにおける各PEのプログラムの命令記述順序を 保持したまま,全PEのプログラムをマージして一つの逐次プロ グラムとする場合,そのようなプログラムは複数考えられる. – これらのプログラムを,「先行する命令が完了してから次の命令 を実行する(writeはatomicに実行)」,というように逐次実行した 結果の集合をAとする(命令列が複数あるので結果も複数). – 元の並列プログラムを並列実行した結果が必ずAの集合の要 素となる場合,そのような実行をSequential Consistencyな実 行とする.またそのように実行するシステムをSequential Consistencyなシステムとする. 13 Sequential consistency (SC) a=1,b=2に初期化 PE1: PE2: a=10; print b; b=20; print a; 全マージプログラム print b; a=10; print a; b=20; print b; a=10; b=20; print a; print b; print a; a=10; b=20; a=10; b=20; print b; print a; a=10; print b; print a; b=20; a=10; print b; b=20; print a; 14 Sequential consistency (SC) a=1,b=2に初期化 PE1: PE2: a=10; print b; b=20; print a; print b, print aはこの順 序を維持するとする • SCでは結果(4)はありえない 実行結果 (1) (2) (3) (4) 2 2 20 20 1 10 10 1 a=10; a=10; a=10; print b; print print b; b; a=10; print a=10; a; b=20; print print b;b; b=20; a=10; print print b=20; a; a; b; print print a; a;a; b=20; b=20; b=20; print print 15 Sequential consistency (SC) • 直感に合う • 制限がきつすぎる – コード最適化がほとんどできない – メモリアクセスレイテンシを隠蔽できない • 並列プログラムの意味を保つためにはそこまで制限を きつくする必要はない • SCの制限を緩和したコンシステンシモデルの必要性 16 TSO,PC あるプロセッサでのWriteが完了とは,他 の全プロセッサで,そのWriteされた値 のReadが可能な状態になること. • SCの制限を以下のように緩和したモデル – 各PEにおいて,read は,先行するwriteの完了を待たずに, 完了可能とする (write間/read間の実行順序は保たれる) あるプロセッサでのRead 1)Total Store Ordering (TSO) – writeはSCと同様アトミックに実行 2)Processor Consistency (PC) が完了とは,他のプロセ ッサで,そのReadする値 のWriteが不可能な状態 になること. – TSOと同様だが,さらにwriteはアトミックではないとする • 先行するwriteがキャッシュミスした際などのレイテンシ を隠蔽可能.ストアバッファの利用. 17 TSO,PC • read が,先行するwriteの完了を待たずに完了可能と すると・・・ a=flag=0に初期化 PE1: PE2: a=1; while(flag==0) ; flag=1; print a; • write間およびread(printはreadと同じ)間の実行順序 が保たれるのでSCと同じ結果 18 TSO,PC • read が,先行するwriteの完了を待たずに完了可能と すると・・・ a=1,b=2に初期化 PE1: PE2: a=10; print b; b=20; print a; • write間およびread(printはreadと同じ)間の実行順序 が保たれるのでSCと同じ結果 19 TSO,PC • read が,先行するwriteの完了を待たずに完了可能と すると・・・ a=1,b=2に初期化 PE1: PE2: a=10; b=20; print b; print a; print b; print a; a=10; b=20; • SCでは「2,10」「1,20」「10,20」「20,10」はあっても 「1,2」や「2,1」のプリントはありえない • TSOとPCではreadの完了がwriteの完了を待たなくて 良いため, 「1,2」や「2,1」の結果もありうる 20 TSO,PC • read が,先行するwriteの完了を待たずに完了可能と すると・・・ a=b=0に初期化 PE1: PE2: a=1; while(a==0); b=1; PE3: while(b==0); print a; • TSOではプログラマの意図どおりの結果となる • PCではwriteがatomicでないため,aが0とプリントされ る可能性もある – PCでは,PE2にはa=1が伝わっていてもPE3には伝わってい 21 ない可能性あり TSO,PC • TSO,PCでSCを保証するには同期メカニズムが必要 – readが,先行するwriteの完了を待つようにする 例)メモリバリア命令 – writeのatomicityを保証する(PCの場合) • PSO(Partial Store Ordering, Sun Sparc) – writeが,先行するwriteの完了を待たずに完了可能 22 WC,RC • さらに制限を以下のように緩和したモデル – readもwriteも,先行するreadやwriteの完了を待たずに完了 することができる 1)Weak Consistency(WC) 2)Release Consistency(RC) 23 WC • Weak Consistency – プログラム中に「同期命令」を挿入する. – 同期命令は,それより先に記述されているreadやwriteの完 了後でなければ発行できない – 同期命令より後に記述されているreadやwriteは,その同期 命令完了後でなければ発行できない – 同期命令間のreadやwriteは任意にリオーダリングできる – 同期命令自体はSCを満たさなければならない 24 WC • Weak Consistency 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; • a=1;とb=2;の順序は入れ替えられる. • 二つのprintの順番は入れ替えられる可能性があるので 「1,2」または「2,1」とプリントされうる.a,bとも0とプリント されることは無い 25 WC • Weak Consistency 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; • c=d;はflag=1;が終了してから出ないと実行できない.こ の二つの命令は特に順序関係は必要ないのに... • 同様にwhileはe=100;が完了してから出ないと実行でき ない.特に順序関係は必要ないのに...そこで 26 RC • Release Consistency – 同期命令を「獲得命令」と「解放命令」の二つに分ける – 獲得命令の後に記述されているreadやwrite命令は獲得命令 完了後でなければ発行できない 獲得命令は,それより前に記述されているreadやwriteの完了 を待つ必要は無い – 解放命令は,それより前に記述されているreadやwrite命令の 完了後でなければ発行できない 解放命令後に記述されているreadやwriteは解放命令の完了を 待つ必要は無い – 獲得命令はreadに対応させ,解放命令はwriteに対応させ,こ れらはPCに従う – それ以外は任意にリオーダリング可能 27 RC • Release Consistency 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; • c=d;はflag=1;の完了を待たずに発行可能 • while;はe=100;の完了を待たずに発行可能 28 ERC,LRC • Eager Release Consistency – 解放命令より前に記述されているwrite命令の結果は,解放 命令を実行した時点でコピーを持っているプロセッサに一括し て送付される – writeの粒度を大きくできる • Lazy Release Consistency – 解放命令より前に記述されているwrite命令の結果は,その 解放命令に対応する獲得命令が実行された時点でそれを実 行したプロセッサにのみ一括して送付される – writeによるトラフィックを軽減することができる • どちらもソフトウェアDSMで利用される 29 ERC,LRC ERC PE1 x PE2 PE3 PE4 x aq(L) x= 書込みがあっても何もしない rl(L) 無駄な通信 無効化 aq(L) =x read miss/page copy rl(L) 30 ERC,LRC ERC PE1 x LRC PE2 aq(L) PE3 PE4 PE1 x x PE2 PE3 aq(L) x= x= rl(L) rl(L) 何もしない PE4 x 無効化 aq(L) aq(L) =x =x rl(L) read miss/page copy rl(L) 31 ERC,LRC ERC P0 x P1 aq(L) P2 P3 x x= rl(L) aq(L) =x rl(L) 32 ソフトウェア分散共有メモリ SDSM: Software Distributed Shared Memory 35 分散共有メモリ • 各PEに物理的に分散しているメモリを,プログラムから はひとつの共有メモリ(単一アドレス空間)として見せる 技術 – ハードウェアのキャッシュコヒーレンスによるもの CC-NUMAなどハードウェア自体が分散共有メモリタイプ – ソフトウェアによるもの クラスタなどハードウェアは分散メモリタイプ • 共有変数モデルでプログラミング可能 →メッセージパッシングの必要なし 36 ソフトウェア分散共有メモリ • 各PEに物理的に分散したメモリ上で仮想的に共有メモ リを提供 – データの所在やアクセスの仕方を考慮する必要なし • 1980年代中期からシステムが出始める – 性能が上がらず普及せず – 昨今のクラスタコンピューティングブームで見直されている • 仮想記憶システムを利用(page-based DSM) – Shared Virtual Memory(SVM) – ページ単位(~4Kbyte)でコンシステンシ(一貫性)制御 – アクセスデータがローカルメモリ上にない場合 → ページフォルト発生 他ノードかディスクから必要なページをフェッチ 37 ソフトウェア分散共有メモリ • ページ転送機構:ページ共有と一貫性制御(無効化) 無効化 ページ要求 PE1 PE2 read ミス read ミス read(x) read(x) write(y) PE3 x,y,z 38 ソフトウェア分散共有メモリ • ページ転送機構:ページ共有と一貫性制御(一括書戻) ページ要求 書き戻し PE1 PE2 PE3 read ミス x,y,z read(x) read(x) write(y) write(x) sync 39 ソフトウェア分散共有メモリ • コンシステンシ制御の単位が粗粒度のための利点 – 空間的局所性を利用可能 – コンシステンシ制御オーバーヘッドが相対的に小さい • 欠点 – フォールスシェアリング(false sharing)による性能低下 – 異なるPEが異なる変数へ頻繁にアクセスする際,その変数 群が同じページにマップされていると,PEがそのページを取り 合う – diff作成によるmultiple-writerプロトコルで対処できる 40 ソフトウェア分散共有メモリ • false sharing PE1 無効化 PE2 PE3 write(x) write(x) write(y) write(y) x,y 41 ソフトウェア分散共有メモリ • IVY @Yale – 最初のソフトウェアDSM – シーケンシャルコンシステンシを実装. • TreadMarks @Rice – LRCとMultiple-Writerを実装し性能を向上 • APOLLO AEGIS (DOMAIN/OS) – ネットワークワイドでのオブジェクト(ファイル)管理 – 単一階層記憶(ファイルを仮想記憶空間にマップ) – ネットワークワイドでのデマンドページング • Munin, JIAJIA, SCASH, Shasta, Midway, etc... – メモリコンシステンシモデルの違い – ページ配置(home based or not),ページ粒度 42 Multiple-Writer Protocol • 同一ページへ複数PEが同時期に書込みできる – PEは書き込みを始める際にページの元の状態をTwinとして コピーを保存しておく – 書き込みを行なった後,次の同期時点でTwinと書き込みを行 ったページの差分(diff)を求める – そのページを要求する他のノードにdiffを渡す – そのページを要求するノードはdiffを集めページに反映させて からそのページにアクセスする • diffの集積とページへの反映方法 – diff分散方式:ページ要求時に各プロセッサからdiffを集め回 る(Tread Marks) – home based: 各ページのホームを決めておいて同期時にそ こへ集積する(JIAJIA) 43 Multiple-Writer Protocol home based P0 ページ要求 P1 P2 write ミス home x,y,z write(x) twin作成 44 Multiple-Writer Protocol home based P0 ページ要求 P1 P2 write ミス home x,y,z write(y) twin作成 45 Multiple-Writer Protocol home based P0 P1 P2 home x,y,z diff作成 diff作成 46 高性能コンピューティング論Ⅰ 高性能コンピューティングのキーテクノロジである並列 処理に関して,その原理と利用技術(主にソフトウエア) の視点から解説 47
© Copyright 2025 ExpyDoc