動的に再構成可能なコンピュータ・ネットワーク環境を考慮した並列分枝限定法

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

昨年度開発したPVMを利用して動的に計算機の追加/削除を許すEnvironment Managerの配下で,分枝限定法の評価計算を行うSolverを動的に追加/削除できる並列・分散型分枝限定法の実装をPUBB(Parallelization Utility for Branch-and-Bound algorithms)に行った.ただし,実行時に生成される子問題数等の定量的な評価実験は今後の課題となった.本年度は,独自に並列分枝限定法を実行できる環境を持つべく,PCクラスタを構成した.PCクラスタは、Pentiume II 400MHz, 256Mバイトメモリをを持つPC21台を100baseスイッチにより接続した構成である.構成したPCクラスタ環境上でPUBBの性能評価を行った.ワークステーション・クラスタを利用して行ってきた数値実験結果との比較により,PCクラスタ環境がPUBBを利用した並列分枝限定法の実行環境として,極めて高い性能を示すことを確認した.動的に再構成可能な環境での実行性能を定量的に測定するためには,実行時に暫定解の更新が,数回は行われる問題の解法を利用した方が良い,そのため,一般混合整数計画問題の解法の実装を考えている.また,一般混合整数計画問題を,計算機構成を固定した環境と動的に変更した環境で解き,比較することで性能評価を行いたい.また,本年度はWEBを利用した並列・分散分枝限定法のプロトタイプの実装を行った.こちらは,実装そのものがまだ不十分ではあるが,今後の開発に対するノウハウを得ることができた.