共有メモリ
次のプログラムの出力は?
初期値: a = b = 0
 P:
a = 1;
printf(“b=%d\n”, b);
Q:
b = 1;
printf(“a=%d\n”, a);

選択肢
a=1
b=1
a=1
b=0
a=0
b=1
a=0
b=0

a = b = 0はなさそう


P: W(a=1), R(b)
Q: W(b=1), R(a)
可能な順序
•
•
•
•
•
•
PPQQ: W(a=1), R(b), W(b=1), R(a) -> a=1, b=0
PQPQ: W(a=1), W(b=1), R(b), R(a) -> a=1, b=1
PQQP: W(a=1), W(b=1), R(a), R(b) -> a=1, b=1
QPPQ: W(b=1), W(a=1), R(b), R(a) -> a=1, b=1
QPQP: W(b=1), W(a=1), R(a), R(b) -> a=1, b=1
QQPP: W(b=1), R(a), W(a=1), R(b) -> a=0, b=1
別の言い方としては
“a = 0” => R(a); W(a=1) => W(b=1); R(a);
W(a=1); R(b) => “b=1”
 “a=0” かつ “b=0” => R(a); W(a=1) かつ
R(b); W(b=1)

たった今行ったreasoning:
“sequential consistency”

プログラムの挙動は,
• 各プロセッサが発行(issue)したread/writeがど
のような順番でinterleaveするかはわからない,
しかし
• 「あるひとつの順番で」interleaveされ,
• しかもその順番は各プロセッサがread/write
を発行した順番と矛盾していない
• ような挙動である
Sequential Consistencyは共有メ
モリプログラムをを書くときに反
射的に仮定しているモデル
v = …;
done = 1;
 while (done == 0);
… = v;

Sequential Consistency

アクセス
• write(x, v) xにvを書く
• read(x, v) xを読みvを得る
• プログラムの実行: アクセスの列

ある実行がsequentially consistent 
• 全プロセッサがissueした全アクセスの全順序a1 < a2 <
… < an が存在する
• その順序は各プロセッサがread/writeを発行した順序
(program order)を拡張したものである
ポイント
グローバルな,唯一の順序(write
atomicity)
 アクセスの入れ替えがない(program order
の保存)

なぜこんな当たり前のことが重
要?



Sequential consistencyを,性能のロスなく満たす
ことは難しい
実際,現実のHWの多くが,sequential
consistencyを満たしていない
HWのみならず,ソフトウェアで共有メモリ(もどき)
を実装することがある
• 「実装」と「挙動」の関係の理解

多くのプログラムはsequential consistencyを全て
の場所で要求するわけではない
Sequential Consistencyを満たす
ための(ひとつの)十分条件

各プロセッサは,
• writeをissueした後,そのwriteが完了するまで
次のread/writeをissueしない
• readが返す値を書いたwriteが完了するまで次
のread/writeをissueしない
Sequentially Consistentなシステ
ムの実例(1)
Nプロセッサ(P1, …, PN),Lメモリモジュー
ル(M1, …, ML)
 プロセッサ-メモリ間のネットワーク
 cache (replica)が存在しない.全てのメモリ
アクセスが該当メモリモジュールへ送られ
る

プロトコル

プロセッサ
• write(x, v) : write(x, v, p)モジュールへ送り,
ackを待つ
• read(x) : read(x, p)を該当するモジュールへ送
り,返事を待つ

メモリ
• received(write(x, v, p)) -> pへackを送る
• received(read(x, p)) -> pへ値を送る
Sequentially Consistentの証明

event
•
•
•
•

s : メモリアクセスのissue (send)
r : メモリアクセスのreceive
a : メモリアクセスのackのreceive
< : 実際の実行における順序関係
メモリアクセス
• a = (s, r, a) send/receive/ack eventの組

(s1, r1, a1) <’ (s2, r2, a2)  s1 < s2 または r1 <
r2
<がサイクルを含まない
(s1, r1, a1) <’ (s2, r2, a2) <’ … <’ (sn, rn,
an) <’ (s1, r1, a1)とする
 すべて同じメモリへのアクセスのとき:

• r1 < r2 < … < rn < r1 となり矛盾

(s1, r1, a1) <p (s2, r2, a2) => s1 < r1 < a1 <
s2 < r2, とくにr1 < r2
Violationの例
writeの完了を待たない
 例を出す

Cache Coherentシステム

あるcacheの,ある共有変数xに対する状態
• invalidまたはcacheにない(read/writeともserve
不可能)
• shared (readのみserve可)
• exclusive (read/write serve可)
Cacheの存在下でのSequentially
Consistentなシステム

バス結合システム
• すべてのrequest/responseはバスでserializeさ
れ,かつbroadcastされる
write: replicaがexclusiveでなければバスに
メッセージを送り,全cacheのinvalidateを待
つ
 read: replicaがなければバスにメッセージを
送り,replicaを作る

Violationの例

write buffer
現実のプロセッサのconsistency
model






Weak Ordering, Release Consistency
SPARC Relaxed Memory Ordering (RMO)
Processor Consistency (Pentium)
Alpha
PowerPC
共通アイデア
• アクセスのreorderingを許す
• Orderingを保証するための特別な命令(fence, barrier)
Weak Ordering

sync : 特別な命令
• semantics: syncをまたがってアクセスがreorder
されることはない
• a1; a2; a3; sync; a4; a5; a6
• ○ a2 -> a3 -> a1 -> a4 -> a6 -> a5
• × a2 -> a3 -> a4 -> a1 -> a6 -> a5
SPARC RMO

Weak Orderingの実例
• syncの代わりにMEMBAR命令
• MEMBAR #LoadStore : MEMBAR以前の
Loadを以降のStoreが追い越さない
• sync = MEMBAR
#LoadLoad|#LoadStore|#StoreLoad|#StoreStor
e
こんなんでプログラム書けるの
か?

Practice:
• 同じ変数に複数のプロセッサがアクセスする場合,以
下の場合がほとんど
• 同期(排他制御,producer/consumer etc.)で分離さ
れている
• readアクセスのみ
• 同期で分離された各部分はで,どんな風にreorderさ
れようと結果には関係ない
• しかも同期はlibraryなどを使えば自分でsyncを書く必
要はない
ダウンロード

共有メモリ