MPIを用いたグラフの並列計算 情報論理工学研究室 07-1-037-0213 藤本 涼一
あらまし 目的・方法 並列処理 仮想並列計算機 MPI 計算方法 結果・考察 結論
目的・方法 目的 仮想並列計算機の性能を実験的評価 方法 最小全域木問題を並列処理にて解き、計算にかかった時間を比較する
並列処理(Parallel Processing) ある一つの処理を複数のプロセッサを用いて行うこと メリット 処理時間の短縮が可能 デメリット 計算量が増えるにつれて大量のプロセッサが必要になる
仮想並列計算機 安価で並列計算機が実現できる 容易に並列処理ができる →主な仮想並列計算機としてMPI,PVM,OpenMP等がある
MPI(Message Passing Interface) メッセージ通信ライブラリ 並列計算機を実装するための標準化された規格 言語を問わず利用できる →主な実装としてMPICH,LAM,OpenMPI
MPICH Argonne国立研究所が開発 無償で配布されているライブラリ 移植性を重視 現在では後継のMPICH2がある
最小全域木問題 重み付無向グラフ が与えられたとき、G の全域木のうち、辺の重みの和が最小になるグラフT を求める
最小全域木の探索方法
検証内容 毎回ランダムに重み付き無向グラフGを作成 頂点数は5,10,20,40,80,160の場合を検証 それぞれの頂点数に１から5台の計算機で処理時間を測定（試行回数10回）
今回使用した機器 OS CPU 1GB 512MB メインPC サブPC1 サブPC２ サブPC３ サブPC４ Core2 1.4GHz Windows Vista XP CPU Core2 1.4GHz Pentium 1.6GHz Memory 1GB 512MB
結果（内部計算時間）
結果（合計の処理時間）
結論 通信の事を考慮したプログラムが必要 処理能力が大きく劣る計算機は並列計算には有効でない 本研究では、MPIによる最小全域木を解く時間の計測をした 通信の事を考慮したプログラムが必要 処理能力が大きく劣る計算機は並列計算には有効でない