目次目次

ＭＰＩによる並列計算 ＭＰＩによる並列計算

並列計算理論研究室

穂積　剛文

目次 目次



並列処理 (Parallel Processing)



仮想並列計算機



MPI (Message Passing Interface)



目的



最小全域木問題



Sollin’s

Algorithm



結果・考察

並列処理 並列処理

(Parallel Processing) (Parallel Processing)

処理時間の短縮 データの分割

機能の分割　　　　

様々な分野での活躍

仮想並列計算機 仮想並列計算機

・ネットワークを利用し、複数のコンピュータを 並列計算機として用いることができる

・安価で並列計算機の構築ができる

・簡単に並列処理ができる

ＭＰＩ ＭＰＩ

無料の通信ライブラリのソフトウェア 世界標準を目的に作成された API の規 格

プログラムの移植性が高い

目的 目的

本研究では、家庭用の計算機を複

数台ネットワーク接続しＭＰＩを

用いた並列計算処理での有用性を

検証する。

最小全域木問題

最小全域木問題

Sollin’s Algorithm Sollin’s Algorithm

 6

　 　　　　 2 3

　 　　　　　　　 7 5

　 　　　　　　　v 4 1

v 2

v 4 v

3 v

5

Sollin’s Algorithm Sollin’s Algorithm

 6

　 　　　　 2 3

　 　　　　　　　 7 5

　 　　　　　　　v 4 1

v 2

v 4 v

3 v

5

検証方法 検証方法

最小全域木問題を Sollin’s Algorithm を使用して解き速度を検証する。

頂点数 10,20,30,40,80,160

計算機は１から 4 台の計算機を使用する

OS は WindowsXP で統一

計測結果 計測結果

　内部計算時間と計算機数の関係

全体の処理時間と計算機数の関

全体の処理時間と計算機数の関

係 係

考察 考察



本研究では、 MPI による最小全域木 問題の検証をした。

•

MPI による並列化によって内部処理計 算時間短縮は可能となった



しかし全体の速度は計算機が増えるほ ど時間がかかっていた



つまり各ＰＣ間の通信速度の処理に時

間がかかったといえる。

結論 結論

MPI による並列化によって内部処理計算 時間向上可能

しかし実用化のためには、通信速度向上

のために 通信環境の向上通信に負担のかからない

プログラムなどが必要といえる。