DCPDCP DCP
9.2 実行オーバーヘッド の見積り
9.2.2 マルチプロセッサでの実行見積り
PSG、BSGが複数プロセッサから構成される場合の耐故障プログラムの実行効率を見積 もる．耐故障化する前のプログラムを、同じプロセッサ数からなるマルチプロセッサ上で 実行した場合との処理時間の比較によって実行効率を表す．
ここで、
N : PSGを構成する要素プロセッサ数
O : 単一プロセッサで実行する際の元のプログラムの仕事量
F : 単一プロセッサで実行する際の耐故障プログラムの仕事量
PSG/BSGのコミュニケーションも含む．
とする．
アムダールの法則によれば、Oの並列化可能部分率pとして、N台で並列実行する場合に は最大負荷のプロセッサの仕事量がpO =N+(10p)Oになる[20]．しかしこの値にはプロセッ サ間の通信は考慮されていない．N分割することによって他のプロセッサ上へ分散されたプ ロセスとプロセッサ間コミュニケーションが必要な場合、プロセッサ内の単位処理時間をR、 プロセッサ間メッセージ処理時間M、メッセージ数mとするとき、負荷バランスが均衡した として並列実行による処理時間は、通信遅延を無視して(pO=N+(10p)O)R+mM (N >1)
となる．よって並列処理をして意味がある、すなわち効果が得られるためには、
1
N
(pO =N +(10p)O)R+mM
OR
<1
であることが必要十分である．これから、0NmM <(N 01)pOR を得る．
0
B
B
B
B
@
1
N
p
N
+10p+ mM
O R
<1
0(10p)(10 1
N )
mM
OR
<p(10 1
N )
0 mM
O R
<
p(N01)
N
1
C
C
C
C
A
すなわちNが十分大きいとすれば、mM=OR<p1より、プロセッサあたりのメッセー ジ処理時間mMは、単一プロセッサでの処理時間OR すなわちマルチプロセッサシステム 全体で処理しようとする仕事の単体での処理時間よりも小さくなければならない．
ここで改めて
R : 平均リダクション処理時間
M : 平均メッセージ処理時間
m : Oを並列化することで生じるメッセージ数 とすると、
TP
nor mal
=
p
N
+(10p)
OR+mM
が並列化した元のプログラムの実行時間である．
元のプログラム自身のコミュニケーション量は耐故障化しても変わらないものとし、ま た仕事の分散とともに、PSG/BSGのコミュニケーションも分散されるとする．よって、耐 故障プログラムの実行時間は、上と同様に
TP
fts
=
p
N
+(10p)
FR+mM
となる．ここで、
: 耐故障化によって増える仕事量比率（F =2O ）
: 潜在するコミュニケーション量の元のプログラムに対する比率（m=2O）
: メッセージ処理とリダクション処理の処理時間比（M =2R） とすると、処理時間比は、
TP
fts
TP
nor mal
=
p
N
+(10p)
FR+mM
p
N
+(10p)
OR+mM
=
(p+(10p)N)+N
(p+(10p)N)+N
となる．
並列プログラムは本質的に並列性が高いものと考えて、並列化部分率を p ' 1として、
2をx軸にとって、 = 10固定でN =10〜10000の場合をプロットしたのが図9.3で ある．すなわち、耐故障化することでユーザプログラムは単体で10倍の仕事量に増えた
として、10台から10000台規模のプロセッサで耐故障実行させた場合に相当する．なお並
列プログラムが意味を持つ条件 0 NmM <(N 01)pO R は、 N
N01
<p 1であるの で、0 1の範囲だけ意味を持つ．ここで(= mM
OR
)は、並列化することで生じる
メッセージの処理時間とプログラムを単体プロセッサで逐次実行した場合の処理時間の比 である．
これを見ると、システム規模が大きくなるほどは任意にとっても、性能低下しない．
システム規模が100台程度であれば0:1< 1でなければ2倍以上の実行時間となって しまう．従って本方式は大規模並列計算機であるほど有効であり、その性能は、メッセー ジ量とその処理時間、プロセッサ内の処理量と処理時間の比に依存する．
1 2 3 4 5 6 7 8 9 10
0.001 0.01 0.1 0.2 0.5 1
Performance Ratio of FTP to Original
beta * gamma
The Estimated Overhead on MPP
10 PE 100 PE 1000 PE 10000 PE
図9.3: マルチプロセッサでの推定オーバーヘッド(p=1)
図9.3のグラフは並列化部分率p=1として得たものだが、一般にはp<1であり、その 値に応じて図 のような曲線を描く．なおこのとき、 でのみ、並列プログラ
ムとして意味がある．これを見ると、並列度が低い(p<< 1)プログラムの場合、も小 さくなり、急激に処理時間比が悪化することが分かる．図9.3(p =1)の =0:01のよう に1000PEで2倍程度であったはずの処理時間比も、p=9になると9倍程度になる．pが
1に近いところの変化を見るために、図9.4を0:99p 1;0:01 0:1の範囲で、
軸を対数軸としてグラフを描き直したものが図9.5である．これを見ても並列度がかなり高 く(p! 1)ないと、性能を向上が期待できないことが分かる．メッセージ処理効率が上昇 するか、あるいはメッセージ数が減少して処理時間mMが小さいプログラムの場合には、
が減少することから、やはりプログラムの並列性の高さがより支配的になる．これはサ イトを構成するプロセッサ数が大きくなるほど顕著である．
The Ideal Overhead on MPP (alpha = 10)
10000 PE
0.1
0.5
0.9 1 0.1
0.5
1 1
5 6 7 8 9 10
p
beta * gamma 1000 PE
100 PE 10 PE
Performance Ration of FTP to Original
図 9.4: マルチプロセッサでの推定オーバーヘッド (0:1<p<1)