BSPモデルを用いた 並列計算の有用性の検証

Slides:



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

MPIを用いたグラフの並列計算 情報論理工学研究室 藤本 涼一.
グローバルコンピューティング環境における遺伝的アルゴリズムの検討
第3回 並列計算機のアーキテクチャと 並列処理の実際
情報理工学系研究科 コンピュータ科学専攻 上嶋裕樹
計算理工学基礎 「ハイパフォーマンスコンピューティングの基礎」
キャッシュ付PRAM上の 並列クィックソートと 並列マージソート
クラスタの構成技術と クラスタによる並列処理
TCPコネクションの分割 によるスループットの向上
10. メモリ 五島 正裕.
第12回 ソート(3): シェルソート、クイックソート
発表内容 研究背景・目的 伝送線路の構造 伝送線路間カップリングシミュレーション - 1段増幅器シミュレーション
全体ミーティング (4/25) 村田雅之.
研究集会 「超大規模行列の数理的諸問題とその高速解法」 2007 年 3 月 7 日 完全パイプライン化シフト QR 法による 実対称三重対角行列の 固有値並列計算 宮田 考史  山本 有作  張 紹良   名古屋大学 大学院工学研究科 計算理工学専攻.
PCクラスタにおける2個体分散遺伝的アルゴリズムの高速化
対角マトリックスを用いた3次元剛塑性有限要素法の並列計算 対角マトリックスを用いた剛塑性有限要素法
AllReduce アルゴリズムによる QR 分解の精度について
仮想マシンの並列処理性能に対するCPU割り当ての影響の評価
P,Q比が変更可能なScaLAPACKの コスト見積もり関数の開発
分散遺伝的アルゴリズムによる各種クラスタのベンチマーク
各種PC クラスタの性能評価 同志社大学 工学部 廣安 知之 三木 光範 谷村 勇輔.
データ構造とアルゴリズム 分割統治 ~ マージソート~.
Ibaraki Univ. Dept of Electrical & Electronic Eng.
ネットワーク性能に合わせた 分散遺伝的アルゴリズムにおける 最適な移住についての検討
デジタル回路(続き) コンピュータ(ハードウェアを中心に)
応用数理工学特論 第5回 計算理工学専攻 張研究室 山本有作.
MPIによる行列積計算 情報論理工学研究室 渡邉伊織 情報論理工学研究室 渡邉伊織です。
Occam言語による マルチプリエンプティブシステムの 実装と検証
文献名 “Performance Tuning of a CFD Code on the Earth Simulator”
Mathematicaによる固有値計算の高速化 Eigenvalue calculation speed by Mathematica
並列計算技術によるタンパク質の構造解析 IBM RS/6000SPを用いた研究 同志社大学大学院 小掠真貴 同志社大学工学部 廣安知之
OpenMPハードウェア動作合成システムの検証(Ⅰ)
MPIによるwavからmp3圧縮の検証 情報論理工学研究室 04‐1‐47‐200 木村 惇一.
計算理工学基礎 「ハイパフォーマンスコンピューティングの基礎」
ソフトを用いた動画の並列変換処理 情報論理工学研究室 中村勇介.
MPIを用いた並列計算 情報論理工学研究室 清水周.
応用数理工学特論 第6回 計算理工学専攻 張研究室 山本有作.
MPIを用いた最適な分散処理 情報論理工学研究室 角 仁志
決定木とランダムフォレスト 和田 俊和.
MPIとOpenMPを用いた Nクイーン問題の並列化
混合ガウスモデルによる回帰分析および 逆解析 Gaussian Mixture Regression GMR
リモートホストの異常を検知するための GPUとの直接通信機構
Jh NAHI 横田 理央 (東京工業大学) Hierarchical low-rank approximation methods on distributed memory and GPUs 背景  H行列、H2行列、HSS行列などの階層的低ランク近似法はO(N2)の要素を持つ密行列をO(N)の要素を持つ行列に圧縮することができる。圧縮された行列を用いることで、行列積、LU分解、固有値計算をO(NlogN)で行うことができるため、従来密行列の解法が用いられてきた分野では階層的低ランク近似法
通信機構合わせた最適化をおこなう並列化ンパイラ
進化的計算手法の並列計算機への実装 三木 光範
導電性高分子材料の電子状態計算に現れる連立一次方程式に対する 並列直接解法の高性能化
決定木 Decision Tree DT 明治大学 理工学部 応用化学科 データ化学工学研究室 金子 弘昌.
アルゴリズムとプログラミング (Algorithms and Programming)
Genetic Algorithm-based Partial Least Squares GAPLS Genetic Algorithm-based Support Vector Regression GASVR 明治大学 理工学部 応用化学科 データ化学工学研究室 金子 弘昌.
3次元Nクイーン問題の 解の存在の検証 07-1-037-0106 前波 大貴 情報論理工学研究室 宜しくお願いします。
情報論理工学 研究室 研究テーマ 並列アルゴリズム.
並列処理プロセッサTPCOREの 組み込みシステムへの応用 理工学研究科数理情報科学専攻 福永 力,岩波智史,情報システム研究室.
Ibaraki Univ. Dept of Electrical & Electronic Eng.
遺伝アルゴリズムによる NQueen解法 ~問題特性に着目した突然変異方法の改善~
全体ミーティング (5/23) 村田雅之.
社会の情報インフラストラクチャとして、高性能コンピュータおよびネットワークの重要性はますます増大しています。本研究室では、コンピュータおよびネットワークの高速化を狙いとする並列・分散情報処理の科学と技術に関する研究に取り組んでいます。効率のよいシステムの実現を目指して、下記の項目を追求しています。 ◇コンピュータアーキテクチャ.
卒業研究 JCSPを用いたプログラム開発  池部理奈.
Jh NAHI 横田 理央 (東京工業大学) Hierarchical low-rank approximation methods on distributed memory and GPUs 背景  H行列、H2行列、HSS行列などの階層的低ランク近似法はO(N2)の要素を持つ密行列をO(N)の要素を持つ行列に圧縮することができる。圧縮された行列を用いることで、行列積、LU分解、固有値計算をO(Nlog2N)で行うことができるため、従来密行列の解法が用いられてきた分野では階層的低ランク近似
理工学部情報学科 情報論理工学研究室 延山 周平
ソートのプログラムの流れ 配列の中身を小さい順に並び替える a[1],a[2],…a[n]の値を順に出力する
コンピュータアーキテクチャ 第 9 回.
MPIを用いた並列処理計算 情報論理工学研究室 金久 英之
密行列固有値解法の最近の発展 (I) - Multiple Relatively Robust Representation アルゴリズム - 2004年11月26日 名古屋大学 計算理工学専攻 山本有作 日立製作所の山本有作です。 「~」について発表いたします。
IPmigrate:複数ホストに分割されたVMの マイグレーション手法
情報論理工学 研究室 第1回:並列とは.
BSPモデルを用いた 最小スパニング木 情報論理工学研究室 02-1-47-134 小林洋亮.
応用数理工学特論 線形計算と ハイパフォーマンスコンピューティング
MPIを用いた 並列処理 情報論理工学研究室 06‐1‐037‐0246 杉所 拓也.
分散メモリ型並列計算機上での行列演算の並列化
アーキテクチャパラメータを利用した並列GCの性能予測
Presentation transcript:

