DCPDCP DCP
9.1 実行オーバーヘッド の分類
実行オーバーヘッドは、プログラムから静的に見積もれるものと、動作させた時に発生 し得る動的なものがある．静的なオーバヘッドにより、プログラムに沿って単一プロセッ サ上で間断なく動作する際の実行時間を見積もることができる．別プロセスの並行動作、
別プロセッサからの非同期なメッセージ送信等の予測困難な動作は動的なオーバヘッドと なって観察するプロセスの実行に影響を与える．動的なオーバヘッドについては見積りは 困難であるが、考察することで静的解析からの値と実測値との差を埋める助けとなる．
9.1.1
静的オーバーヘッド
変換後のプログラム構造から、静的にオーバーヘッドを考察する．変換によって以下の 処理が、すべてのプログラムに追加される．
1. 監視プロセスのネットワークを構成させる．
2. ゴールの複製を作る．
3. PSG、BSGへゴールを転送する．
監視プロセスを各プロセッサ上で起動させる際には、次のような処理が行われる．
1. PSG、BSGのノードを決定する．
2. ホストノードからPSG、BSGの各プロセッサへゴールを送出する．
3. 送出されたゴールは、各プロセッサ上からホストノードへ返信を送る．
4. 返信を送って来たプロセッサどうしをリングネットワークに接続する．
この際、明示的には各プロセッサとホストノードとの間に、3回のコミュニケーションが 必要である．ゴールの複製については、実際に複製されるデータ量に比例した処理オーバ ヘッドがある．
第8.1.1節 で述べたように、FTRecV、FTRepVのプログラムでは次の処理が追加される．
FTRecVに追加された処理 :
1. 入力処理: 直前の非決定的実行に対する、返信の待ち合わせが追加される．
2. 部分処理: 条件分岐が非決定的であるならば、分岐情報をログとして送る処理 が追加される．
静的には、抽象マシン語レベルで数命令〜10命令程度での増加が見込まれる．十分 大きな述語定義であれば全体として数%〜10%程度の増加である．プロセッサ間メッ セージの送受信処理を伴うため、メッセージ処理オーバーヘッドを考慮する必要があ る．なお決定的述語については、ほとんど元のプログラムと同じである．
FTRepVに追加された処理 :
1. 割り込み処理: 監視プロセスからの割り込みをチェックする処理が追加される．
2. 入力処理: 非決定的実行に対する、ログの待ち合わせが追加される．
3. 部分処理: ログに対する返信を送る処理が追加される．
入力処理以下については、FTRecVと同様で10命令程度にすぎないが、割り込み処 理に1リダクション追加される．また、入力処理と部分処理についても、プロセッサ 間メッセージ処理を考慮する必要がある．
9.1.2
動的オーバーヘッド
耐故障プログラムの実行時には、次のようなオーバーヘッドが考えられる．
1. 監視プロセスに関する処理
(a) 故障検出
故障検出のためには、監視プロセス間でのメッセージ交換が必要である．監視 プロセスは物理的に別プロセッサ上で動作するため、メッセージ処理を考慮し なければならない．PSGでのメッセージ転送は、PSGのリングネットワークを
1周する分と、最後にBSGの監視プロセスへの1 メッセージ転送が含まれる．
よってサイトを構成するプロセッサ個数＋１個分のメッセージ処理が必要であ る．故障検出は、一定サイクルごとにタイマー駆動で発生する．もちろん故障 検出サイクルを長くとるほど全体のオーバーヘッドは減少する．
(b) サイト内ゴール転送
ゴール転送は監視プロセスを介して行われるため、ユーザのゴールプロセスか ら監視プロセスへの通知がプロセッサ内で起こり、プロセスチェンジした監視 プロセスの1リダクションが必要になる．
(c) 制御ストリームのマージ
監視プロセスへの制御ストリームは、ノード内で実行するすべてのゴールから マージされる．制御ストリームを使わない場合でも、閉じる処理のために少な くとも1 メッセージが監視プロセスへ送られる．監視プロセスへ割り出すこと のない述語であると静的に解析されれば、このオーバーヘッドは軽減される．
ユーザプログラムとの関係では、通常のゴール転送が、
制御ストリームへの制御ストリームへのユニフィケーション 制御ストリーム内でのマージ
監視プロセスのプロセスチェンジ
監視プロセスでのリダクション
監視プロセス間のストリームへのユニファイ
これによって、ゴールはプロセッサ間を一般のデータとして転送される．
2. ホストプロセッサとPSG、BSG間で動的に通信されるデータの複製処理
ホストプロセッサ上のクライアントとPSG、BSG上のサーバプログラムとの通信は、
クライアント側からのデータ転送は複製されてPSG、BSGへと送られ、PSG、BSG 側からの転送は先に来たものをクライアントへと渡す．これら処理はホストプロセッ サ上の複製プロセスが行う．互いに転送されるデータ量に比例したリダクションが複 製プロセスで必要になる．
3. FTRecV とFTRepVとの ログ/返信の転送遅延
転送遅延はプログラムの性質により大きく異る．ログを転送する必要のある非決定的 実行間隔がまばらであれば転送遅延は0になる．逆に頻繁であれば、FTRepVの実 行時間＋ネットワーク転送時間かかる．遅延はログとその返信の転送に関係して発生 する．よって遅延時間は非決定的実行の量に影響される．
4. プロセススイッチ
プロセッサ上の各プロセスは、プロセッサ間メッセージの到着によって動的にプロセ ススイッチする． また監視プロセスへの割り出しも監視プロセスへのトリガーとな る．KLICの実行上はサスペンド、リジュームのコストに含まれる．
5. その他ガーベジコレクション等処理系がバックグラウンドで行う処理
並列論理型言語は動的なメモリ割り付けを許すため、メモリの消費状況によってガー ベジコレクションが発生する．その他処理系がバックグラウンドで動的に行う処理に ついては見積り不可能である．通常では発生頻度が低いと思われるため無視できる が、メモリ消費の激しいプログラムについてはガーベジコレクションの発生回数は大 きく実行性能に影響する．