print a

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