キャッシュ付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 P2 基準値より小 基準値より大 D4 P1 P3 P2 P4 P1 P3 P2 P5 P6 P7 P4 P8
並列マージソート(Parallel Merge Sort) d P1 P2 P1
シミュレートプログラム 並列クィックソート 並列マージソート キャッシュ付PRAM上での シミュレートプログラムを作成
実行結果(並列クィックソート) キャッシュサイズ c データ数 : 1024 プロセッサ数 : 128
実行結果(並列マージソート) キャッシュサイズ c マージソート クィックソート データ数 : 1024 プロセッサ数 : 128
結果と考察 両アルゴリズムとも キャッシュサイズによる実行時間への影響 マージソートは連続したデータを扱うためキャッシュを有効的に利用できる 通信遅延時間: 大 ⇒ 実行時間: 大 キャッシュサイズ: 大 ⇒ 実行時間: 小 キャッシュサイズによる実行時間への影響 マージソート > クィックソート マージソートは連続したデータを扱うためキャッシュを有効的に利用できる
まとめ キャッシュサイズ、通信遅延に応じて 両アルゴリズムを使い分ける キャッシュ付PRAM上の動作のシミュレート 並列クィックソートと並列マージソート 両アルゴリズムとも 通信遅延時間: 大 ⇒ 実行時間: 大 キャッシュサイズ: 大 ⇒ 実行時間: 小 キャッシュサイズによる実行時間への影響 マージソート > クィックソート キャッシュサイズ、通信遅延に応じて 両アルゴリズムを使い分ける