ノイハウス・ペーター,古瀬蔵,飯田仁
並列効果の高い単一化解析法
Abstract:As effectively programmable parallel architectures become available their usage in natural language processing increases. But an often disregarded problem is the discrepancy between the number of processors required by so-called massively-parallel algorithms and the number of processors
provided by the parallel machine actually at hand.
A parallel parsing algorithm on the basis of the well known CYK algorithm has been published.
We present an efficient, further parallelized version for JPSG-like unification-based grammars and
show the effectiveness of restricting parallelization with regard to the size of the parallel machine
used.
効果的にプログラム可能な並列アーキテクチャが利用できるようになるにつれ、自然言語処理においても並列計算機が使われるようになってきた。しかし、超並列アルゴリズムなどで仮定される理論上のプロセッサの数と、実際に並列計算機で使用可能なプロセッサの数の違いの問題は議論されないことが多かった。本論文では、JPSGのようなユニフィケーションに基づく文法を使って、CYKの並列化アルゴリズムを改良した効率的なパーサを提案し、与えられた並列計算機の並列度に関し、効果的に動作することを示す。