MPIを用いた並列計算 情報論理工学研究室 07-1-037-0065清水周
構成 研究背景 並列計算機 MPI(Message Passing Interface) 研究方法 -過去の円周率計算結果 結果 -過去の円周率計算結果 結果 考察及び今後の課題
研究背景 一度に扱うデータの量の増大 処理の高速化の要求 ネットワーク環境の充実 並列計算機を用いた並列処理 計算機の性能は向上し続けており、ハードディスクの記憶容量なども増加し続けている。 計算機の性能向上に伴い、一度に扱うデータの量は増大して来ている。 計算機が扱うデータ量は今後も増大していき、 膨大なデータに対する処理の高速化の方法として、 複数のプロセッサを持つ並列計算機(Parallel Computer)を用いた 並列処理(Parallel Processing)が注目されている。 計算機自体の性能の向上は近い将来頭打ちになることが予想される。
並列計算機 利点 処理の分散 故障に強い 欠点 高価 通信時間の発生 処理の分散 故障に強い 欠点 高価 通信時間の発生 並列計算機は高価であるため以下で説明するソフトを用いネットワークを利用した仮想並列計算機を用います。
仮想並列計算機 複数の計算機 ネットワーク接続 安価 MPI(Message Passing Interface) PVM(Parallel Virtual Machine) OpenMP Score 無料で提供されている仮想並列計算機を構築するソフトウェアとしては、MPI(Message Passing Interface)[1], PVM(Parallel Virtual Machine)[4], OpenMP[5], Score[6]等がある。以下に、これらについての説明をする。 MPI(Message Passing Interface)[1]は世界標準とされている分散メモリ型並列処理におけるメッセージ交換のためのライブラリである。 このライブラリの基本はメッセージパッシング (message passing)であり、 あるプロセスから他のプロセスへデータを明示的に送る方法で、 極めて効率の良い並列プログラムを書くことができる。 PVM(Parallel Virtual Machine)[4]は並列計算を行うためのソフトウェアである。 PVMはアメリカのオークリッジ国立研究所のメンバーが中心となって開発され、 動作するマシンの種類が多いのが特徴である。 PVMソフトウェアシステムの構成は、デーモンとルーチンライブラリの大きく2つに分けられる。 OpenMP[5]は並列コンピューティング環境を利用するために用いられる標準化された基盤である。 OpenMPの利点としては、移項のたやすさ、移植性の高さ、単一プロセッサ環境との共存の容易さが挙げられる。 Scoreは[6]は経済産業省が設立した超並列処理研究推進委員会である新情報処理開発機構(Real World Computing Partnership, RWCP)にて 開発されたLinux用クラスタ計算機用超並列プログラム実行環境である。 主に流体行動解析、量子化学計算、物理学計算等の科学技術計算分野で使用されている。 今回は世界標準とされ、最も主流の方式であるメッセージパッシングを利用したMPIを使用する。
-MPI(Message Passing Interface) ・世界標準 ・メッセージパッシング ・移植性が高い
研究方法 1台から3台の計算機 円周率の計算 実行時間を計測 本研究では、異なるスペックをもつ計算機3台をネットワークで繋ぎMPI環境を構築する。本研究で使用する計算機のスペックを表 2に示す。 本研究では、計算機3台を100Base-TXによるLAN接続し、MPI環境の構築を行った。図 1に本研究で用いたLANの構成図を示す。
研究方法-スペック 本研究で使用した計算機のスペック スペック OS プロセッサ メモリ(GB) 計算機 WindowsVista スペック OS プロセッサ メモリ(GB) 計算機 WindowsVista Intel®Core™2DUO CPU L7300 1.40GHz RAM 1.00 Windows XP Intel®Core™2CPU 6300 1.86 GHz RAM 2.00 Vista Intel®Core™i5CPU750 2.67 GHz RAM 4.00
-過去の円周率計算結果(1) 円に外接および内接する多角形の周の長さ (紀元前3世紀) 無限級数和・無限乗積が発見(14世紀) 計算機を用いないπ計算結果の例 氏名 年 計算桁 求め方 アルキメデス 前3世紀 2 円に接する正96角形の周の長さ ルドルフ= フォン=コーエン 17世紀 70 正262角形 の周の長さ ジョンマチン 1706 100 Machinの公式と Gregory-Leibniz級数 円周率の計算は古来より様々な方法が考えられてきた。 数学が発達する以前には、円に外接および内接する多角形の周の長さから円周率の近似値を得ていた。紀元前3世紀に古代ギリシアの数学者Archimedes (前287-前212)は円に接する正96角形の周の長さから、円周率を小数点以下2桁まで求めた。 14世紀には円周率が無限級数和や無限乗積として表されることが判明する。 20世紀後半からは計算機により円周率を計算できるようになった。
-過去の円周率計算結果(2) 20世紀には計算機による円周率計算が実現 円周率の計算は計算機の性能評価の指標 計算機によるπ計算結果の例 氏名 年・月 計算桁 使用機種 リトワイズナー等 1949 2,037 ENIAC 高橋,金田 1999.9 206,158,430,000 HITACHI SR8000と128 台の演算機(並列計算) 近藤茂とアレクサンダー・イー 2010.8 5兆 自作PC
研究方法-計算アルゴリズム MPI用円周率プログラムを作成し計算 -数値積分 -モンテカルロ法 並列処理環境を実現するためにMPI(Message Passing Interface)[1]を用いる。 MPIを用いた理由は、世界標準とされている分散メモリ型並列処理におけるメッセージ交換のためのライブラリであり どんな計算機でも動くからである。 フリーであらゆるアーキテクチュアをサポートしているMPICH[7]というソフトウェアが存在することも理由として挙げられる。 円周率の計算は計算機の性能評価の指標となっている。 11
研究方法-数値積分 n個の長方形の 面積の足し合わせ MPIにおいて 3台の計算機で n/3個の長方形の 面積を求め、合計 この式は他の式のような積分を必要とせず、簡単な四則演算で計算できるものであったため使用した。この式で求められる値Sはシグマの総和計算により求められた半径1の円の面積であり円周率の近似値となる。 小数点第6桁目
研究方法-モンテカルロ法 半径1の円の面積 n個のランダムな点 距離1以下の k個の点 π = 4 × k/n MPIにおいて 分散し計算、 合計し面積をだす モンテカルロ法とは乱数を用いたシミュレーションを何度も行うことにより近似解を求める計算手法である。 円周率をモンテカルロ法で求める場合、1辺の長さが2の正方形の中からランダムに1点を選択し(ランダムなx座標をy座標の組を求め)、その座標の正方形の中心からの距離が1以下であるかどうかを判断する。ランダムに設定したn個の点のうち、正方形の中心からの距離が1以下のものがk個だった場合、円の面積は π = 4 × k/n と求められる。 小数点第3桁目
結果 MPIによる計算時間と計算台数の関係 モンテカルロ法において短縮化を実現 アルゴリズム 数値積分(6桁) モンテカルロ法(3桁) PC アルゴリズム 数値積分(6桁) モンテカルロ法(3桁) PC (台数) 1 0.000096 6.612981 2 0.000215 3.875726 3 0.000597 3.516391 MPI上で円周率を計算した時の計算時間を表 3に示す。 表 3より、プログラムBの処理時間は計算機台数の増加に伴い時間短縮が見られたことから、 MPIによる並列計算の有用性を示せている。 しかし、プログラムAの処理時間は計算機台数の増加に伴い逆に処理時間が延びていることが示される。 処理時間が延びてしまった事については、計算機台数を増やしたことにより計算機間の通信が増えたためと考えられる。 また、本研究で得られた結果は、有効桁数が非常に少ないため、検証として用いるには有効桁数を上げる必要がある。 有効桁数を向上させるには、プログラムAについては、積分範囲をもっと広げればさらに桁数が上げられると思われる。 プログラムBについては、乱数により生成される点の数を増やせば桁数が増えると思われる。 (m秒)
考察及び今後の課題 並列計算機による高速化 数値積分による方法での高速化失敗 原因:通信時間 並列計算機の有効性を示した 原因:通信時間 並列計算機の有効性を示した 入力を増やし有効桁数の増加が必要 -内部計算の増加 プログラムBの処理時間は計算機台数の増加に伴い時間短縮が見られたことから、MPIによる並列計算の有用性を示せている。しかし、プログラムAの処理時間は計算機台数の増加に伴い逆に処理時間が延びていることが示される。処理時間が延びてしまった事については、計算機台数を増やしたことにより計算機間の通信が増えたためと考えられる。 また、本研究で得られた結果は、有効桁数が非常に少ないため、検証として用いるには有効桁数を上げる必要がある。有効桁数を向上させるには、プログラムAについては、積分範囲をもっと広げればさらに桁数が上げられると思われる。プログラムBについては、乱数により生成される点の数を増やせば桁数が増えると思われる。 本研究ではMPIの有効性を検証するために、MPIを用いて円周率の計算を行った。しかしながら、本研究の結果からはMPIの有用性が少なくともプログラムBでは示せた。Aの場合、積分範囲が小さすぎ通信時間の方が大きくなり、また性能の違った複数台のPCを利用したため計測が遅くなったのではないかと思われる。MPIに適した並列処理を行えるようにアルゴリズムを改良し、処理速度のより一層の向上を得ることが今後の課題である。