オーバーヘッドに関する比較

文献 [4]の結果を見ると, プロセッサ数32台, 単語数107の ように, 十分な単語数がある場合でも, 台数効果は1.5倍〜2倍程度にとどまっ ている. 同論文によるとこれは「通信が頻繁でアイドル時間が頻発するからで ある」, と推測されている.

オーバーヘッドに関する解析を, 5.6.5節と同様に試みると 次のようになる. まず前提として, 改良版PAXと同様, 集合 には記号その ものが挿入されるとする. また, という形の プロセスは一つしか生成されないものとする. つまり, 我々のパーザ同様重複した記号の 除去を行なっているものとする. また, プロセス切替えのオーバーヘッドを零 とする. その上で5.6.5節同様以下の記号を導入する.

• C--与えられたs', s''に対して, なるs を求めるコスト
• G--エッジを一つ, ローカルに生成するコスト
• S--メッセージを送受信するスタートアップオーバーヘッド
• A--メッセージに一つの記号を含ませるための処理.
• -- なる規則の数.

すると, から を求める部分の処理量は以下の ようになる.

つまり, の各要素s'が, 各 ( によって処理され, その中ではまず なるs が求められ, それぞれについてエッジがローカルに生成された後, に挿 入されるために通信が起こる.

ここで重要なことは, メッセージ送信のスタートアップのコストSが各生成 されたエッジごとにかかってきてしまう点である. 非常に大雑把な見積もり として, を平均して, 2, S = 10G = 20C程度と仮定すると, 1プ ロセッサ上での合計処理量に比べ, 複数プロセッサ上での合計処理量は, 約,

倍もの量になり, 32台で高々6.4倍程度の性能向上しか見込めない. これはプ ロセス切替のオーバーヘッドを無視した見積もりであり, 実際には複数プロセッ サ実行時の方がプロセス切替のオーバーヘッドも増え, さらに性能は悪化する ものと予想される.

つまり, ABCL/fで書かれた我々のCKYアルゴリズムとPAXとを比べてもっとも 大きく違う点は, 我々のCKYではある集合 を求めるのに, および が完全に求まってから, 処理を開始しているのに対 し, PAXにおいては, 処理系によるmessageのaggregationが行なわれない限り, に要素を一つ挿入するごとに通信が起こる点である. 結果として, 我々 の方式では を求める際に, 2回の通信ですみ, さらに, ひとたび および が求まってしまえば, 途中で(データが生成されて いないことによる)スレッドの中断が起こることはない. 一方, PAXでは, は, 多数のプロセッサが部分構造を徐々に求めていくという形式で徐々 に求まり, (処理系によるaggregationがなければ)1要素求まるごとに通信が起 きる. さらに, を読み出すプロセスは, その一部分の要素が求まり次第 処理を開始するので, 一旦 の処理が始まってからも の1要素ごとに 中断が起こる可能性がある. もちろんこれは理論的にはKL1処理系の最適化に よって改善可能な点ではあり, そのような研究もすでになされているが [6], の要素が求まった時に, 通信をどれだけ遅れ せて良いかの解析は容易ではない. ABCL/fの処理系では現時点においても などをリストとして他のプロセッサに送る際には, 全ての要素をコ ピーすることを保証しているので, 5.6.5節で述べたよう なオーバーヘッドの削減が達成されている.