MPIを用いた並列処理情報論理工学研究室 06‐1‐037‐0246 杉所拓也あらまし並列処理  仮想並列計算機  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による最小全域木問題を検証した     内部処理の高速化に並列処理は有効である全体の高速化に並列処理は通信を考慮しなければ有効だとは言えないデータ送信時に、計算機のスペックごとにデータの振り分けを考慮する必要がある通信を考慮したプログラミングが必要である