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回）  今回使用した機器メインPC サブPC1 サブPC２サブPC３サブPC４ OS Windows Vista Windows Vista Windows Vista Windows XP Windows Vista CPU Core2 1.4GHz Core2 1.4GHz Core2 1.4GHz Pentium 1.6GHz Core2 1.4GHz Memory 1GB 1GB 1GB 512MB 1GB 結果（内部計算時間） 0.003 内部 0.0025 計算 0.002 時 0.0015 間 ( 頂点5 頂点10 頂点20 頂点40 頂点80 頂点160 0.001 m 秒 0.0005 ) 0 1台 2台 3台 4台計算機数 5台結果（合計の処理時間） 14.000 12.000 処理 10.000 時間 8.000 ( 頂点5 頂点10 頂点20 頂点40 頂点80 頂点160 6.000 m 秒 4.000 ) 2.000 0.000 １台２台３台４台計算機数５台結論本研究では、MPIによる最小全域木を解く時間の計測をした  通信の事を考慮したプログラムが必要  処理能力が大きく劣る計算機は並列計算には有効でない