MPIによる並列計算

MPIによる並列計算
並列計算理論研究室
07-1-037-0138
穂積 剛文
目次







並列処理(Parallel Processing)
仮想並列計算機
MPI (Message Passing Interface)
目的
最小全域木問題
Sollin’s Algorithm
結果・考察
並列処理
(Parallel Processing)
処理時間の短縮
データの分割
機能の分割
様々な分野での活躍
仮想並列計算機
・ネットワークを利用し、複数のコンピュータを
並列計算機として用いることができる
・安価で並列計算機の構築ができる
・簡単に並列処理ができる
MPI
無料の通信ライブラリのソフトウェア
世界標準を目的に作成されたAPIの規
格
プログラムの移植性が高い
目的
本研究では、家庭用の計算機を複
数台ネットワーク接続しMPIを
用いた並列計算処理での有用性を
検証する。
最小全域木問題
Sollin’s Algorithm

6
v2
2
v3
3
7
v1
4
5
v4
v5
Sollin’s Algorithm

6
v2
2
v3
3
7
v1
4
5
v4
v5
検証方法
最小全域木問題をSollin’s Algorithm
を使用して解き速度を検証する。
頂点数10,20,30,40,80,160
計算機は1から4台の計算機を使用する
OSはWindowsXPで統一
計測結果
0.003
0.0025
0.002
頂点10
頂点20
頂点30
0.0015
頂点40
頂点80
0.001
頂点160
0.0005
0
1台
2台
3台
4台
(m秒)
内部計算時間と計算機数の関係
全体の処理時間と計算機数の関
係
14
12
10
頂点10
8
頂点20
頂点30
頂点40
6
頂点80
頂点160
4
2
0
1台
2台
3台
4台
考察
本研究では、MPIによる最小全域木問
題の検証をした。
• MPIによる並列化によって内部処理計
算時間短縮は可能となった
 しかし全体の速度は計算機が増えるほ
ど時間がかかっていた
 つまり各PC間の通信速度の処理に時
間がかかったといえる。

結論
MPIによる並列化によって内部処理計算時
間向上可能
しかし実用化のためには、通信速度向上
のために
通信環境の向上通信に負担のかからない
プログラムなどが必要といえる。