キャッシュ付ＰＲＡＭ上の 並列クィックソートと 並列マージソート

Presentation on theme: "キャッシュ付ＰＲＡＭ上の 並列クィックソートと 並列マージソート"— Presentation transcript:

1 キャッシュ付ＰＲＡＭ上の 並列クィックソートと 並列マージソート
情報論理工学研究室 　桜打　純視

2 あらまし 背景 ＰＲＡＭ(Parallel Random Access Machine) キャッシュ付ＰＲＡＭ
並列クィックソートと並列マージソート 結果と考察 まとめ　

3 並列計算機 高速に問題を解きたい より複雑な問題を解きたい プロセッサ価格の低下 並列計算機の誕生 複数のプロセッサを持つ計算機

4 並列アルゴリズム 並列アルゴリズムとは 並列計算モデルとは 並列計算機上で動作するアルゴリズム 並列計算モデル上で設計・解析
並列計算機を抽象化 PRAM, BSP, メッシュ, ハイパーキューブ, etc…

5 ＰＲＡＭ(Parallel Random Access Machine)
共有メモリ P1 P2 P3 Pp ・・・・・・・ P : プロセッサ

6 共有メモリ キャッシュ付ＰＲＡＭ ・・・・・・・ ＰＲＡＭの拡張モデル P1 P2 P3 Pp キャッシュ キャッシュ キャッシュ

7 キャッシュサイズと通信遅延 キャッシュ付ＰＲＡＭのパラメタ 多くの計算機はキャッシュ付き より現実に近いモデル c : キャッシュサイズ
d : キャッシュ-共有メモリ間の通信遅延 共有メモリ上の連続した c 個のデータを　　　　　　　　　　　　　　ｄ 時間でキャッシュに読み込める 多くの計算機はキャッシュ付き より現実に近いモデル

8 並列クィックソート(Parallel Quick Sort)
n個のデータ P1 P1 P2 基準値より小 基準値より大 Ｄ４ P1 P3 P2 P4 P1 P3 P2 P５ P6 P7 P4 P8

9 並列マージソート(Parallel Merge Sort)
d P1 P2 P1

10 シミュレートプログラム 並列クィックソート 並列マージソート 　キャッシュ付ＰＲＡＭ上での 　シミュレートプログラムを作成

11 実行結果(並列クィックソート) キャッシュサイズ c データ数 : 1024 プロセッサ数 : 128

12 実行結果(並列マージソート) キャッシュサイズ c マージソート クィックソート データ数 : 1024 プロセッサ数 : 128

13 結果と考察 両アルゴリズムとも キャッシュサイズによる実行時間への影響 マージソートは連続したデータを扱うためキャッシュを有効的に利用できる
通信遅延時間: 大 ⇒ 実行時間: 大 キャッシュサイズ: 大 ⇒ 実行時間: 小 キャッシュサイズによる実行時間への影響 マージソート > クィックソート マージソートは連続したデータを扱うためキャッシュを有効的に利用できる

14 まとめ キャッシュサイズ、通信遅延に応じて 両アルゴリズムを使い分ける キャッシュ付ＰＲＡＭ上の動作のシミュレート
並列クィックソートと並列マージソート 両アルゴリズムとも 通信遅延時間: 大 ⇒ 実行時間: 大 キャッシュサイズ: 大 ⇒ 実行時間: 小 キャッシュサイズによる実行時間への影響 マージソート > クィックソート キャッシュサイズ、通信遅延に応じて 両アルゴリズムを使い分ける