MPI を用いたグラフ の並列計算

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

Vista

Windows Vista

Windows Vista

Windows XP

Windows Vista

CPU

1.4GHz Core2

1.4GHz Core2

1.4GHz Pentium 1.6GHz

Core2 1.4GHz

Memory

1GB 1GB 1GB 512MB 1GB

結果（内部計算時間）

結果（合計の処理時間）

結論

　 本研究では、 MPI による最小全域木を解く時 間の計測をした

 通信の事を考慮したプログラムが必 要

 処理能力が大きく劣る計算機は並列

計算には有効でない