キャッシュ付PRAM上の 並列クィックソートと 並列マージソート 情報論理工学研究室 01-1-26-081 桜打 純視 あらまし 背景 PRAM(Parallel Random Access Machine) キャッシュ付PRAM 並列クィックソートと並列マージソート 結果と考察 まとめ 並列計算機 高速に問題を解きたい より複雑な問題を解きたい プロセッサ価格の低下 並列計算機の誕生 複数のプロセッサを持つ計算機 並列アルゴリズム 並列アルゴリズムとは • 並列計算機上で動作するアルゴリズム 並列計算モデル上で設計・解析 並列計算モデルとは • 並列計算機を抽象化 PRAM, BSP, メッシュ, ハイパーキューブ, etc… PRAM(Parallel Random Access Machine) 共有メモリ P1 P2 P3 Pp ・・・・・・・ P : プロセッサ キャッシュ付PRAM PRAMの拡張モデル 共有メモリ P1 P2 P3 Pp ・・・・・・・ キャッシュ キャッシュ キャッシュ キャッシュ キャッシュサイズと通信遅延 キャッシュ付PRAMのパラメタ • c : キャッシュサイズ • d : キャッシュ-共有メモリ間の通信遅延 共有メモリ上の連続した c 個のデータを d 時間でキャッシュに読み込める 多くの計算機はキャッシュ付き より現実に近いモデル 並列クィックソート(Parallel Quick Sort) n個のデータ P1 P1 基準値より小 P1 P1 P5 P2 基準値より大 P3 P3 P2 P6 P2 P4 P7 P4 P8 並列マージソート(Parallel Merge Sort) P1 P5 P3 P6 P2 P7 P4 P8 P1 P3 P2 P1 P4 P2 P1 シミュレートプログラム 並列クィックソート 並列マージソート キャッシュ付PRAM上での シミュレートプログラムを作成 実行結果(並列クィックソート) キャッシュ サイズ c 実行時間 1000000 2 4 8 16 32 64 128 256 100000 10000 1 2 4 8 16 32 64 128 256 通信遅延 d データ数 : 1024 プロセッサ数 : 128 実行結果(並列マージソート) キャッシュ サイズ c 1000000 実行時間 マージソート クィックソート 2 4 8 16 32 64 128 256 100000 10000 1 2 4 8 16 32 64 128 256 通信遅延 d データ数 : 1024 プロセッサ数 : 128 結果と考察 両アルゴリズムとも • 通信遅延時間: 大 ⇒ 実行時間: 大 • キャッシュサイズ: 大 ⇒ 実行時間: 小 キャッシュサイズによる実行時間への影響 • マージソート > クィックソート マージソートは連続したデータを扱うため キャッシュを有効的に利用できる まとめ キャッシュ付PRAM上の動作のシミュレート • 並列クィックソートと並列マージソート 両アルゴリズムとも 通信遅延時間: 大 ⇒ 実行時間: 大 キャッシュサイズ: 大 ⇒ 実行時間: 小 キャッシュサイズによる実行時間への影響 マージソート > クィックソート キャッシュサイズ、通信遅延に応じて 両アルゴリズムを使い分ける
© Copyright 2025 ExpyDoc