MPI を用いた 並列処理
情報論理工学研究室 杉所 拓也
あらまし
並列処理
仮想並列計算機
MPI(Message Passing Interface)
最小全域木問題
計測方法
結果・考察
並列処理
対象問題に複数の計算機を用いる
処理時間の短縮（利点）
データ分割手法
並列計算機は高価（欠点）
仮想並列計算機の使用
仮想並列計算機
仮想並列計算機の利点
安価で並列計算機が構築できる
無料提供されているソフトウェア 一般的な PC を用いて並列可能
並列化が容易
計算機をネットワーク接続することで並列化 仮想並列計算機として MPI 、 PVM 、 OpenMP がある
MPI
(Message Passing Interface)
世界標準を目的に作成
並列計算におけるプログラムを記述する ための規約を設けるために開発
様々な通信関数が実装されている
プロトコルの障害を考慮しなくて良い
最小全域木問題
重み付無向グラフ
各頂点間の辺に重みがついている 各辺に向きがない
最小全域木
辺の重みの総和が最小なもの 閉路がない
最小全域木問題の例
MPI
の性能を検証する対象問題最小全域木問題
→ 最小全域木問題を解く並列アルゴリズム
→Sollin のアルゴリズムを使用
→MPI 上でプログラミング
検証方法
重み付無向グラフを使用
頂点数： 5 ・ 10 ・ 20 ・ 40 ・ 80 ・ 160
使用計算機台数は 5 台
1 台から 5 台まで順増やしていく
計算機は Windows Vista 、 Windows XP を用いる 計測はそれぞれ 10 回行い、平均値を用いる
仮想並列計算機の構成
内部処理時間と計算機台数の関係
全体の処理時間と計算機台数の関 係
結論
本研究では MPI による最小全域木問題を検証した
内部処理の高速化に並列処理は有効である
全体の高速化に並列処理は通信を考慮しなけれ ば有効だとは言えない
データ送信時に、計算機のスペックごとにデー タの振り分けを考慮する必要がある
通信を考慮したプログラミングが必要である
