BSPモデル上の 並列ソーティングアルゴリズム 情報論理工学研究室 01-1-26-003 松川 怜 あらまし 背景 BSP（Bulk-Synchronous Parallel） BSP上でのソーティングアルゴリズム 実行結果と解析 まとめ 背 景 問題を高速に解きたい。 サイズの大きい（複雑）な問題を解きたい。 コンピュータ素子の価格が安く手に入る。 並列アルゴリズムの必要性が高まっている。 並列計算モデル 並列アルゴリズムの設計・解析 並列計算モデル上で行う。 代表的な並列計算モデル PRAM、メッシュ、BSP・・・・・ ＰＲＡＭ （parallel random access machine） 共有メモリ P1 P2 P3 ・・・・・・・ PP PRAMの特徴 1単位時間でデータの読み書き 1単位時間ごとに自動的に同期 プロセッサ間通信は共有メモリを通じて行う 以上のように仮定されているため、通信遅延や 同期等を考える必要がない（設計が容易） BSP （Bulk Synchronous Parallel） ネットワーク メモリ メモリ メモリ P1 P2 P3 同期機構 BSP上での実行 barrier synchronization L P1 P2 P3 P4 superstep ：local computation g ：communication BSPの特徴 内部計算=1単位時間 ；送信命令=g単位時間 ；同期時間=L単位時間 g：通信の帯域幅 L：通信遅延 同期や通信について考慮しなければならない PRAM上でのクイックソート P1 P1 P1 P2 P3 P1 P5 P3 P6 P2 P2 P4 P7 P4 P8 BSP上でのクイックソート P1 通信 P1 P2 通信 P1 P3 P1 P5 P3 P6 通信 P2 P2 P4 P7 P4 P8 BSP上でのクイックソート P1 通信 P1 P2 通信 P1 通信 P3 P2 P4 基準値の選び方 PRAM 基準値＝中央値 BSP 基準値＝通信遅延を考慮した最適な値を考える 基準値k=2(gN+L)/N(logN+2g) N：データ数 g：通信の帯域幅 L：通信遅延 実行結果 最適値 中央値 10000 1000 1 2 4 8 16 32 64 128 256 実行命令数 100000 通信帯域幅 結論 BSPモデル上で高速なソートアルゴリズ ムを提案 基準値を通信を考慮して選択 基準値k=2(gN+L)/N(logN+2g) N:データ数 g：通信の帯域幅 L：通信遅延
© Copyright 2024 ExpyDoc
