MPIによる並列計算
情報論理工学研究室
07-1-037-0142
廣岡 佑介
本発表の流れ
１．目的
２．並列処理
３．仮想並列計算機
４．MPI
５．最小全域木問題
６．検証方法
７．結果
８．結論及び考察
目的と検証方法

目的
仮想並列計算機の性能を検証

検証方法
最小全域木問題を並列処理で行い処理時
間の向上率の検証
並列処理
ある一つの処理を複数のプロセッサを用いて行うこと
 利点
データや機能を分割処理出来る
故障に強い
 欠点
通信時間の発生
並列計算機は高価である
仮想並列計算機



安価で並列計算機の構築ができる
容易に並列処理ができる
PVM,MPI,OpenMPなど
MPI（Message Passing Interface)
分散メモリ型並列計算機を構築
世界標準を目的に作成
 移植性が高い
 サポートするプログラム言語が多い

最小全域木問題
重み付無向グラフ
閉路を持たない
辺の重みの総和が最小
検証方法
最小全域木問題を並列処理
毎回ランダムに重み付き無向グラフを作成
頂点数を５、１０、２０、４０、８０、１６０と変化
試行回数１０回の平均
 使用PCは５台
１台から５台まで順に構築
OSはWindowsに統一

解法アルゴリズム

プリムアルゴリズム

クラスカルアルゴリズム

ソリンズアルゴリズム
仮想並列計算機の構成図
計算機一覧
内部処理時間
全体の処理時間
結論及び考察
本研究ではMPIによる最小全域木問題を検証した


結論
内部処理時間の向上
全体の処理時間の増加
今後の課題
ネットワーク環境の向上
通信を考慮したアルゴリズムを作成