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