BSPモデル上での Selectionアルゴリズム情報論理工学研究室 02-1-47-084 中内義典あらまし • • • • • 背景 BSP(Bulk-Synchronous Parallel) BSP上でのSelectionアルゴリズム実行結果と解析結論背景 • 地球環境のシミュレーション, 天気予報、コンピュータグラフィックス、画像処理など逐次型計算機では扱うのが困難な大規模かつ複雑な問題を解く必要性が高まる。並列計算機並列計算モデル • 並列アルゴリズムの設計・解析 • 並列計算モデル上で行なう • 代表的な並列計算モデル PRAM、Mesh 、Hyper Cube 、BSP PRAM （parallel random access machine）共有メモリ P1 P２ P3 ・・・・・・・・ Pp PRAM上のアルゴリズムの実行 0 1 2 3 4 P1 演算命令 P2 メモリアクセス命令 P3 入出力命令 P4 同期 PRAMの特徴 • １単位時間でデータの読み書き • １単位時間ごとに自動的に同期 • プロセッサ間の通信は共有メモリを通じて行なう BSP (Bulk Synchronous Parallel) ネットワークメモリメモリメモリ P1 P2 P3 同期機構 BSP上での実行例 L P1 P2 P3 P4 スーパーステップ l: 内部計算 g: 通信 BSPの特徴 • 内部計算=1単位時間；送信命令=g単位時間；同期時間=L単位時間・g：通信の帯域幅・L：通信遅延同期や通信について考慮しなければならない PRAMとBSPの比較ＰＲＡＭＢＳＰ同期 1命令ごとスーパーステップごと同期時間 1 Ｌ通信時間 1 ｇ BSP上のSelectionアルゴリズム P1 P2 P3 P4 P5 A1 A2 A3 A4 A5 ｍ1 ｍ2 ｍ4 ｍ5 ｍ3 P0 m1 m2 m3 m4 m5 P1 P2 P3 P4 P5 BSP上のSelectionアルゴリズム P1 m3 A1 L A1 P2 m3 R A2 L A2 P3 m3 R A3 L A3 P4 m3 R A4 L A4 P5 m3 R A5 L A5 P0 50 P1 P2 P3 P4 P5 R BSP上のSelectionアルゴリズム P1 m3 A1 P0 L A1 P2 m3 R A2 L A2 P3 m3 R A3 A3 L P4 m3 R A4 L A4 P5 m3 R A5 L A5 P1 P2 P3 P4 P5 A1 A2 A3 A4 A5 ｍA1 ｍA2 ｍA4 ｍA5 ｍA3 R シミュレートプログラムデータ数nの中でd番目に小さい要素を検索 BSPモデル上でシミュレートをする入力：プロセッサ台数p データ数ｎ出力：内部計算時間、通信時間、同期時間実行結果：内部計算時間 3000 内部計算時間 2500 2000 データ数256 データ数120 データ数60 1500 1000 500 0 0 5 10 15 プロセッサ数 20 実行結果：通信時間 600 500 通信時間 400 データ数256 データ数120 データ数60 300 200 100 0 0 5 10 15 プロセッサ数 20 結論プロセッサ台数をある程度少なくしたほうが実行時間を短縮できるプロセッサ数を増やすことにより、プロセッサ1台辺りの処理データが減るため内部計算時間が減少する一方、プロセッサ内の同期を取る回数が増える内部計算時間、通信時間を抑え、データ数に対するより的確なプロセッサ台数を提案するアルゴリズムを考えることが今後の課題となる。