ＢＳＰ上での整列法 情報論理工学研究室 ０１―１－２６－００７ 北村勇樹 あらまし 背景 ＢＳＰモデル 並列クイックソート 結果 まとめ 並列計算機モデル ・ＰＲＡＭ(Parallel Random Access Machine) ・ＢＳＰ（Bulk Synchronous Parallel) ・Mesh ・Hypercube ＰＲＡＭ 共有メモリ Ｐ1 Ｐ2 Ｐｎ ＢＳＰ ネットワーク プロセッサ メモリ プロセッサ メモリ プロセッサ メモリ ＢＳＰとＰＲＡＭの違い ＰＲＡＭ ＢＳＰ 1命令ごと スーパース テップごと 通信遅延 1 Ｌ 帯域幅 1 1／ｇ 同期 ＰＲＡＭ上での並列クイックソート１ n プロセッサ：Ｐ1 Ｐ2 Ｐ3 Ｐ4 ＰＲＡＭ上での並列クイックソート２ n プロセッサ：Ｐ1 Ｐ2 Ｐ3 Ｐ4 ＢＳＰ上での並列クイックソート１ 通信 プロセッサ：Ｐ1 Ｐ2 Ｐ3 Ｐ4 ＢＳＰ上での並列クイックソート２ 通信 プロセッサ：Ｐ1 Ｐ2 Ｐ3 Ｐ4 基準値の選択 ＰＲＡＭ 基準値＝中央値 ＢＳＰ 通信を考慮して選ぶ シミュレートプログラム ＢＳＰ上での整列の実行をシミュレートする。 入力：データ数N プロセッサ数：Ｐ 通信帯 域幅：ｇ 通信遅延時間：Ｌ 出力：整列アルゴリズムの実行時間 最適な基準位置 実行時間 ｔ 帯域幅と実行時間 70000 60000 基準値＝ 中央値 基準値＝ 最適値 50000 40000 30000 20000 10000 0 1/ 1/ 1/ 1/ 1/ 1/ 1 64 32 16 8 4 2 帯域幅 ｇ 実行時間 ｔ 通信遅延と実行時間 30000 25000 20000 15000 10000 5000 0 基準値 ＝中央 値 基準値 ＝最適 値 1 4 16 通信遅延 ｌ 64 結論 ＢＳＰ上での並列アルゴリズムを提案 ・帯域幅が狭くなると実行時間は長くなる。 ・通信遅延は実行時間にあまり影響を及ぼさない。 ・ソーティングの基準値は通信を考慮し、最適な値 を選ぶ必要がある。
© Copyright 2024 ExpyDoc
