並列アルゴリズムについての調査報告情報論理工学研究室０７－１－０３７－０２５１太田尚吾本発表の流れ         本研究の目的並列処理仮想並列処理 MPI(Message Passing Interface) 最小全域木問題(Minimum Spaning Tree) Sollinアルゴリズム検証方法・結果結論本研究の目的 MPI (Message Passing Interface)を用いてグラフ問題である最小全域木問題を解き、仮想並列計算での処理の有用性を検証する。並列処理ある一つの処理を複数のプロセッサで行うこと  メリット・データや処理を分割できる・故障に強い  デメリット・複数のプロセッサが必要である・通信時間が発生する仮想並列処理ネットワークを利用し、複数の計算機を並列計算機として利用できる     安価で並列計算機の構築ができる容易に並列処理ができる VPNやMPI,OpenMPなどがある本研究ではMPIを使用する MPI(Message Passing Interface)     世界標準を目的に作成されたAPIの規格移植性が高い様々な言語がサポートされている異機種間での通信が考慮されていない最小全域木(Minimum Spaning Tree:MST)問題 Sollinのアルゴリズム v2 4 5 v1 2 v5 4 3 v4 2 2 3 v3 v6 6 Sollinのアルゴリズム v2 4 5 v1 2 v5 4 3 v4 2 2 3 v3 v6 6 Sollinのアルゴリズム v2 4 5 v1 2 v5 4 3 v4 2 2 3 v3 v6 6 Sollinのアルゴリズム v2 2 v5 v1 3 v4 2 3 v3 2 v6 検証方法・結果  計算機４台を用いて、頂点数 10,20,30,40,80,160の重み付無向グラフに対して、その最小全域木をそれぞれ1,2,3,4 台の計算機で解き、実行時間を測定する検証方法・結果処理時間時間(m秒) 0.002750 0.002500 0.002250 0.002000 頂点数 0.001750 10 0.001500 20 30 0.001250 40 80 0.001000 160 0.000750 0.000500 0.000250 0.000000 1 2 計算機数 3 4 検証方法・結果全体処理時間 12.000 11.000 10.000 頂点数 9.000 8.000 10 時間 (m 秒 ) 7.000 20 6.000 30 5.000 40 4.000 80 3.000 160 2.000 1.000 0.000 1 2 3 計算機数 4 結論・今後の課題     並列処理によって内部処理の時間を短縮することができた通信に時間がかかるため、全体の処理時間は長くなってしまった。通信環境の向上通信を考慮したアルゴリズムの使用