バに用いたPE数である．従って、Originalではクライアントのプロセッサを除くPE数、
FTPではサイトを構成するPE数に等しい．
230000 1.3e+06 3.2e+06 9e+06 2.5e+07 1.3e+08
1 2 3 4 5 6 7 8 9 10 11 12 13 14
Execution Time (micro sec)
PE 8 Queen
FTS (type 3)
FTS (type 1) FTS (type 2)
Original (type 3)
Original (type 1) Original (type 2)
図10.15: 8 Queenプログラム（並列実行における処理性能変化）
図10.15は、各プログラムの並列実行結果を示す．Originalのtype-1とtyp e-2は、予想
現れている．typ e-3は通信量が多いことから、やはり並列化による効果が得られなかった．
これらに対してFTSは、差があるがどれも並列効果が現れている．Originalで近い動作の
typ e-1とtyp e-2も、FTSでは差がでてきている．
40 500 1000 20000 50000 150000 300000
1 2 3 4 5 6 7 8 9 10 11121314
Number of messages
PE
8 Queen (Messages)
FTS (type 3) FTS (type 1) FTS (type 2)
Original (type 3)
Original (type 2)
Original (type 1)
図10.16: 8 Queenプログラム（並列実行におけるメッセージ数）
図10.16は、それぞれの実行時のメッセージ数を示す．Originalの1PEの実行で、type-1
からtyp e-2、typ e-3のメッセージ数が増えているのは、ホストプロセッサとの通信である．
typ e-1はバッチ転送モードが効き易いように、解の生成が行われたと思われる．Original
のtyp e-1、typ e-2とも通信量が少なく負荷バランスしやすいことから、十分に並列効果が
現れている．typ e-3は、通信量が多く台数効果が得にくくなっている．FTS(typ e-2)は負
荷分散が均等化し易く、うまく台数効果が得られている．
第9章での考察から、実験結果を元に各値を算出してみたところ、表10.2のような値と なった．ORとFRは、それぞれOriginalプログラムと耐故障プログラムの1PEでの実行 時間に相当する．
3 4 5 6 7 14 16 18 20 40 90
1 2 3 4 5 6 7 8 9 10 11 12 13 14
Performance Ratio of FTS to Original
PE
type 1
type 2
ideal line for type 1,2
type 3 ideal line for type 3
図10.17: 8Queenプログラム（並列実行における処理時間比）
メッセージ処理時間は、ベンチマークと同じくM =260secとした．mは2PEでのメッ セージ数から1PEでのメッセージ数を減算したものであり、PE1でのメッセージ数はバッ チ転送が効かない場合をとった．これによると、type-3は >1であり並列実行に適さな いことが分かる．typ e-1,typ e2について、第9章の考察を元にして予測処理時間比を算出す
表10.2: 応用プログラムの 並列因子
OR FR =FR=OR m =mM=O R
typ e-1,typ e-2 1:3210 6
2:5210 7
19:2 2000 0.4
typ e-3 同上 1:32108 102 19500 3.9
ると、PE台数Nに対して
19:2+0:4(N 01)
1+0:4(N 01)
(N 1)
となる．この予測値および、実測による処理時間比を示したものが図10.17である．比較 的うまく負荷分散したtyp e-2の8PE以下であっても、予測と大きくはずれている．耐故 障実行では、プロセッサ間のゴール転送処理が大きくなったため、ゴール転送が多いと予 測とずれる可能性があるが、typ e-2、type-1ともゴール転送は高々8回でしかない． 一方、
ゴール転送の多いtyp e-3もプロットしてみると、予測とほぼ一致していることがわかる．
よってこの差は、負荷分散方式の相違が大きく影響していると思われる．なおtyp e-3は、
上で示したように並列プログラムとしては不適であり、性能向上が良く見えるのは元のプ ログラムに並列効果が出ないせいである．
10.5
実験結果に関する考察
ベンチマークプログラムによる実験結果から、単体プロセッサでの耐故障プログラムの 実行については、予測性能とかなり近い値を得た．基本性能の測定結果から、メッセージ 処理とリダクション処理時間比M=R = 80〜160 であり、非決定性が決定性の0.01%以下 でないと単体での性能は得難いことがわかる．
本研究で提案する手法は、メッセージ処理性能が落ちるほどユーザプログラムに占める 非決定性の割合が性能に大きく影響する．ShenらによるInstantReplayの研究では、いく つかのベンチマークプログラムに対して静的解析を行った結果が発表されている[13]．こ れによれば、100述語以下の小規模なプログラムではほとんど非決定性を持つ述語はなく、
200述語程度のプログラムで全体の5〜6%という結果が報告されている．しかし、大規模 なプログラムについての調査は行われておらず、また実際に非決定的部分の動作する割合 についても分かっていない．
しかしプログラムの並列度が高ければ、耐故障化によって単一PEサイトで10倍になっ たとしても、うまく負荷分散さえすれば並列実行によって大きく軽減されることも第9章 で示した．これは、元のプログラムが十分に並列性が高く、メッセージ処理がある程度あ る場合で、かつ並列効果が得られることを仮定している．しかし負荷一定でプロセッサ数 を増やした図10.13の実験結果を見ても、それほど速度向上していない．これは、ベンチ マークプログラムのように、並列性がかなり高いプログラムでもコミュニケーションが少 ないためであろうと考えられる．図10.10のように、プロセッサ数に応じて処理負荷を増や した場合でも、一定の時間がほぼ保存されるだけで比率は縮まらない．
8Queenプログラムは、純粋な非決定的実行部分は少ないが、決定的実行であっても非決
定的実行を含む場合ログを発生させるため、実質的なログ量の全体に占める割合は大きい．
実測によると45121リダクションのうち、33069リダクションでログを発生する（73%）．
このため単一プロセッサでの耐故障化のオーバーヘッドにより処理時間比で20倍近くに なっている．理論的には8PEのサイト構成では、6倍程度まで落ちるものと期待されるが 負荷分散方式の相違からよい比較とはならなかった．
上記ベンチマークプログラムを対象にして、プログラム実行中にプライマリサイトの1 プロセッサを強制的に終了させるプログラムを用意し、実験しによりバックアップが実行 を引き継ぐことも確認した．また8Queenプログラム測定中に、メモリ不足を起こして処 理系で例外を起こした際にも解を得ることができた．
現在の実装では、監視プロセッサのリング結合ネットワークを利用して単純に隣接プロ セッサへ負荷を分散させているため、元のプログラムの負荷分散方式のように均等に広が らなかった．ユーザの負荷分散方式を反映できるような実装の改良は、今後の課題である．