a(2)

プログラムの並列性と並列・分散化
1
並列処理による処理速度向上
• ひとつのプログラムをタスク（集合）に分割
タスクを複数プロセッシングエレメント(PE)で同時実行
処理速度向上（＝実行時間短縮）を目指す
PE0
PE0
PE1
2
並列処理による処理速度向上
• 速度向上率
プログラムを分割してn個のPEで並列実行
– T1：１個のPEでの『逐次』実行時間
– Tn：n個のPEでの『並列』実行時間
速度向上率（Speed-up ratio）
S=T1/Tn
• 並列処理効率（PE利用率）
e=S/n
• 理想的な並列処理では次のようになる
S=n
e=1
linear speed-up
3
並列処理による処理速度向上
• 速度向上率のグラフ
速度向上率 S
スーパーリニアスピードアップ
リニアスピードアップ
飽和
PE数 n
• リニアスピードアップが得られない原因
– 並列化可能部分の割合(並列化率)が低い，並列性が低い
– 通信/同期のオーバーヘッド
– PEの負荷の不均衡
4
並列化率とAmdahl’s law
• 並列処理による速度向上の限界を示す法則
• 並列化可能部分と不可能(逐次処理)部分の比を
p:(1-p)
p：並列化率≦1
とする
• 並列化可能部分の並列処理効率e=1であっても，
速度向上率Sは:
S=T1／{ T1*(1-p) + T1*p/n}
S=1／{ (1-p) + p/n}
• PEを無数に用いても逐次処理部分（1-p）が残る限り
S=n（リニアスピードアップ）とならない
5
並列処理のオーバーヘッド
• 通信や同期のオーバーヘッドによる並列処理効率低下
• 同期オーバーヘッドの影響の単純な例
–
–
–
–
–
プログラムを処理時間 t のn個のタスクに分割
PE数もn個
同期のために各タスクの処理の後にtsyn時間必要だとする
逐次処理時間：T1=nt
並列処理時間：Tn=t+ntsyn
S=nt／(t+ntsyn)
S=n／{1+n(tsyn/t)}
tsyn＞0である限り
S＝nとならない
t
tsyn
1
2
3
・・・
n
6
並列処理のオーバーヘッド
• S=n/{1+n(tsyn/t)}を大きくしnに近づけるには
• tsyn/t を小さくする
– tsynは小さいほど良いがハードやシステムによって決まる
– tを大きくするために分割数 n を小さくすると並列度が下が
ってしまう
• 最適な n は?
• tsynは一定，プログラム全体の
処理時間をT=nt とする
S=n/{1+(tsyn/T)n2}
t
1
• Sを最大にするn>0は
n=√(T/tsyn)
tsyn
2
3
・・・
n
7
並列処理のオーバーヘッド
• S=n/{1+ (tsyn/T)n2}
• Sを最大にするnは n=√(T/tsyn)
• 単に分割数nを大きくすればよいというわけではない
18
・並列処理粒度の問題
16
14
12
s10
8
6
tsyn/T=0.001
4
t
2
1
2
3
・・・
n
0
0
20
40
60
n
80
100
120
S=n／{1+(tsyn/T)n2} のグラフ tsyn
8
処理の分割配置
• 並列処理単位(タスク)の大きさ：粒度(granularity)
• 高い並列処理効果を得るには
⇒粒度の適切な選択が重要
– 粒度が細かいと並列性は高くなる
⇒オーバーヘッドが顕著
– 粒度が粗いと並列性が低くなる
⇒PE資源を有効に利用できない
9
処理の分割配置
• PEへの処理の分割配置が不適当
⇒PEの負荷が不均等⇒並列処理効率の低下
PE0
PE1
PE2
t
PE0
PE数の倍数に
タスク分割するか
PE1
PE2
t
10
処理の分割配置
• PEへの処理の分割配置が不適当
⇒PEの負荷が不均等⇒並列処理効率の低下
PE0
PE1
PE2
t
PE0
タスクをさらに
細かく分割する
PE1
PE2
t
11
処理の分割配置
• PEへの処理の分割配置が不適当
⇒PEの負荷が不均等⇒並列処理効率の低下
PE0
均等に分割できるとは
かぎらない
PE1
PE2
t
PE0
割り当て方を工夫する
スケジューリング問題
PE1
PE2
t
12
並列処理による性能向上
• 並列処理を有効なものとするには：
–
–
–
–
–
問題からたくさん並列性を引き出す
タスクサイズを最適な粒度に設定する
上手にスケジューリング（負荷分散）する
並列処理オーバーヘッドの低いH/WおよびS/W
etc.
13
プログラムの並列化
• プログラムの並列化
1)プログラムからの並列性の抽出
(a)プログラムのタスクへの分割
(b)並列性の検出
(c)並列性向上のためのプログラムリストラク
チャリング
2)タスクスケジューリング(PE負荷の均一化)
(a)タスクのPEの割り当て
(b)データ転送の最小化･効率化
(c)同期の最小化･効率化
3)コード生成
14
タスク
• タスク：
PEへ割り当てる処理の単位
プログラムを分割しタスクを生成
（ひとつのタスクは中断なしに実行される）
• 分割の視点（演算 or 変数）：
データ並列（分散メモリ型コンピュータ）
vs
制御並列/機能並列/タスク並列
15
タスク粒度
• タスク粒度：タスクの大きさ
• 高い並列処理効果のためには適切な粒度選択が重要
– 細粒度(Fine grain):ひとつの文，演算，命令
– 中粒度(Medium grain)：ループのイタレーション
– 粗粒度(Coarse grain):基本ブロック，ループ，サブルーチン
• 粒度が細かいほど負荷均等が期待できる
⇒通信や同期，割り当ての処理が増える
• 通信や同期が少なくなるような分割が望ましい
領域分割（データ並列）
16
基本ブロック
• 基本ブロック：
「始めからしか入ることができず,一度入ると停止した
り分岐したりすることなく(ただし基本ブロックの終わり
は除く)順番に実行される連続した文の列」
a=b+1
c=a*10
if (c<>0) goto lbl
d=20/c
e=d*3.14
lbl:d=20*c
17
制御フローグラフ
• 制御フローグラフ
– 基本ブロックをノードとする
– ノード間の制御の流れを有向グラフで表現
a=b+1
c=a*10
if (c<>0) goto lbl
d=20/c
e=d*3.14
lbl:d=20*c
• 制御フロー解析により得られる
18
制御フローグラフ
• ノードB1からノードB2へ制御が移る可能性がある場合:
– B1はB2の(直接の)先行ブロック(predecessor)
– B2はB1の(直接の)後続ブロック(successor)
a=b+1
c=a*10
if (c<>0) goto lbl
d=20/c
e=d*3.14
lbl:d=20*c
19
ループのイタレーション
• ループのイタレーション：
do i=1,20
a(i)=a(i)*10
b(i)=b(i)+c(i)
enddo
a(1)=a(1)*10
b(1)=b(1)+c(1)
a(2)=a(2)*10
b(2)=b(2)+c(2)
・
・
a(20)=a(20)*10
b(20)=b(20)+c(20)
20
ループ
• ループのフローグラフ：
i=1
lh:if (i>20)goto ex
a(i)=a(i)*10
b(i)=b(i)+c(i)
i=i+1
goto lh
ex:...
21
ループ
• ループのフローグラフ(定型ループの場合の省略形)：
do i=1,20
a(i)=a(i)*10
b(i)=b(i)+c(i)
enddo
22
ループ
• ループとは
– フローグラフ内の閉路
• 自然なループ(ナチュラルループ)：
– 並列化・最適化の対象とするループ
– 次の性質を満たすノードとそのノード間のエッジの集合
強連結されたノード：
ループ内の任意のノードからループ内の他の全てのノー
ドへ行く長さ１以上の経路がある
唯一の入口ノードを持つ：
入口はループ内のノード
ループ外からループ内のノードへは入口ノード通過しな
いと到達できない
23
ループ
• 自然なループではない閉路の例
• 自然なループの検出：
「支配」の概念を用いて「逆向きエッジ」を求める
24
ループ
• 制御フローグラフ上での自然なループの検出
• 支配：
開始ノードからノードnへの全経路がノードdを含む場合，
dはnを支配しているという．
(各ノードは自ノードを支配しているとする)
• 逆向エッジ(バックエッジ)：
頭部ノードが尾部ノードを支配しているエッジ
• ループ：
逆向エッジn→dに対し，dを通らずにnに到達可能な
ノード(nを含む)の集合(dを含む)がループを構成する
ノード
25
ループ
1
入口ノード
ループ
{7,8,10}
{4,7,...}
2
3
4
5
4は7を支配，7→4はBE
6
7
8
9
4を通らずに7に到達可能
なノード{?}
バックエッジ
10
26
ループ
1
入口ノード
ループ
{7,8,10}
{4,5,6,7,8,10}
2
3
4
5
6
7
4を通らずに7に到達可能
なノード{5,6,7,8,10}
8
9
10
27
並列性( タスク間の並列性)
• 並列性
プログラムには結果を得る上で本質的ではない記述
上の順序関係が存在
– 例)タスクT3とT4は実行順序の入替え可能．
同時実行も可能 ⇒並列性がある．
T1:
T2:
T3:
T4:
T5:
A=50
ひとつの代入文=タスク
B=A*10
C=B*2
T10: S=S+a(1)
D=D+B
T11: S=S+a(2)
E=D+C
(注)入れ替え可能でも必ずしも同時実行可能とは限らない
28
並列性検出
• 並列性検出：
– タスク間で並列実行可能なものの検出
– 正しい結果を得るのに必要無い記述上の順序関係を除去
⇒必要最小限の順序制約(先行制約)を求める
– 先行制約はタスクグラフなどによって表現される
T1
T2
T3
タスクグラフ
T4
T5
T1:
T2:
T3:
T4:
T5:
A=50
B=A*10
C=B*2
D=D+B
E=D+C
29
データ依存
• 全タスクが実行されるタスク集合の場合：
(条件分岐が存在しないプログラム)
タスク間のデータ依存関係による先行制約
30
データ依存
• データ依存：
逐次実行ではタスクTaはTbより先に実行されるとする
TbはTaに対して：
– フロー依存：Taで定義された変数の値をTbで使用
– 逆依存：Taで使用される変数にTbで定義
Ta: A=...
– 出力依存：Taで定義された変数にTbでも定義
•変数の使用 = X
if (Y>0)
A(I)=
•変数の定義 Z=
Ta: =A
Tb: A=...
=A..
Ta:
Tb: A=..
Tb: A=...
31
データ依存
• 例)どのようなフロー依存があるか？
T1:
T2:
T3:
T4:
T5:
A=50
B=A*10
C=B*2
A=A+B
B=A+2
T2はT1にフロー依存
T3はT2にフロー依存
T4はT1とT2にフロー依存
T5はT4にフロー依存
T1にはフロー依存してい
ないことに注意
• データ依存の検出方法については後述
32
データ依存
• 例)どのような逆依存があるか？
T1:
T2:
T3:
T4:
T5:
A=50
B=A*10
C=B*2
A=A+B
B=A+2
T4はT2に逆依存
T5はT3に逆依存
33
データ依存
• 例)どのような出力依存があるか？
T1:
T2:
T3:
T4:
T5:
A=50
B=A*10
C=B*2
A=A+B
B=A+2
T4はT1に出力依存
T5はT2に出力依存
34
データ依存
• 例)全てまとめると
T1:
T2:
T3:
T4:
T5:
A=50
B=A*10
C=B*2
A=A+B
B=A+2
T1
フロー依存
逆依存
T2
出力依存
T3
データ依存グラフ
T4
T5
• 逆依存と出力依存：「みせかけの依存」
新しい変数を用いて意味を変えずに除去できる
• フロー依存：「真の依存」
35
データ依存
• 例)ループの場合は少々複雑
do i=2,n
a(i)=a(i-1)+b(i)
enddo
a(2)=a(1)+b(2)
a(3)=a(2)+b(3)
a(4)=a(3)+b(4)
a(5)=a(4)+b(5)
.
.
T
データ依存グラフ
データ依存がイタレーショ
ン間にまたがる
36
制御依存
• 実行するタスクが実行時に決定するタスク集合の場合
(条件分岐が存在するプログラム)
タスク間のデータ依存＋制御依存関係による先行制約
• タスクTbがタスクTaに制御依存している：
Taの実行結果によりTbを実行することが決定する
• 「あるタスクを実行することが決定する」
と
「実行するか否かを決定する」
は，違うことに注意
37
制御依存
• 例) if (i>1)
then a(i)=a(i-1)+b(i)
else a(i)=0
endif
if
then else
制御フローグラフ
• if の評価が完了しないとthenもしくはelseを実行する
ことが確定しない．
→ thenおよびelseはifの評価の後でないと実行でき
ないという意味でifに依存している．
• 一般にはif-then-elseの(実行するか否かを決定する)
38
ように簡単ではない．
制御依存
• 逆支配
フローグラフ上でTaからに出口タスク
に至るには必ずTbを通る場合
「TbはTaを逆支配している」
という．
(注)TaからTbに至る経路上の全タス
クはTbに逆支配されている
Ta
Tb
出口
39
制御依存
• 制御依存
フローグラフ上のタスクTxとTyにおい
て
T1
Tx
– TxからTyへ至る経路上で，その経路上
の全タスク(除くTx,Ty)をTyが逆支配する
パスが存在し，
– TxはTyに逆支配されていない，
場合またその場合に限りTyはTxに制
御依存している
Ty
出口
40
制御依存
• Tx(if1)からTy(T2)に至るパスのひとつ
「if1→T1→T2」上の全てのタスク{T1}は
T2に逆支配されている
if1はT2に逆支配されていない
• よってT2はif1に制御依存している
• 同様にT2はif2にも制御依存している
if1
T1
if2
T2
41
制御依存
if1
T1
T2
if1
if2
T3
T4
if1
if2
if2
T1 T2
データ依存 T4
(制御)フローグラフ
T3
制御依存グラフ
T1 T2
T3
T4
プログラム依存グラフ
42
データ依存解析 ud連鎖解析
• データフロー解析(使用定義連鎖(ud連鎖)解析)
文Sで使用される変数Aの値はどの文で定義されうる
のか(フロー依存)を求める
T1: A=50
– 変数の使用
T2: B=A*10
=X
T3: C=B*2
if (Y>0)
A(I)=
T4: A=A+B
– 変数の定義
T5: B=A+2
Z=
• 右の例は基本ブロック内だけなので簡単
基本ブロックにまたがる解析は複雑
• 逆依存・出力依存も同様の問題として扱える
43
データ依存解析
• 基本ブロックにまたがるデータ依存
複数個所に依存することもある
a=b+1
c=a*10
if (c<>0) goto lbl
a=20/c
e=d*3.14
lbl:d=20*a
44
データ依存解析地点
• プログラム中の点(地点)とは文の直前または直後
• フローグラフ上で文Sでの変数Aへの定義が点pへ到達
するとは，Sからpへの経路があり，他のいかなるAの
定義もその経路上に存在しないこと
a=b+1
c=a*10
if (c<>0) goto lbl
a=20/c
e=d*3.14
lbl:d=20*a
45
データ依存解析の方法
• ud連鎖を求める
1. 各文の定義に番号付けをする
2. 各変数についてその変数への全ての定義の集合を作る
(とりあえず配列変数は除く)
3. 各基本ブロックBiについて次の集合を求める
– GEN[Bi]
Biの最後の文の直後の点に到達するBi内にある定義からなる
集合(各変数のBi内での最後の定義)
– KILL[Bi]
Bi内で定義されている変数と同じ変数に定義をしているBi外に
ある定義の集合
46
データ依存解析の方法
4. 基本ブロックBiに対して以下の集合を計算する
– IN[Bi]
Biの最初の文の直前の点に到達している全ての定義からな
る集合
– OUT[Bi]
Bの最後の文の直後の点に到達する定義からなる集合
5. ブロックBi内の変数Aを使用する文uに対する定義は
① 文uより前にBi内でAの定義があるならば
→直近の定義がuに到達するAの唯一の定義
② 文uより前にBi内でのAの定義が無ければ，
→IN[B]のAの定義がuに到達するAの定義（複数ありうる）
47
データ依存解析例
in[1]={}
1
1:a=b+1
gen[1]={1,2}
2:c=a*10
kill[1]={4}
3:if (c<>0) goto lbl
out[1]={1,2}
in[2]={1,2}
2 4:a=20/c
gen[2]={4,5}
5:e=d*3.14 kill[2]={1}
out[2]={2,4,5} in[3]={1,2,4,5}
3 6:lbl:d=20*a gen[3]={6}
kill[3]={}
48
データ依存解析データフロー方程式
• INとOUTに関するデータフロー方程式
全てのBiに対して
Biの先行ブロックBip
(1) IN[Bi] =
∪
OUT[Bip]
(2) OUT[Bi] = (IN[Bi]–KILL[Bi])∪GEN[Bi]
• データフロー方程式の最小解が存在しそれを求めるア
ルゴリズム(反復解法)も知られている
49
データ依存解析アルゴリズム
入力：KILL[Bi], GEN[Bi]
初期化：全てのBiに対してIN[Bi]=φ, OUT[Bi]=GEN[Bi]
change=true;
while change {
change=false;
for Bi {
Biの先行ブロックBip
new_in =
∪
OUT[Bip];
if new_in<>IN[Bi] change=true;
IN[Bi]=new_in;
OUT[Bi] = (IN[Bi]–KILL[Bi])∪GEN[Bi];
}
}
50
ループのデータ依存解析
• イタレーション間でのデータ依存関係の有無の判定
⇒異なるイタレーションでの配列変数への定義と使用が
同じ添字の値をとりうるか否かの検査
do i=2,n
a(i)=a(i-1)+b(i)
enddo
do i1=2,n
do i2=1,i1
a(3*i1+2*i2, 2*i2)= ...
...= a(i1-i2+6, i1+i2)
enddo
enddo
51
ループのデータ依存解析データ依存システム
• データ依存システム：
do i1=2,n
do i2=1,i1
a(3*i1+2*i2, 2*i2)= ...
...= a(i1-i2+6, i1+i2)
依存方程式
3*i1d+2*i2d = i1u-i2u+6
2*i2d = i1u+i2u
依存不等式
2≦i1d≦100
1≦i2d≦i1d
2≦i1u≦100
2≦i2u≦i1u
• データ依存検査：依存方程式と依存不等式を同時に満
52
たす整数解が存在するか否かの検査
データ依存システムの解法
• 依存システム
Ai＝c
Bi≦b
• 前提
– 配列添字式はループ制御変数の線形式
– ループ制御変数の上限・下限は外側ループ制御変数の線形式
• 解法
–
–
–
–
GCDテスト
Power test
Omega test
etc...
53
データ依存システムの解法
• 前処理：ループ制御変数の正規化
do I1=2,100
do I2=1,I1
A(3*I1+2*I2, 2*I2) =
= A(i1-I2+6, I1+I2)
enddo
enddo
do I1=0,98
do I2=0,I1+1
A(3*I1+2*I2+8, 2*I2+2) =
= A(i1-I2+7, I1+I2+3)
enddo
enddo
54
データ依存システムの解法の例：Power test
1. 一般化GCDテスト
– 依存方程式中のn個の変数iをrank(A)個の変数tに置換
(依存システムの自由度を縮小)
– t に対し整数解の存在の可能性を検討
2. 依存方程式に整数解が存在しうるなら
3. Fourier-Motzkin の消去法
– 代入により依存不等式をt を用いて表現
– これに対し変数消去を施しt の存在領域の有無を判定
55

Download Report