で解析可能である. CKYアルゴリ
ズムは高速なCFG構文解析アルゴリズムであるが, それでも多くの時間を要す
るため, 効率の良い並列アルゴリズムの開発は重要である. そして構文解析は
複雑な記号処理であるため, 論理型言語やそれを並列にした並行論理型言語な
どの応用問題としても良い題材となっていた. しかしながら, 並列処理という
観点からはこれまで良い結果は得られていない. たとえば, ICOTで開発された
PAX
[5]
という並列CFGパーザは, 32台のプロセッサ使用時
に, 台数効果は1.5〜2倍に留まっている
[4].
また, 16台と32台
でほとんど計算時間が変わっておらず, これ以上増えた時に大きく性能向上で
きるかどうかは疑わしい.
我々は今回ABCL/fの応用問題として, CKYアルゴリズムの並列化を試みた. 台 数効果は256台で実行時に, 同じアルゴリズムをC++で書いたものの場合の10倍 程度である(平均語長119.4の5文, allocatorはABCL/fと同じものを使用). ま た, 同じABCL/fと比較した場合には30倍程度になっている. また, 同じ例題 に対して, 256台で実行時に, 128台での実行時間に比べて, ほぼ2倍の性能を 得ており, これ以上の台数の増加に対してもまだ性能向上が見込める可能性が 高い.