並列化困難問題の並列性に関する研究

本研究では,並列化困難とされている問題群に対して,実用的な並列アルゴリズムの提案を目指し研究に取り組んでいる.平成16年度に関しては,以下のような成果を得た.1 一般問題の並列性の評価を行なうシステムの実現平成15年度までの研究において,いくつかの並列化困難問題に適した並列アルゴリズムの提案を行ない,また,そのアルゴリズムを実際の計算機クラスタ上で実装することにより,効果的な並列処理が可能であることを示した.この結果を元に,一般的な問題に対する並列性の評価尺度を提案した.提案した評価尺度は有効性,評価容易性等の条件を満たしており,並列化困難な問題に対するアルゴリズム制作の指標として活用することが可能であった.また,自動的に問題の並列性を評価するシステムを作成し,多くの並列化困難問題に対して,問題の持つ並列性の評価を行った.2 グリッド環境における並列化困難問題に対する並列アルゴリズムの実装と評価平成15年度までに提案した並列アルゴリズムを拡張し,地理的に離れた複数のクラスタを用いたグリッド環境に実装することにより,大規模なグリッド環境におけるアルゴリズムの実用性を示した.これまでの計算機クラスタ環境とは異なり,グリッド環境では様々な計算資源(通信遅延,通信路帯域制限,CPUの性能等)の差異が大きい.したがって,実際のグリッド環境に実装を行う時点で,実際の並列化のコストを正確に見積もった上で開発を行うことが必要であった.本研究については,グリッド上での基本操作である完全交換について一般的には効率的に実行できない"致命的な通信行列"というものが存在することを示し,この通信行列に対してタスク分割を行なうことにより効率よく処理を実行するアルゴリズムを提案した.

本研究では,並列化困難とされている問題群に対して,実用的な並列アルゴリズムの提案を目指し研究に取り組んでいる.平成16年度に関しては,以下のような成果を得た.1 一般問題の並列性の評価を行なうシステムの実現平成15年度までの研究において,いくつかの並列化困難問題に適した並列アルゴリズムの提案を行ない,また,そのアルゴリズムを実際の計算機クラスタ上で実装することにより,効果的な並列処理が可能であることを示した.この結果を元に,一般的な問題に対する並列性の評価尺度を提案した.提案した評価尺度は有効性,評価容易性等の条件を満たしており,並列化困難な問題に対するアルゴリズム制作の指標として活用することが可能であった.また,自動的に問題の並列性を評価するシステムを作成し,多くの並列化困難問題に対して,問題の持つ並列性の評価を行った.2 グリッド環境における並列化困難問題に対する並列アルゴリズムの実装と評価平成15年度までに提案した並列アルゴリズムを拡張し,地理的に離れた複数のクラスタを用いたグリッド環境に実装することにより,大規模なグリッド環境におけるアルゴリズムの実用性を示した.これまでの計算機クラスタ環境とは異なり,グリッド環境では様々な計算資源(通信遅延,通信路帯域制限,CPUの性能等)の差異が大きい.したがって,実際のグリッド環境に実装を行う時点で,実際の並列化のコストを正確に見積もった上で開発を行うことが必要であった.本研究については,グリッド上での基本操作である完全交換について一般的には効率的に実行できない"致命的な通信行列"というものが存在することを示し,この通信行列に対してタスク分割を行なうことにより効率よく処理を実行するアルゴリズムを提案した.