整合ラベリング問題における併合解法の並列化について

概要

論文の詳細を見る
This paper deals with the parallelization of algorithms to solve consistent labeling problems, abbreviated as CLPs, which are NP-complete combinatorial search problems of finding totally consistent combinations of local interpretations. After surveying a merge method for CLPs proposed by us before, we introduce two types of parallelization having different granularities of parallelism each other : the structure-level one and the merge-level one. The efficiency of each parallelization is evaluated by experiments run actually on a multi-processor computer. The merge-level parallelization is proved to be always very effective. However, the structure-level parallelization is not necessarily efficient, sometimes, even rather harmful to cause serious inefficiency of computational time. The reason is explained by using a concrete example.
社団法人人工知能学会の論文
1991-01-01