並列化オーバーヘッド

一般に「並列化オーバーヘッド」というのは, ある処理を実行するのに, 逐次 処理であれば必要ないが, 並列処理をする時には行なわなくてはならない仕事 のうち, CPUが行なうべき仕事を指す. たとえば通信のオーバー ヘッドがそのもっとも顕著な例である. 繰り返しになるが, 通信のオーバーヘッ ドは, 通信を行なうに当たって純粋にCPUが行なわなくてはならない処理を指 し, たとえばネットワークの遅延は含まれない. ネットワークの遅延は, その 遅延の結果生ずるアイドル時間がなければ(つまり, 遅延が隠蔽されていれば), 全体の性能に影響を与えることはない.

並列化オーバーヘッドは, 「全てのプロセッサが100% 稼働していても, 理想 の台数効果が得られない理由」を与える. CKYアルゴリズムにおいては, オー バーヘッドを調べることで, プロセッサ台数に比べて, 処理の量が多い場合 (つまり文の長さが長い場合)の, 性能の「上限」を予測するのに使える.

を計算するのに, および を他のプロセッサから 取り寄せる部分である. これは1台でローカルメモリで実行していればいらな かったはずの処理である. 以下の記号を導入する.

• --与えられた記号の組(s',s'')に対し, なる規則の数.
• C--与えられた記号の組(s',s'')に対し, なるsを求めるのに要する時間.
• G--一つのエッジを生成するのに要する時間.
• S--一つのメッセージを送受信するのにかかる, スタートアップコス ト(送信側, 受信側の和).
• A--メッセージに一つのリスト要素を加えるのにかかる時間.

我々のパーザの, AP1000+上の実装においては, Cは2次元配列の参照, Gは 1 cons, Aは, 1 cons程度の処理である. 一方, Sは, 詳しく計測していな いが, 1000命令以上はかかる処理である.

上を用いて, を通信オーバーヘッド零のプロセッサ(逐次プロセッ サの近似)で求めるための処理量 を, 以下で近似する.

最初の2項が, 要素を取り寄せるために必要な通信のコスト, 残りがローカル な処理のコストである. 取り出された要素, は, 各 に対し, なるsの集合を, コストCで求め, 取り出された 要素 に対し, エッジを生成する. 本来はこの上にさらに, sがすでに生成されて いるかどうかの検査のコストが必要になるが, 省略してある. その検査はロー カルな処理であり, それを0と見積もることは我々の並列処理のオーバーヘッ ド(通信コスト)を大きく評価することになる.

このアルゴリズムでオーバーヘッドを減らすために重要なことは, 通信オーバー ヘッドが式全体の外に出ているということである. たとえば上で, , の要素数をそれぞれn, mとし, が平均でaである とすると,

となる. このうち前2項が通信オーバーヘッドとなり, n + mのオーダー, 一 方ローカルな処理は, nmのオーダとなる.