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

メモリコンシステンシモデル
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

Download Report