HBSP モデル上での 行列積を求めるアルゴリ ム 情報論理工学 吉岡健太
あらまし 背景 研究内容 結果 結論・今後の課題
背景 膨大な計算量を必要とする問題を高速かつ 短時間で解きたい 複雑な問題を解きたい ( 例 ) 画像処理、気象シミュレーション、コンピュータ グラフィック、天体の軌道計算など プロセッサの性能の向上 複数のプロセッサを持つ並列計算機 による並列処理
HBSP （ Heterogeneous Bulk- Synchronous Parallel ）モデル ネットワーク メモ リ プロセッサ …………… ＨＢＳＰモデルの概念図
HBSP モデルのパラメタと特徴 ｐ 2 ：プロセッサ数 g ：通信コスト Ｌ：バリア同期時間 s i ：プロセッサ P i の速度 s 0 ≧ s 1 ≧ ……… ≧ s p 2 -1 =1 s ：プロセッサの速度合計 s=∑s i 計算量の小さい処理 最も早いプロセッサ１台で行う 計算量の大きい処理 プロセッサの能力差によって処理を割り当て
研究内容 n*n の行列積 C=A*B に対して各行列 A,B,C を それぞれ s 個の部分行列に分割し 速度 s i (0 ≦ i ＜ p 2 ) であるプロセッサ p i に対して s i 個の部分 行 列を割り当てる 本研究では簡単のために通信コストと各プロセッサ の処理速度が比例すると仮定する。 g 0 :s 0 =g 1 :s 1 ==g p 2 -1 :s p 2 -1 この式よりプロセッサ P i はプロセッサ P p 2 -1 に比べて 内部計算命令および送信命令は s i 倍高速に実行でき る
データの割り当て方 入力行列 A,B の各プロセッサへのデータの割り当て方は以 下の３通り α ：それぞれサイズ n/s 0.5 *n/s 0.5 個の部分行列に分割し、各プロセッサに１つ の部分行列を割り当てる β ：それぞれサイズ n/s*n 個の部分行列に分割し、各プロセッサに１つの部 分行列を割り当てる γ ：それぞれサイズ n*n/s 個の部分行列に分割し、各プロセッサに１つの部 分行列を割り当てる αβ γ
割り当て方の組み合わせ方は 3 3 =27 通りある 入力行列 B ：送信に必要なデータ数は行列 A を縦横 入れ替えたものと等しい 解行列 C ： β と γ の向きが異なるだけ よって、割り当て方の組み合わせは A と C について 考慮すればいいので 3 2 =9 通りの組み合わせに ついて求める
組み合わせの９通り ① A の割り当て方 α C の割り当て方 α ② A の割り当て方 α C の割り当て方 α ③ A の割り当て方 α C の割り当て方 α ④ A の割り当て方 α C の割り当て方 α ⑤ A の割り当て方 α C の割り当て方 α ⑥ A の割り当て方 α C の割り当て方 α ⑦ A の割り当て方 α C の割り当て方 α ⑧ A の割り当て方 α C の割り当て方 α ⑨ A の割り当て方 α C の割り当て方 α
A のデータ送信については①から⑨より C の割り当て方が α の時の全体の通信計算量 は O(g*{n 2 /s 0.5 }+L) C の割り当て方が β の時の全体の通信計算量は O(g*n 2 +L) C の割り当て方が γ の時の全体の通信計算量は O(g*{n 2 /s}+L)
B のデータ送信については A を縦横入れ替えたものと等しいので C の割り当て方が α の時の全体の通信計算量 は O(g*{n 2 /s 0.5 }+L) C の割り当て方が β の時の全体の通信計算量は O(g*{n 2 /s}+L) C の割り当て方が γ の時の全体の通信計算量は O(g*n 2 +L)
結果 よって、通信計算量が最小となるのは C=A*B に対して α=α*α の分割パターンにした時 であり、通信計算量は O(g*{n 2 /s 0.5 }+L) また、解行列の計算は O(n 3 /s) で行うことが 出来 るので、 HBSP モデル上での行列積を求めるア ル ゴリズム計算量は O(n 3 /s+n 2 /s 0.5 +L) となる。
結論と今後の課題 各プロセッサへの最適なデータの割り当て方 は行列積 C=A*B に対して各行列を s 0.5 *s 0.5 個 の部分行列に分割し、プロセッサ P i に s i 個の 部分行列を割り当てた場合である。 データを送信する最適な分割パターンは各部 分行列が正方形になる場合である。 行列以外にも２次元配列になっているデータ が存在するような問題に対する各プロセッサ へのデータの割り当て方を求めていくことが 必要