Parallel Distributed Programming

並列・分散プログラムの
状態遷移モデル
講義全体の思想と目標
並列・分散プログラムの実行を定式化する
 定式化により

• 並列・分散アルゴリズムの正しさを正確に述べる
• 並列・分散アルゴリズムの正しさを証明する
• ある問題の不可能性(条件を満たすアルゴリズム
が存在しないこと)を証明する
並列・分散プログラミングモデル

メッセージパッシング
• プロセス + send/receiveによる通信・協調

共有メモリ
• プロセス + 共有メモリ(read/write)による通信・協調

もっと高水準なモデルも存在するが，講義で
は主に低水準なモデルを対象とする
• 低水準ゆえ汎用的
• 現実に多く使われている(pthread, MPI, etc.)
• 高水準なモデルの実装に必要
動機付け:並列プログラムの難しさ

以下は皆，似ていることの言い換え
• 「大域的な状態」を観測できない
• 出来事に大域的な「順序」が存在しない
• 操作の不可分性・原子性が保証できない
ほとんどの場合動作が非決定的である
 簡単でないこと

• 複数の場所の変数を「一度に」観測する
• 複数の場所の変数を「一度に」更新する
例:変数の同時更新

プロセスAとB: ともに(ローカル)変数pを保持
• 初期値は一致しているとする

目的:
• プロセスA : 何回かpをともに0にセット
• プロセスB : 何回かpをともに1にセット
• 回数・タイミングは不明
• 実行された操作のうち，どの値が残っても良いが，
両者が食い違うのは×(“同時”更新)
最初の試み

A:
while (1) {
…  p = 0; send(B, update);
| received(update)  p = 1;
}
B:
while (1) {
…  p = 1; send(A, update);
| received(update)  p = 0;
}
“p=0”
“q=0”
p=0
p=1
p=?
“p=1”
“p=1”
p=1
p=0
p=?
教訓
二つのプロセッサの変数を両方同時に更新
するのは自明でない
 複数の更新が「インターリーブ」する可能性が
ある
 原子性(不可分性)の欠如

第2回目の試み: 更新中フラグの導入

アイデア:
• 自分が更新中(locked)の間は相手の更新を待たせ
る
• 自分の更新が終了後，相手の更新を実行する
locked = 1
更新中フラグ


A: (me = 0, him = 1; Bは逆)
req = 0;
/* 相手からの未処理リクエスト */
locked = 0; /* 自分が相手にリクエスト中 */
while (1) {
!locked && …
 p = me; send(him, update); locked = 1;
| received(update)  req = 1;
| req && !locked  p = him; req = 0; send(him, ok);
| received(ok)  locked = 0;
}
正しい終了状態: pが一致．req/lockedはともに0
一見正しそう?
Aがひとたびsend(update) を実行したら，okを
受け取るまで，p = 1を実行しない
 okを受け取るには，Bでp = 0が実行されてい
るはず
 Bがその後p = 1を実行するかもしれないが，
その場合は自分もokの後にupdateを受け取
るはず(同一の送信者受信者間でのメッセー
ジ順序の保存を仮定)

誤り
p=?
p=0
l=0
l=1
r=0
r=1
“p=0”
“q=0”
“p=1”
“p=1”
p=?
p=1
l=0
l=1
r=0
r=1
デッドロック

A: (me = 0, him = 1; Bは逆)
req = 0;
/* 相手からの未処理リクエスト */
locked = 0; /* 自分が相手にリクエスト中 */
while (1) {
!locked && …
 p = me; send(him, update); locked = 1;
| received(update)  req = 1;
| req && !locked  p = him; req = 0; send(him, ok);
| received(ok)  locked = 0;
}
教訓

分散システムの終了状態
• これ以上実行可能な文がなくなること
•  プログラムの文面上の終了

望ましい状態に，いつか実際に到達すること
を証明する必要がある
• デッドロック: 間違った状態で終了する実行
• ライブロック: 望ましい状態に達しないまま，終了
しない(無限の長さを持つ)実行
この例題の一般化

複数プロセスにまたがるデータの原子的な更新
• データベースの更新 (直列化可能性)

分散共有メモリ
• 複製を伴うデータの一貫性のある更新(逐次一貫性)

Atomicマルチキャスト
• 全員に同じ順序でメッセージが届くマルチキャスト
注
問題は分散メモリのせいではない．共有メモ
リでも，複数の変数の更新には同じ困難があ
る
 A : pA = 0; pB = 0;
B: pB = 1; pA = 1;
ABBA

並列・分散計算のモデル

構成要素
• プログラム(プロセス)の記法
• プログラム  1プロセスの状態遷移グラフ
• 多数のプロセスの状態遷移グラフ + 通信手段 
大域的な状態遷移グラフ
メッセージパッシングプロセス

