MPIを用いたグラフの並列計算処理情報論理工学研究室 07-1-037-0198 川﨑直紀目次 並列処理 仮想並列計算機 目的 MPI (Message Passing Interface) MPICH 検証方法 結果・考察 結論・今後の課題並列処理並列処理とはある一つの処理を複数のプロセッサを用いて行うこと  処理速度の向上 • データの分割 • 機能の分割  メリット  処理時間が短縮できる  デメリット  計算量が増加につれてプロセッサが多く必要  専用の並列計算機は高価仮想並列計算機 (Parallel Virtual Computer) クラスタ(Cluster)処理  主な実装、MPI,PVM,OpenMP等目的 目的 MPIを用いた並列計算の有用性を検証 方法 1台の計算機の所要時間比較複数台で並列処理した場合の所要時間 →どの程度処理時間短縮できるかを計測 MPI(Message Passing Interface) 世界標準を目的に作成されたAPIの規格 メリットライブラリレベルでの並列化であるため、言語を問わず利用できる  プログラマが細密なチューニングを行える デメリット  デッドロックの対処などの問題  ファイアウォールの問題  ＭＰＩＣＨ Argonne国立研究所が開発 無償でソースコードを配布したライブラリ 移植しやすさを重視した作りになっている 2005 年にはMPICH の後継としてMPICH2 が開発された最小全域木問題 重み付無向グラフG が与えられたとき、G の最小全域木T を求める問題 Sollinのアルゴリズムを使用検証方法  最小全域木問題 • 毎回ランダムに重み付きグラフＧが作成 • 頂点数は5,10,20,40,80,160 • 1から5台の計算機で処理時間を測定 • 試行回数10回仮想並列計算機の構成図使用した各計算機の性能ホストPC サブPC1 サブPC2 サブPC3 サブPC4 Windows Windows Windows Windows Windows OS Vista Vista Vista XP Vista CPU Core2 1.4GHz Core2 1.4GHz Core2 1.4GHz Pentium 1.6GHz Core2 1.4GHz RAM 1GB 1GB 1GB 512MB 1GB 内部計算時間と計算機数の関係内部計算時間 m秒 0.00275 0.00250 0.00225 0.00200 0.00175 0.00150 0.00125 0.00100 0.00075 0.00050 0.00025 0.00000 1台 2台 3台 4台 5台計算機数頂点 5 頂点 10 頂点 20 頂点 40 頂点 80 頂点 160 全体の処理時間と計算機数の関係処理時間 m秒 13.000 12.000 11.000 10.000 9.000 8.000 7.000 6.000 5.000 4.000 3.000 2.000 1.000 0.000 １台頂点 5 頂点 10 頂点 20 頂点 40 頂点 80 頂点 160 ２台３台計算機数４台５台結果・考察 内部計算時間：処理速度向上 全体の処理時間：処理速度低下  原因は通信結論・今後の課題 Sollin のアルゴリズムは、通信について一切考慮されていない →通信を考慮したプログラムを作成する 通信環境を整備 CPU の性能差を考慮して、負荷分散