BSPモデルを用いた 並列計算の有用性の検証 情報論理工学研究室 00-1-26-019 伊波 修一 目的 • BSPモデル上で高速なクイックソートを行う ※BSP：通信や同期を考慮した並列計算モデル ※クイックソート： 整列アルゴリズムの一種 並列計算とは • 問題を複数の仕事に分解 • 並列化された計算機群に計算をさせる • １つの問題に対して複数のマシンを利用 • 目的：複雑な問題をより早く解く ＰＲＡＭモデル (Parallel Random Access Memory) Ｓｈａｒｅｄ Ｍｅｍｏｒｙ P1 P2 P3 ・・・・・・ ・通信時間時間を考えない ・並列処理機構が理想的 Pn ＰＲＡＭモデル (Parallel Random Access Memory) • 通信を考えない → 理想的な並列計算モデル → 現実と大きなギャップ BSPモデル （Bulk Synchronous Parallel ） • 分散メモリ型 • 現実に則した並列計算モデル → 通信時間や同期を考慮 BSP：分散メモリ型並列計算機 M1 M2 M3 ・・・・・・ Mn P1 P2 P3 ・・・・・・ Pn NETWORK 並列クイックソート 基準値を選ぶ 基準値を選ぶ 基準値を選ぶ 赤：プロセッサ１ 青：プロセッサ２ 緑：プロセッサ３ 黄：プロセッサ4 基準値の選択法 • PRAMの場合 → 通信時間がない → 基準値＝中央値 • BSPの場合 → 通信時間を考慮 → 基準値＝通信を考慮して選択 BSP上でクイックソートを行う場合の注意点 P1 内部計算時間T1 P2 内部計算時間T2 P3 内部計算時間T3 P4 通信時間S1 通信時間S2 内部計算時間T4 実行時間 T1+T2=T3+T4 S1=S2 基準値の選択 • サンプルＳ個を抽出 → これを整列 → Ｘ番目に小さい値を選ぶ サンプル数(S)の決定 60000 58000 56000 計算量 54000 S=2 S=4 S=8 S=16 S=32 S=64 52000 50000 48000 46000 44000 42000 40000 0 1 2 4 8 16 32 64 プロセッサ数 128 256 512 図1 BSPモデルシミュレートの実験結果（L=16、g=32、X=S/2） 通信帯域幅が狭いときのシミュレーション 60000 55000 W=16 X=14 X=12 X=10 X=8 X=6 50000 計算量 45000 40000 35000 30000 25000 20000 15000 0 1 2 4 8 16 32 64 128 256 512 プロセッサ数 図2 B SPモデルシミュレートの実験結果（ L= 1 6 、g= 3 2 、S= 3 2 ） Ｘ＝８ 1:3に分割 通信帯域幅が広いときのシミュレーション 60000 55000 50000 X=16 X=14 X=12 X=10 X=8 計算量 45000 40000 35000 30000 25000 20000 15000 10000 0 1 2 4 8 16 32 64 プロセ ッサ数 128 256 512 図６ B SPモデルシミュレート の実験結果（ L= 1 6 、g= 8 ） 通信帯域幅が広いときのシミュレーション 30000 28000 26000 X=16 X=14 X=12 X=10 X=8 計算量 24000 22000 20000 18000 16000 14000 12000 10000 0 1 2 4 8 16 32 64 128 256 512 プロセ ッサ数 図６ B SPモデルシミュレート の実験結果（ L= 1 6 、g= 8 ） Ｘ＝１２ 3:5 結論 • 通信帯域幅が狭くてもデータ分割 を上手く行えば高速化できる。
© Copyright 2024 ExpyDoc