定義:メッセージパッシングプロセスとは5つ組
Z , I, i, s, r
• Z : プロセスの状態の集合
• I : 初期状態の集合( Z)
• i : プロセス内状態遷移関係の集合( Z  Z)
• 記法: z i z’
• s : 送信による状態遷移関係の集合( Z  M  Z)
• 記法: z s(m) z’
• r : 受信による状態遷移関係の集合( Z  M  Z)
• 記法: z r(m) z’
• ただしz, z’  Z, m  M : メッセージの集合
非同期メッセージパッシングシステム
nプロセス + 送受信システムC, I, 
 大域状態 C = z1, z2, … , zn, M

• M : メッセージのマルチ集合 = 送られて，まだ受け取
られていないメッセージの集合
• 変種
• Mを受信プロセスごとにわける(M1, … , Mn)
• Mを送信，受信プロセスペアごとに分ける(M11 , … , Mnn)
• 同一プロセスペア間でのメッセージ順序の保存(FIFO性)

大域初期状態 I = I1  …  In
非同期メッセージパッシングシステム
の大域状態遷移

プロセスiの内部遷移
• z1, … , zi, … , zn, M  z1, … , zi’, … , zn, M
iff zi i zi’

プロセスiの送信による遷移
• z1, … , zi, … , zn, M  z1, … , zi’, … , zn, M {m}
iff zi s(m) zi’

プロセスiの受信による遷移
• z1, … , zi, … , zn, M {m}  z1, … , zi’, … , zn, M
iff zi r(m) zi’
非同期メッセージパッシングシステム
の実行

c 1  c2  …
• ci : 大域状態( C)
• ci  ci+1 : 先で定義した大域状態遷移
メッセージパッシングプログラムの記
述法(1)


通常の手続き的な記述+通信・同期文
通信・同期文
• 送信:
send(dest, tag(式, 式, …))
• ガード付き文:
条件式  行動
| 条件式  行動
|…
| 条件式  行動
条件式:
• received(tag(a, b, …))または局所変数からなる式
メッセージパッシングプログラムの記述法
(2)

本質的ではないが，しばしば以下の条件を設
ける(条件式  行動をひとつの状態遷移
とみなせる)：
• 条件式は副作用なしの式
• 行動部で実行されるsendは高々1つ
• 条件式部がreceivedの場合， 行動部で
はsendは実行されない
プログラムと状態遷移系の関係
プロセスの状態 = 変数の値 + 実行場所(プロ
グラムカウンタ etc.)
 状態遷移

• 送受信以外の一連の文の実行：内部遷移
• 一回のsend文の実行を含む一連の文
• z s(m) z’ (z, z’は一連の文の実行前・後の状態)
• received(m)  送受信を含まない一連の文
• z r(m) z’ (同上)
注:

いわゆるnon-blocking受信
• received(m)  …
| true  …

このモデルは，いわゆるnon-blocking送信(送
信チャネルのバッファ容量は無限大)
重要な制約

ひとつの状態遷移でおこることは以下のひとつ(原
子性の欠如)
• 一プロセスpの内部状態変化
• 一プロセスpの内部状態変化+ pによる一メッセージの送
信
• 一プロセスの内部状態変化+ pによる一メッセージの受信
• おのおのをpによる遷移と呼ぶ

複数の状態遷移が可能な状態では，次にどの遷移
が起こるかは非決定的
共有メモリシステムのモデル

定義:共有メモリプロセスとは5つ組
Z , I, i, w, r
• Z : プロセスの状態の集合
• I : 初期状態の集合( Z)
• i : プロセス内状態遷移関係の集合( Z  Z)
• 記法: z i z’
• w : 共有変数への書き込みによる状態遷移関係の集合( Z  A 
M  Z)
• 記法: z w(a, m) z’
• r : 共有変数からの読み込みによる状態遷移関係の集合( Z  A
 M  Z)
• 記法: z r(a, m) z’
• ただしA : 共有変数(アドレス)の集合，M : メッセージの集合
共有メモリシステム
nプロセス + 共有変数の集合
 大域状態 C = z1, z2, … , zn, M

• M : 共有変数(A  M )

大域初期状態 I = I1  …  In
共有メモリシステムの大域状態遷移

プロセスiの内部遷移
• z1, … , zi, … , zn, M  z1, … , zi’, … , zn, M
iff zi i zi’

プロセスiのwriteによる遷移
• z1, … , zi, … , zn, G  z1, … , zi’, … , zn, G[a:=m] 
iff zi w(a, m) zi’

プロセスiのreadによる遷移
• z1, … , zi, … , zn, G  z1, … , zi’, … , zn, G
iff zi r(a, m) zi’ かつ G(a) = m
共有メモリプログラムの記述法


