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

並列アルゴリズム(Parallel Algorithm)