MPIを用いた並列計算 情報論理工学研究室 07-1-037-0065清水周.

Slides:



Advertisements
Similar presentations
HBSP モデル上での 行列積を求めるアルゴリ ム 情報論理工学 吉岡健太.
Advertisements

専修大学情報科学センターのパソコンを 使ったグリッドコンピューティング ― SPACE計画 - 森正夫 1 、水崎高浩 1 、内藤豊昭 2 、中村友保 2 及び 専修大学情報科学センター 及び 専修大学情報科学センター 1 専修大学 法学部/自然科学研究所 1 専修大学 法学部/自然科学研究所 2 専修大学.
MPIを用いたグラフの並列計算 情報論理工学研究室 藤本 涼一.
3次元nクイーン問題の 解に関する研究 論理工学研究室 伊藤精一
グローバルコンピューティング環境における遺伝的アルゴリズムの検討
第3回 並列計算機のアーキテクチャと 並列処理の実際
CPUとGPUの 性能比較 -行列計算およびN体問題を用いて-
キャッシュ付PRAM上の 並列クィックソートと 並列マージソート
クラスタの構成技術と クラスタによる並列処理
コンピュータプラクティス I 再現性 水野嘉明
LZ圧縮回路の設計とハード・ソフト 最適分割の検討 電子情報デザイン学科 高性能計算研究室 4回生 中山 和也 2009/2/27.
数式処理ソフトウェア のご紹介 株式会社ライトストーン 高橋 直生.
JavaによるCAI学習ソフトウェアの開発
研究集会 「超大規模行列の数理的諸問題とその高速解法」 2007 年 3 月 7 日 完全パイプライン化シフト QR 法による 実対称三重対角行列の 固有値並列計算 宮田 考史  山本 有作  張 紹良   名古屋大学 大学院工学研究科 計算理工学専攻.
PCクラスタにおける2個体分散遺伝的アルゴリズムの高速化
有効数字 有効数字の利用を考える.
円周率 98E13036  平川 芳昭.
AllReduce アルゴリズムによる QR 分解の精度について
神奈川大学大学院工学研究科 電気電子情報工学専攻
遺伝アルゴリズムによる NQueen解法 ~遺伝補修飾を用いた解探索の性能評価~
P,Q比が変更可能なScaLAPACKの コスト見積もり関数の開発
分散遺伝的アルゴリズムによる各種クラスタのベンチマーク
記 憶 管 理(2) オペレーティングシステム 第10回.
各種PC クラスタの性能評価 同志社大学 工学部 廣安 知之 三木 光範 谷村 勇輔.
多数の遊休PC上での 分散ゲーム木探索 導入 ゲーム木探索 ⇒遊休PCを利用して高速化 例)コンピュータ将棋における次手の計算
医療支援診断のためのコンピュータ分散システムの検討
CSP記述によるモデル設計と ツールによる検証
ネットワーク性能に合わせた 分散遺伝的アルゴリズムにおける 最適な移住についての検討
 データベースによる並列処理 情報論理工学研究室  三宅健太.
円 周 率 物 語.
分散処理を用いた大規模ソフトウェアに対するコーディングパターン検出ツール
IPv6アドレスによる RFIDシステム利用方式
MPIによる行列積計算 情報論理工学研究室 渡邉伊織 情報論理工学研究室 渡邉伊織です。
京都大学大学院医学研究科 画像応用治療学・放射線腫瘍学 石原 佳知
OpenMPハードウェア動作合成システムの検証(Ⅰ)
大阪市立大学 学術情報総合センター 大西克実
MPIによるwavからmp3圧縮の検証 情報論理工学研究室 04‐1‐47‐200 木村 惇一.
ソフトを用いた動画の並列変換処理 情報論理工学研究室 中村勇介.
高速剰余算アルゴリズムとそのハードウェア実装についての研究
MPIを用いた最適な分散処理 情報論理工学研究室 角 仁志
コンピュータを知る 1E16M009-1 梅津たくみ 1E16M017-8 小沢あきら 1E16M035-0 柴田かいと
MPIとOpenMPを用いた Nクイーン問題の並列化
Jh NAHI 横田 理央 (東京工業大学) Hierarchical low-rank approximation methods on distributed memory and GPUs 背景  H行列、H2行列、HSS行列などの階層的低ランク近似法はO(N2)の要素を持つ密行列をO(N)の要素を持つ行列に圧縮することができる。圧縮された行列を用いることで、行列積、LU分解、固有値計算をO(NlogN)で行うことができるため、従来密行列の解法が用いられてきた分野では階層的低ランク近似法
実行時情報に基づく OSカーネルのコンフィグ最小化
前回の練習問題.
通信機構合わせた最適化をおこなう並列化ンパイラ
進化的計算手法の並列計算機への実装 三木 光範
オープンソース開発支援のための ソースコード及びメールの履歴対応表示システム
背景 課題 目的 手法 作業 期待 成果 有限体積法による汎用CFDにおける 流体構造連成解析ソルバーの計算効率の検証
同志社大学工学研究科 知的システムデザイン研究室 修士2年 中尾昌広
疑似乱数, モンテカルロ法によるシミュレーション
情報論理工学 研究室 研究テーマ 並列アルゴリズム.
Virtualizing a Multiprocessor Machine on a Network of Computers
社会の情報インフラストラクチャとして、高性能コンピュータおよびネットワークの重要性はますます増大しています。本研究室では、コンピュータおよびネットワークの高速化を狙いとする並列・分散情報処理の科学と技術に関する研究に取り組んでいます。効率のよいシステムの実現を目指して、下記の項目を追求しています。 ◇コンピュータアーキテクチャ.
「マイグレーションを支援する分散集合オブジェクト」
分散処理を用いたコーディングパターン検出ツールの実装
博士たちの愛する円周率 徳山 豪 東北大学 “PI” that professors love
卒業研究 JCSPを用いたプログラム開発  池部理奈.
Jh NAHI 横田 理央 (東京工業大学) Hierarchical low-rank approximation methods on distributed memory and GPUs 背景  H行列、H2行列、HSS行列などの階層的低ランク近似法はO(N2)の要素を持つ密行列をO(N)の要素を持つ行列に圧縮することができる。圧縮された行列を用いることで、行列積、LU分解、固有値計算をO(Nlog2N)で行うことができるため、従来密行列の解法が用いられてきた分野では階層的低ランク近似
BSPモデルを用いた 並列計算の有用性の検証
理工学部情報学科 情報論理工学研究室 延山 周平
円 周 率 物 語.
MPIを用いた並列処理計算 情報論理工学研究室 金久 英之
cp-15. 疑似乱数とシミュレーション (C プログラミング演習,Visual Studio 2019 対応)
情報論理工学 研究室 第1回:並列とは.
統計解析 第11回.
MPIを用いた 並列処理 情報論理工学研究室 06‐1‐037‐0246 杉所 拓也.
分散メモリ型並列計算機上での行列演算の並列化
背景 粒子法(SPH・MPSなど)は大規模流体シミュレーションなどで幅広く利用.一方で,手法の数学的正当化(数値解析)が不十分
ベイジアンネットワークと クラスタリング手法を用いたWeb障害検知システムの開発
Presentation transcript:

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に適した並列処理を行えるようにアルゴリズムを改良し、処理速度のより一層の向上を得ることが今後の課題である。