並列クィックソートと 並列クィックソートと

キャッシュ付ＰＲＡＭ上の キャッシュ付ＰＲＡＭ上の

並列クィックソートと 並列クィックソートと

並列マージソート 並列マージソート

情報論理工学研究室 情報論理工学研究室

01-1-26-081

　桜打　純視 　桜打　純視

あらまし あらまし



背景 背景



ＰＲＡＭ ＰＲＡＭ

Machine)



キャッシュ付ＰＲＡＭ キャッシュ付ＰＲＡＭ



並列クィックソートと並列マージソート 並列クィックソートと並列マージソート



結果と考察 結果と考察



まとめ　 まとめ　

並列計算機 並列計算機



高速に問題を解きたい 高速に問題を解きたい



より複雑な問題を解きたい より複雑な問題を解きたい



プロセッサ価格の低下 プロセッサ価格の低下

並列計算機の誕生



複数のプロセッサを持つ計算機

並列アルゴリズム 並列アルゴリズム



並列アルゴリズムとは 並列アルゴリズムとは

•

並列計算機上で動作するアルゴリズム 並列計算機上で動作するアルゴリズム



並列計算モデル上で設計・解析 並列計算モデル上で設計・解析



並列計算モデルとは 並列計算モデルとは

•

並列計算機を抽象化 並列計算機を抽象化

 PRAM, BSP, PRAM, BSP,

メッシュ メッシュ

ハイパーキュー ハイパーキュー

ブ ブ

ＰＲＡＭ ＰＲＡＭ

Machine)

P₁

・・・・・・・

共有メモリ 共有メモリ

P₂ P₃ P_p

P : プロセッサ

キャッシュ付ＰＲＡＭ キャッシュ付ＰＲＡＭ

P₁

・・・・・・・

キャッシュ キャッシュ

共有メモリ 共有メモリ

P₂

キャッシュ キャッシュ

P₃

キャッシュ キャッシュ

P_p

キャッシュ キャッシュ

ＰＲＡＭの拡張モデル

キャッシュサイズと通信遅延 キャッシュサイズと通信遅延



キャッシュ付ＰＲＡＭのパラメタ キャッシュ付ＰＲＡＭのパラメタ

• cc : :

キャッシュサイズ キャッシュサイズ

• dd : :

キャッシュ キャッシュ

共有メモリ間の通信遅延 共有メモリ間の通信遅延



共有メモリ上の連続した 共有メモリ上の連続した

個のデータを 個のデータを 　　　　　　

時間でキ 時間でキ ャッシュに読み込める

ャッシュに読み込める



多くの計算機はキャッシュ付き 多くの計算機はキャッシュ付き



より現実に近いモデル より現実に近いモデル

並列クィックソート

並列クィックソート

Sort)

基準値より小 基準値より大

P₁

P₁ P₂

P₁ P₃ P₂ P₄

n 個のデータ

P₁ P _５ P₃ P₆ P₂ P₇ P₄ P₈

並列マージソート

並列マージソート

Sort)

P₁ P₅ P₃ P₆ P₂ P₇ P₄ P₈

P₁

P₁ P₂

P₁ P₃ P₂ P₄

シミュレートプログラム シミュレートプログラム



並列クィックソート 並列クィックソート



並列マージソート 並列マージソート

　キャッシュ付ＰＲＡＭ上での 　キャッシュ付ＰＲＡＭ上での

　シミュレートプログラムを作成

　シミュレートプログラムを作成

実行結果 実行結果 ( ( 並列クィックソー 並列クィックソー ト ト ) )

キャッシュサイズ c

データ数 : 1024 プロセッサ数 : 128

実行結果 実行結果 ( ( 並列マージソート 並列マージソート ) )

キャッシュサイズ c

データ数 : 1024

マージソート クィックソート

結果と考察 結果と考察



両アルゴリズムとも 両アルゴリズムとも

•

通信遅延時間 通信遅延時間

大 ⇒ 実行時間 大 ⇒ 実行時間

大 大

•

キャッシュサイズ キャッシュサイズ

大 ⇒ 実行時間 大 ⇒ 実行時間

小 小



キャッシュサイズによる実行時間への影 キャッシュサイズによる実行時間への影 響 響

•

マージソート マージソート

クィックソート クィックソート



マージソートは連続したデータを扱うた マージソートは連続したデータを扱うた めキャッシュを有効的に利用できる

めキャッシュを有効的に利用できる

まとめ まとめ



キャッシュ付ＰＲＡＭ上の動作のシミュレート キャッシュ付ＰＲＡＭ上の動作のシミュレート

•

並列クィックソートと並列マージソート 並列クィックソートと並列マージソート



両アルゴリズムとも 両アルゴリズムとも



通信遅延時間 通信遅延時間

大 ⇒ 実行時間 大 ⇒ 実行時間

大 大



キャッシュサイズ キャッシュサイズ

大 ⇒ 実行時間 大 ⇒ 実行時間

小 小



キャッシュサイズによる実行時間への影響 キャッシュサイズによる実行時間への影響



マージソート マージソート

クィックソート クィックソート

キャッシュサイズ、通信遅延に応じて キャッシュサイズ、通信遅延に応じて

両アルゴリズムを使い分ける

両アルゴリズムを使い分ける