BSPモデルを用いた 並列計算の有用性の検証 情報論理工学研究室 00-1-26-019 伊波 修一

目的 BSPモデル上で高速なクイックソートを行う ※BSP:通信や同期を考慮した並列計算モデル ※クイックソート: 整列アルゴリズムの一種

並列計算とは 問題を複数の仕事に分解 並列化された計算機群に計算をさせる 1つの問題に対して複数のマシンを利用 目的:複雑な問題をより早く解く

PRAMモデル (Parallel Random Access Memory) Shared Memory P1 P2 P3 Pn ・・・・・・ ・通信時間時間を考えない ・並列処理機構が理想的

PRAMモデル (Parallel Random Access Memory) 通信を考えない   → 理想的な並列計算モデル   → 現実と大きなギャップ

BSPモデル (Bulk Synchronous Parallel ) 分散メモリ型 現実に則した並列計算モデル    → 通信時間や同期を考慮

BSP:分散メモリ型並列計算機 M1 M2 M3 Mn ・・・・・・ P1 P2 P3 Pn ・・・・・・ NETWORK

並列クイックソート 基準値を選ぶ 基準値を選ぶ 基準値を選ぶ 赤:プロセッサ1  青:プロセッサ2 緑:プロセッサ3  黄:プロセッサ4

基準値の選択法 PRAMの場合   → 通信時間がない   → 基準値=中央値 BSPの場合   → 通信時間を考慮   → 基準値=通信を考慮して選択  

BSP上でクイックソートを行う場合の注意点 内部計算時間T1 通信時間S1 P2 内部計算時間T2 P3 内部計算時間T3 通信時間S2 P4 内部計算時間T4 実行時間 T1+T2=T3+T4  S1=S2

基準値の選択 サンプルS個を抽出   → これを整列   → X番目に小さい値を選ぶ

サンプル数(S)の決定

通信帯域幅が狭いときのシミュレーション X=8 1:3に分割

通信帯域幅が広いときのシミュレーション

通信帯域幅が広いときのシミュレーション X=12 3:5

結論 通信帯域幅が狭くてもデータ分割を上手く行えば高速化できる。