QR分解のブロック化２００８年７月１０日応用数理工学特論期末発表深谷猛 QR分解とは？ ◆QR分解 n m A m → Q n × R （直交行列）（上三角行列） ◆応用例 • 最小二乗問題 • 長方行列の特異値分解 • 三重対角化（二重対角化）のブロックアルゴリズム ◆主な計算方法 • グラム・シュミットの直交化 • ハウスホルダー変換今回はこの方法に注目 QTQ = I （単位行列）ハウスホルダー変換によるQR分解 ◆ハウスホルダー変換（直交行列） ◆QR分解への適用 → → → → （直交行列の積⇒直交行列）ハウスホルダーQR分解の問題点 • 行列ベクトル積： • 行列のランク１更新：両方ともLevel-2 BLAS データの再利用性が低いため，計算機の性能が出ない Level-3 BLASを使うためにブロック化を行うハウスホルダー変換のブロック化 ◆compact-WY representation Y T YT 計算コスト： O(ml 2) ◆Level-3 BLASによるハウスホルダー変換の作用 2l 回のLevel-2 BLAS 3回のLevel-3 BLAS ハウスホルダーQR分解のブロック化 ◆Fixed-size Blocking （LAPACKで使用されている手法）入力行列を幅 l のブロックに分割 1 2 3 → 1 2 3 l l l （ⅰ）ブロック内のQR分解従来（非ブロック化）のアルゴリズム 1 → 1 Level-2 BLAS （ⅱ）compact-WY representationの計算 Level-2 BLAS （ⅲ）compact-WY representationの作用 2 3 → 2 3 Level-3 BLAS QR分解のブロック化におけるポイント ◆ブロック化による高速化の原理 Lv.2 全体の計算量は増加（compact-WY representationの計算） WY Level-3 BLASの部分で時間短縮 Lv.3 計算時間両者ともブロック幅に依存 ◆様々なブロック化方法 • Variable-size Blocking • Recursive Blocking • 複数のブロック化方法の組合せ（ハイブリッド型）計算環境や問題サイズに合ったブロック化が望ましい計算量数値実験について ◆実験方法 • 自作プログラム同士（非ブロック化とブロック化） • LAPACKのDGEQR2（非ブロック化）とDGEQRF（ブロック化）それぞれ行列サイズを変えて，QR分解の実行時間を測定（※自作のブロック化プログラムはブロック幅を変化させて測定）高速化率 = 非ブロック化での実行時間 / ブロック化での実行時間 ◆実験環境 • CPU ： Opteron（2.0GHz） • BLAS ： AMD ACML Level-2 BLASとLevel-3 BLASの性能比較  DGEMV (Level-2 BLAS) ： n × n 行列と n 次元ベクトルの積 MFLOPS  DGEMM (Level-3 BLAS) ： n × n 行列と n × n 行列の積 4000.0 3500.0 3000.0 2500.0 6～7倍程度の性能差 2000.0 1500.0 1000.0 500.0 0.0 250 500 750 1000 1250 1500 1750 2000 2250 2500 2750 3000 n ブロック化による高速化率の評価 ◆自作プログラム行列サイズ実行時間（秒）高速化率非ブロック化ブロック化ブロック幅 1000×1000 3.84 0.54 30 7.04 3000×1000 22.7 2.43 40 9.33 3000×3000 174 13.4 60 12.96 ◆LAPACKのルーチン実行時間（秒）行列サイズ高速化率非ブロック化ブロック化（DGEQR2）（DGEQRF） 1000×1000 3.13 0.51 ー 6.09 3000×1000 13.3 1.99 ー 6.69 3000×3000 89.8 11.7 ー 7.67 ブロック幅ブロック幅による実行時間の変化（自作プログラムを使用）実行時間（秒）（サイズ： 3000×1000） 4.0 行列サイズが小さく，Level3 BLASの性能がでない 3.5 3.0 2.5 best 2.0 1.5 Level-3 BLAS以外の演算量の増加 1.0 （ブロック内QR分解 & WY representation計算） 0.5 0.0 10 20 30 40 50 60 ブロック幅 70 80 90 100 行列サイズによる高速化率の変化高速化率 14.0 LAPACK 12.0 自作プログラム 10.0 8.0 6.0 BLASの性能差と同程度 4.0 2.0 0.0 250 500 750 1000 1250 1500 1750 2000 2250 2500 2750 3000 行列のサイズ（正方行列）まとめ • ハウスホルダー変換によるQR分解のブロック化を行った． • compact-WY representationを用いてブロック化を行うことで，Level-3 BLASを使うことが可能になった． • 自作プログラムを用いた数値実験の結果，最大で13倍程度の高速化を確認できた． • LAPACKのルーチンを用いた数値実験の結果，BLASの性能差と同程度の高速化率が確認できた． (補足)QR分解のアルゴリズム ◆non-blocking (補足)QR分解のアルゴリズム ◆fixed-size blocking