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

Presentation on theme: "BSPモデルを用いた 並列計算の有用性の検証"— Presentation transcript:

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

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

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

4 ＰＲＡＭモデル (Parallel Random Access Memory)
Ｓｈａｒｅｄ　Ｍｅｍｏｒｙ P1 P2 P3 Pn ・・・・・・ ・通信時間時間を考えない ・並列処理機構が理想的

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

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

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

8 並列クイックソート 基準値を選ぶ 基準値を選ぶ 基準値を選ぶ 赤：プロセッサ１　　青：プロセッサ２ 緑：プロセッサ３　　黄：プロセッサ4

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

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

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

12 サンプル数(S)の決定

13 通信帯域幅が狭いときのシミュレーション Ｘ＝８　1:3に分割

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

15 通信帯域幅が広いときのシミュレーション Ｘ＝１２　3:5

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