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の割り当ては縦横が異なるのみ
(送信が必要なデータ数と送信先数が同じ)
• AとCの組み合わせの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
今後の課題
• 2次元上にデータが存在する問題に対するデ
ータ分割など
ダウンロード

卒研発表