通常の手続き的な記述+共有変数アクセス
共有変数アクセス
• 書き込み:
a := v (a は共有変数)
• ガード付き文:
条件式  文
| 条件式  文
|…
| 条件式  文
制約: 条件式と対応する文には共有変数が高々1つしか現
れない
プログラムの正しさ

多くの場合，プログラムから導かれる状態遷
移系に関して，以下の二つを示すことになる
• 正しい終了: 初期状態から到達可能な終了状態
(これ以上の遷移がない状態)で，常にある望まし
い性質が成り立っている
• 停止性: 初期状態から，常に有限回の状態遷移
で終了状態に達する(停止性)
正しい終了

多くの場合，系のある「不変条件」Pを，以下
のように証明することに帰着
• P(i) for each i  I (初期状態でPが成立)
• P(c) かつ c  c’ ならばP(c’)

Pを証明した後で
• P(c)かつcが終了状態  Q(c)
• Q(c)が示したい性質
停止性
多くの場合，系のある値が各ステップで減少
すること，そのような降下列(decreasing
sequence)は常に有限であることを示すことに
帰着
 f : C  W (W : well-founded set. 無限の降下
列を持たない集合(例 : 自然数))
 c  c’ならばf(c) > f(c’)

例題の続きと証明

デッドロック防止の基本アイデア: AとBが衝
突したらAが勝つ
• AはBにnegative ackを送る
• Bはnegative ackを受け取ったらlockを解除してA
のrequestを実行
明文化されていない仮定


updateは有限回しか実行されない
証明のための単純な明文化(高々N回)
•

i > 0 && !locked
 send(him, update(me)); locked = 1; i--;
| i > 0 && !locked  i--;
| … (以下同様) …
また，同一プロセスペア間のメッセージ順序の保存
を仮定する(先に送ったほうが先に届く)
i = N;
/* 高々あと何回updateを送るか */
req = 0;
/* 相手からの未処理リクエスト */
locked = 0; /* 自分が相手にリクエスト中 */
while (1) {
i > 0 && !locked
1
 i--;send(him, update); locked = 1;
2 | i > 0 && !locked  i--;
3 | received(update)  req = 1;
4 | req && !locked  p = him; req = 0; send(him, ok);
5 | req && locked && me < him  req = 0; send(him, ng);
6 | received(ok)  locked = 0; p = me;
7 | received(ng)  locked = 0;
}

正しさの表明
任意の実行の長さは有限
 任意の終了状態(これ以上の遷移がない状
態)において，

• lockedA = lockedB = 0
• reqA = reqB = 0
• pA = pB
「実行の長さ有限」の証明


ほとんど明らか(updateは有限回しか送られない．ひ
とつのupdateメッセージからは有限個の状態遷移し
かおこらない)
正式な証明は，各遷移で「何か」の値が狭義に減少
することを示す．その値とは以下の組に辞書順(上
の要素ほど優先)で順序を入れたもの
•
•
•
•
i
M中のupdateメッセージの個数
reqの値
M中のok/ngメッセージの個数
正しい終了
任意の実行 C = c1  c2  …  cnをfix
 正しそうな表明:

• この実行中で実行された
• received(ok)  locked = 0; p = me;
• の遷移のうち，最後のものによって最終結果が
決まっているのだろう(つまり，もう一方のプロセ
スのpも同じ値で，かつlocked = req = 0)
pの一致

C中で最後に実行された
• received(ok)  locked = 0; p = me;
の遷移をeとする．これを実行したプロセスをx,
もう一方のプロセスをyとする．
 eが実行可能となるためには少なくとも一回，
yでsend(him, ok)が実行される必要があるか
ら，そのような最後の遷移をe1とする．以降で
は，C中でe1以降，yによるpへの代入(遷移4,
6)がおきないことを言う

e1以降yの遷移4はない

e1が，eに先立つyによるsend(him, ok)のうち
最後のものであるという仮定に反する
e1以降yの遷移6はない

e1が実行可能となるには，少なくとも一回，x
でsend(him, update)が実行される必要がある．
そのような最後の遷移をe2とする． e2実行後
lockedx = 1であり，eまでそうあり続ける(要詳
細化)．したがってe以前に実行されたxによる
send(him, ok)は，(あるとすれば) e2以前のも
のである．したがって，メッセージ順序の保存
より，yによるreceived(ok)は，あるとすればe1
に先立つ
locked = 0 (B)

Bによる，最後のlockedB = 1 (遷移1)が実行さ
れたら，いずれlockedB = 0 (遷移6, 7)が実行
される．実際，
• Aはいずれreceived(update) (遷移3)を実行
• Aはいずれ遷移4 or 5を実行
• Bはいずれ遷移6 or 7を実行

つまり，最終状態でlockedB = 0
locked = 0 (A)

