MGTP の OR 並列化に関して、N 逐次方式と呼ぶ方式を考案し実装した[1]。 この方式は、多数生成されるタスクを高々 PE 数に応じた 固定数 N までの範囲で並行実行させることを基本としている。 各 PE では次々に生成されるタスクをスタックに保持し、 これが空になるまで逐次化して実行することに専念する。 タスクスタックが空となった PE からのタスク分配要求があるとき、 マスタープロセスが仲介してタスク分配を offer している PE を選び、 そのスタック基部(最上部でない)からタスクの提供を受けてこれを分け与える。
まず、PIM/m 上で本方式の評価実験を行った。 試験例題 (TPTP中のSYN009-1) において、 従来方式では約 2 万回発生していたタスク割当回数が 100 回程度にまで削減され証明時間が短縮されるなど、顕著な効果を確認した。 また、128 PE までの並列実行において良好な台数効果が得られている。
次に、共有メモリ型の汎用並列機 Cray SuperServer6400 (20 PE) を用いた実験を行った。 従来の循環割付け方式ではタスクの爆発的生成によりオーバヘッドが著しく増大し、 1 PE での逐次実行にすら劣る。 これに対し、N逐次方式では効果的に負荷分散が行われることが確認された。 試行ごとに負荷分散状況にかなり大きなバラツキがあるものの、 数回の試行中最良の場合だけを見れば、比較的良好な台数効果が認められる。
(b)N-sequential method
図 1: Snapshot of ``xamonitor'' on PIM/m (128 PE)
