@misc{oai:uec.repo.nii.ac.jp:00004938,
 author = {田村, 遼也},
 month = {2016-09-21},
 note = {2013, QR分解は様々な分野に利用される行列分解計算の一つであり、その中でも行数m>>列数nとなる縦長行列に対するQR分解はベクトルの直交式に相当し、様々な数値計算手法で高速でありなおかつ高精度な方法が求められている。従来法のハウスホルダーQRは処理が逐次的で同期や通信多く、並列化が難しい。近年提唱された並列処理に適したTall Skinny QR(TSQR)アルゴリズムでは縦長行列を行方向に分割した小行列をQR分解し、得られた上三角行列Rを結合し、QR分解を繰り返す階層的な構造をしている。A=[■(A_0@A_1 )]=[■(Q_0 R_0@Q_1 R_1 )]→[■(R_0@R_1 )]=Q_2 R_2 本研究ではGraphics Processing Unit (GPU)に着目しNVIDIA社のCUDAを用いたTSQRの実装を行う。CUDAではカーネル関数として実装した部分をGPUで並列処理することができる。TSQRでは自明な並列性のある複数の行列に対するQR分解をカーネル関数とするべきである。ここで、CUDAブロック単位で1つのQR分解を処理することが理想的であるが、現在のCUDAの実行モデルでは2分木等の葉の実行完了をブロック間で認識できないので、一旦ホストに戻し、システムレベルで大きな同期を行う必要がある。TSQRの第二階層以降で扱う行列はとても小さいものとなるので、データの移動は少ないものの、実行時間全体に占める同期のコストは大きくなることが問題となる。本研究では、コストが大きい集約操作を2分木型ではなく1度に全て集約する形とし、同期の回数を最小限に抑える実装を行う。本実装とCUDA向けの線形代数ライブラリであるMAGMAでQR分解実行時間の比較実験を行った。MAGMAはハウスホルダーQR を使用している。結果、行数が少ない場合では、MAGMAに大差をつけられるが、1ブロックあたりで処理するベクトルの長さが十分大きくなる行数領域では本実装の方が高速であった。最適化された実装であるMAGMAに対し、最適化が十分でない本実装でも高速である場合が確認でき、最適化を進めることで本実装の優位性が高まることが望める。さらに、2分木型でホスト経由の同期を行わない1カーネル版のTSQRは理想的な実装であるが、ブロック間同期等の新技術によりこれが実現可能であるとの知見を得ており、今後はその検証にすすむことが今後の課題となる。},
 title = {GPUへの完全オフロード化によるTSQRの高速化に関する研究},
 year = {},
 yomi = {タムラ, リョウヤ}
}