BSP*モデル上での行列積アルゴリズム情報論理工学研究室 04-1-47-041 山田直人 • BSPモデルとBSP*モデルについて • 行列積を求めるアルゴリズム • 結果・今後の課題 BSPモデル • Bulk-Synchronous Parallel モデル • 非同期式計算モデル • P（プロセッサ数）、g（通信路帯域幅）、L（同期周期）といったパラメタを持つ BSPモデル • スーパーステップの実行にO(w+gh+L)時間 • 通信のオーバーヘッドや同期のオーバーヘッドを考慮することができる BSP*モデル • • • • BSPモデルの拡張モデル Bäumkerらによって提案通信計算量にパケットの概念を導入 B（通信パケットの最小サイズ）といったパラメタをもつ     • スーパーステップの実行に O s   w  g  L     B     時間 h i 1 i BSP*モデル上で行列積を求めるアルゴリズム • n*nの行列積C=ABを考える • p個の部分行列に分割され、各プロセッサへ • 部分行列の分割のパターンに対する通信計算量の比較部分行列の分割の仕方 • 全体で33=27通り • A,Bの割り当ては縦横が異なるのみ（送信が必要なデータ数と送信先数が同じ） • ＡとＣの組み合わせの32=9通りで考える結果 • Cは(a)、Aは(a)または(c)、Bは(a)または(b)の組み合わせの場合に通信計算量が最小 (a) (b) (c) 結果 • 通信計算量 3 2  n   n     O g p  L   p  p  B    • 最適なアルゴリズムとなるpの数 22 2 n Bn p 2 (  B のとき ) g p 2 2 n n p  (  B のとき ) 2 3 g p 今後の課題 • ２次元上にデータが存在する問題に対するデータ分割など