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