離散最適化手法を用いた並列処理の高速化に関する研究

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

多くの静的負荷分散問題は組合せ最適化としてモデル化できることが知られている。通信時間を考慮した静的負荷分散問題は計算困難なので実用的には単純化されたモデルや近似アルゴリズムを用いる場合が多いが、並列計算機が大規模化し、または分散処理環境の利用により通信遅延時間が支配的になってくると、このような単純化では誤差が大きくなり実行効率が低下する。より一般的な場合に適用できる手法の研究が必要である。筆者は偏微分方程式の並列求解システムNSLを例にとって計算時間と通信時間を考慮した静的負荷分散問題をモデル化し、可能な範囲において分枝限定法を用いて最適解を求め、考案した近似解法の誤差を絶対評価した。特に通信時間が支配的な環境化において、複数プロセッサを利用することにより逆に実行時間が増える状況(過剰な負荷分散)を自動的に検出し回避する手法を検討し評価した。本手法では、計算能力や通信遅延が不均一な分散処理環境において、利用可能な複数のプロセッサの中から適切なプロセッサを適切な数だけ選択し、データと計算を自動的に分割して負荷を分散し、実行時間を短縮することが可能になった。研究の過程で、計算困難問題を実用時間で求解することが必要になったため、計算困難問題の求解を高速化する手法についても検討を進めた。代表的な問題の一つとして部分グラフ同型判定問題(NP完全)を取り上げ、専用計算回路で求解を高速化する研究を行って、現状の計算機に比べ最大20倍程度の高速化が得られることを実証した。専用計算回路を大規模化することにより、更なる高速化も容易であると期待される。