P完全な問題の並列化に関する研究

点击翻译按钮获取中文摘要

本研究では,並列化困難とされているP完全問題に対して,実用的な並列アルゴリズムの提案を目指し研究に取り組んでいる.平成13年度は以下の様な成果を得た.(1)P完全問題に対するコスト最適な並列アルゴリズムの提案平成12年度に提案を行った並列性を表す指標を用いて,凸層問題,可視層問題,スタックを用いた幅優先探索,といったP完全問題について漸近的に効率のよい並列アルゴリズムの提案を行った.これらのアルゴリズムは,時間計算量と使用プロセッサ数の積が逐次処理の時間計算量と等しいコスト最適なアルゴリズムとなっており,これらのP完全問題については理論的に最適な並列アルゴリズムが存在することを証明した.また,これらのアルゴリズムを複数台のPCを用いたクラスタ並列処理環境に実装し,アルゴリズムの実用的な高速化を検証する実験を行った.実験より,実用的にもクラスタ並列処理においてこれらのアルゴリズムが効率よく実行できることを示した.(2)並列性を表す新たな指標の提案とその評価平成12年度の研究により,P完全であることが証明されていないいくつかの問題について本質的な逐次性が存在し,並列化が困難であることが予測された.本年度の研究においては,これらの問題について,その並列性を示す指標の提案を行った.また,その指標を用いて,パティエンスソート,安定結婚問題といった並列化困難問題に対するコスト最適な並列アルゴリズムの提案を行った.また,その並列性の指標に基づいた並列計算モデルのシミュレータの設計,製作を行った.