キャッシュ付PRAM上の 並列クィックソートと 並列マージソート

Slides:



Advertisements
Similar presentations
HBSP モデル上での 行列積を求めるアルゴリ ム 情報論理工学 吉岡健太.
Advertisements

MPIを用いたグラフの並列計算 情報論理工学研究室 藤本 涼一.
3次元nクイーン問題の 解に関する研究 論理工学研究室 伊藤精一
第3回 並列計算機のアーキテクチャと 並列処理の実際
情報理工学系研究科 コンピュータ科学専攻 上嶋裕樹
計算理工学基礎 「ハイパフォーマンスコンピューティングの基礎」
クラスタの構成技術と クラスタによる並列処理
ヘテロジニアスマルチコアプロセッサ 環境を対象としたキャッシュシステム 自動生成ツールの開発
Chapter11-4(前半) 加藤健.
Pose Tracking from Natural Features on Mobile Phones
久保幹雄 東京海洋大 宇野 毅明 国立情報学研究所 藤澤 克樹 中央大学 宮本 裕一郎 上智大学
秘密のリンク構造を持つグラフのリンク解析
計算機システムⅡ 主記憶装置とALU,レジスタの制御
研究集会 「超大規模行列の数理的諸問題とその高速解法」 2007 年 3 月 7 日 完全パイプライン化シフト QR 法による 実対称三重対角行列の 固有値並列計算 宮田 考史  山本 有作  張 紹良   名古屋大学 大学院工学研究科 計算理工学専攻.
仮想マシンの並列処理性能に対するCPU割り当ての影響の評価
遺伝アルゴリズムによる NQueen解法 ~遺伝補修飾を用いた解探索の性能評価~
記 憶 管 理(2) オペレーティングシステム 第10回.
データ構造とアルゴリズム 分割統治 ~ マージソート~.
医療支援診断のためのコンピュータ分散システムの検討
大阪教育大学大学院教育学研究科 総合基礎科学専攻 中窪 仁
Ibaraki Univ. Dept of Electrical & Electronic Eng.
Systems and Software Verification 10. Fairness Properties
ネットワーク性能に合わせた 分散遺伝的アルゴリズムにおける 最適な移住についての検討
計算機システムⅡ 入出力と周辺装置 和田俊和.
MPIによる行列積計算 情報論理工学研究室 渡邉伊織 情報論理工学研究室 渡邉伊織です。
外部共有サーバーによる認証設定と そのセキュリティ問題に関する基礎的考察 施設設計工学研究室 馬場 健.
静的情報と動的情報を用いた プログラムスライス計算法
MPIによるwavからmp3圧縮の検証 情報論理工学研究室 04‐1‐47‐200 木村 惇一.
アルゴリズムとチューリングマシン 「もの」(商品)としてのコンピュータ 「こと」(思想)としてのコンピュータ アルゴリズム
MPIを用いた並列計算 情報論理工学研究室 清水周.
高速剰余算アルゴリズムとそのハードウェア実装についての研究
MPIを用いた最適な分散処理 情報論理工学研究室 角 仁志
MPIとOpenMPを用いた Nクイーン問題の並列化
ソートアルゴリズムの種類 選択ソート (selection sort) バブルソート (bubble sort)
オペレーティングシステム イントロダクション
アルゴリズムとデータ構造 補足資料4-1 「メモリと配列」
通信機構合わせた最適化をおこなう並列化ンパイラ
先進的計算基盤システムシンポジウム SACSIS2007併設企画 マルチコアプログラミングコンテスト 「Cellスピードチャレンジ2007」
適応的近傍を持つ シミュレーテッドアニーリングの性能
信号伝搬時間の電源電圧依存性の制御 による超伝導単一磁束量子回路の 動作余裕度の改善
3次元Nクイーン問題の 解の存在の検証 07-1-037-0106 前波 大貴 情報論理工学研究室 宜しくお願いします。
情報論理工学 研究室 研究テーマ 並列アルゴリズム.
VMが利用可能なCPU数の変化に対応した 並列アプリケーション実行の最適化
Virtualizing a Multiprocessor Machine on a Network of Computers
プログラミング演習Ⅲ- Sorting Quick Sort and Merge Sort
第5回 メモリ管理(2) オーバレイ方式 論理アドレスとプログラムの再配置 静的再配置と動的再配置 仮想記憶とメモリ階層 セグメンテーション
並列処理プロセッサTPCOREの 組み込みシステムへの応用 理工学研究科数理情報科学専攻 福永 力,岩波智史,情報システム研究室.
Ibaraki Univ. Dept of Electrical & Electronic Eng.
コンピュータアーキテクチャ 第 9 回.
マイグレーションを支援する分散集合オブジェクト
福岡工業大学 情報工学部 情報工学科 種田研究室 于 聡
秘匿リストマッチングプロトコルとその応用
遺伝アルゴリズムによる NQueen解法 ~問題特性に着目した突然変異方法の改善~
「マイグレーションを支援する分散集合オブジェクト」
成長する一次元自己組織化写像の応用について
BSPモデルを用いた 並列計算の有用性の検証
理工学部情報学科 情報論理工学研究室 延山 周平
ソートのプログラムの流れ 配列の中身を小さい順に並び替える a[1],a[2],…a[n]の値を順に出力する
計算機群における 「動的なインターネット接続性」の共有に関する研究
コンピュータアーキテクチャ 第 9 回.
MPIを用いた並列処理計算 情報論理工学研究室 金久 英之
シミュレーション演習 G. 総合演習 (Mathematica演習) システム創成情報工学科
情報論理工学 研究室 第1回:並列とは.
複数ホストにまたがるVMの 高速かつ柔軟な 部分マイグレーション
BSPモデルを用いた 最小スパニング木 情報論理工学研究室 02-1-47-134 小林洋亮.
参考:大きい要素の処理.
MPIを用いた 並列処理 情報論理工学研究室 06‐1‐037‐0246 杉所 拓也.
信号伝搬時間の電源電圧依存性の制御 による超伝導単一磁束量子回路の 動作余裕度の改善
分散メモリ型並列計算機上での行列演算の並列化
アーキテクチャパラメータを利用した並列GCの性能予測
Presentation transcript:

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