Aによる最後のlockedA = 1 (遷移1)が実行されたら，
いずれlockedA = 0 (遷移6, 7)が実行される．実際，
• Bはいずれreceived(update) (遷移3)を実行(e’とする)
• Bが最後にlockedB = 1 lockedB = 0となった遷移をeとす
る．これ以降ずっとlockedB = 0に注意
• …, e, …, e’, …の場合：Bはいずれ遷移4を実行
• …, e’, …, e, …の場合：eまでにBが遷移4を実行しなければ，e直
後でなおreqB = 1．結局Bはいずれ遷移4を実行
• Aはいずれ遷移6 or 7を実行

つまり，最終状態でlockedA = 0
req = 0

最終状態ではlocked = 0である．ここでreq = 0
ならば遷移3が実行可能となり，それは最終
状態ではない
非同期メッセージパッシングプログラ
ムの性質と重要概念

用語: 遷移(transition)の代わりに事象(event)
ということもある
因果順序

ある実行Cを考える．C中のeventの因果順序
(causal order) とは以下を満たす最小の半
順序関係
• C中で…, a, …, b, … の順に現れ，a, bが同じプロ
セスのeventならばa  b
• C中で…, a, …, b, … の順に現れ，aがあるメッ
セージの送信，bがその受信ならばa  b
因果順序の性質
ある実行Cに対し，すべての因果順序を保っ
たまま，eventの順番を入れ替えても，それは
正しい実行であり，同じ最終状態に到達する
 直感的な意味: 因果順序にないeventが実行
された順番は観測不可能

• 互いに通信しないプロセス同士の内部遷移が
「どっちが先立ったか?」と問うても無駄
因果順序の性質(続)
「実行」は因果順序を拡張したeventの全順序
で，神のみが知る
 Event間の因果順序こそが，特定のプログラ
ムの実行を特徴付け(他の実行と区別し)てい
る

メッセージパッシングプログラムの実
行の図示

A
B
C
D
このような，横軸に時間，縦軸にプロセスを
とった図で表すことが多い．プロセス間のメッ
セージは斜めの線で表す
有用な見方
この図示はevent間の因果順序を表している
と見ることもできる．より正確には，
 メッセージの矢印の根元に送信event, 先端に
受信event, 水平線の各所に内部遷移がある
と思うと，
a  b  図上でaからbへ矢印の道がある

メッセージ図
= eventの因果順序関係の図示
A
B
C
D












 









              








メッセージ図と「実行」

A
B
C
D
神様はメッセージ図に示された矢印間の順序
は保ちながら次に実行するeventを任意に選
択していた…










  










              








実行

神様が実際に選択したeventの実行順序(全
順序)を知るすべはないが，「もっともらしい」
「観測と矛盾しない」実行順序を作ることは容
易である
• 因果順序を保った順序であればなんでもよい
aba<b
を満たす順序であればなんでもよい(そう考えても
矛盾はきたさない)
時計(Clock)


ある実行中のevent eに対して割り当てられた値C(e)
で，
a  b  C(a) < C(b)
を満たすものを時計という
例
• 正確に実時間と同期した時計があれば，もちろんそれは
時計である
• 神様が実行したeventの全順序を知ることができれば，
C(a) = その全順序でのaの位置
もまた(実現不可能な)時計である
Lamportの論理時計
簡単に実現可能な時計
 int Cp : (pの時刻)
 初期化 Cp := 0
 内部遷移: t = Cp ; Cp = t + 1;
 send(m)：
t = Cp ; mに時刻印t + 1を付加;
t = Cp + 1;
 recveived(m) :
t = max(Cp , mの時刻印); Cp = t + 1;

Lamportの論理時計の簡単な応用：
実行の再現
並列実行中：各eventに論理時計を付加して
記録(logging)
 再現実行中：論理時刻が小さい順にeventを
実行

公平性(Fairness)

停止性を「任意の実行系列」に対して証明す
ることは不可能であることが多い
• 例: どんなアルゴリズムでも，常に実行可能な無
意味な状態遷移をひとつ付け加えるだけで，常に
「終了しない実行」が可能になってしまう

証明の対象となる実行にある種の制限(公平
性; fairness)を設けることが必要になる
Weak Fairness

ある実行がweakly fairとは，
もう少し複雑な例題
極大木構築

G = V, E プロセスのネットワーク
• V : プロセス, E : 通信できるプロセスペア
各プロセスは自分の近隣ノード(neighbors)を
与えられる
 問題:

• 各プロセスで変数 parent を計算
• parentをポインタとしたグラフがEの生成木になっ
ている
10/18 加藤(数理), …
 10/25 今竹，堀田
 11/15 ふじたはやつ
 11/22 林
 11/29 吉本(電子情報)，吉田
 12/6 初田, 豊島


Download Report