AllReduce アルゴリズムによる QR 分解の精度について 山本有作 森大介 張紹良 名古屋大学 大学院工学研究科 計算理工学専攻 張研究室 行列・固有値の解法とその応用 第６回研究会 2008/11/26 目次 QR分解 QR分解の並列化アルゴリズム 従来のハウスホルダー変換 AllReduceアルゴリズム 精度に関する数値実験 理論的誤差解析 まとめと今後の課題 2 QR分解 行列 A ∈Rm×n を Q ∈Rm×n と R ∈Rn×n に分解する Q: 列直交行列 R: 上三角行列 n m A = Q R 応用例 m≫n 最小二乗問題 特異値分解の前処理 二重対角化・三重対角化のブロック化アルゴリズム 電子状態計算 大規模問題に対する高速かつ高精度な手法が必要 3 QR分解 グラムシュミットの直交化法 並列化に向く（古典的グラムシュミット法） 得られるQ の直交性は行列の条件数に依存 ハウスホルダーQR分解 4 計算が逐次的 得られるQ の直交性が良い （従来の）ハウスホルダー変換 あるベクトル x を任意のベクトル y に変換する H x 0 A H1 作成 H2 作成 0 H1 y u x x 2 e1 → u を正規化 (I: 単位行列) H I 2uuT H 1 H T H 0 0 H2 作用 作用 H N ・・・ H3 H 2 H1 A R QT 各ステップの計算は逐次的なため 並列化（高速化）が困難 5 Q H1H 2 H3 ・・・ H N A = QR 並列化時に考えるべき点 プロセッサ間の通信量 通信量が大きいと（計算以外の）コストが増加 通信回数 通信回数が多くても（計算以外の）コストが増加 （通信にかかる全時間） = （データ通信時間）+（立ち上げ時間） tcomm ≪ tsetup 通信回数の少ないアルゴリズムが必要 以下，分散メモリ型の並列計算機を考える 6 ハウスホルダー変換の並列化 (2並列) n 行列を上下に二分割して 各プロセッサにデータを持たせる。 u x x 2 e1 → u を正規化 (I: 単位行列) H I 2uu 1 T H H H m T H A 0 0 I. u の生成(||x||2 の計算) II. H = I - 2uuT の作用 各ステップ 2回 communication 0 communication 7 update 合計 2N 回 AllReduceアルゴリズム*（Langou 2007） n : それぞれ独立に計算可能 A1 m Q1 R1 R1 A A2 Q2 R2 R communication m≫n QR分解はすべて ハウスホルダー変換で行う • m/2×n の行列 2回 • 2n×n の行列 1回 合計 1回 A Q1 O O Q2 8 R2 ~ Q ~ Q R Q R このアルゴリズムは再帰的に利用可能 再帰段数が増えるにつれ，計算量は従 来のハウスホルダー変換に比べて増加 * TSQR（Tall and Skinny QR）アルゴリズムとも呼ばれる 比較 従来の ハウスホルダー変換 手法 計 算 量 逐次 計算 2 3 2MN N OMN 3 2MN 2 2 N 3 OMN 並列 計算 1 3 MN N OMN 3 8 3 MN N OMN 3 2N 1 1 2 N N 2 1 2 N 2 通信回数 通信量 9 AllReduce アルゴリズム 2 2 2 計算量と計算時間（逐次計算） 計算量 8 2 10 3 2MN N 3 OMN QR分解の計算時間 k 1.5 2 k は再帰の段数 計算時間 (s) 1 0.5 0 0 1 2 3 4 5 再帰の段数(k ) ハウスホルダー変換 CPU: Xeon 2.80GHz メモリ: 4GB 行列サイズ: 4000×100 10 本研究の目的 並列性能についてはすでに多くの検証がなされている （Demmel et al. 2008，村上 2008） 精度についてはまだ詳細な報告がない AllReduce アルゴリズムの精度を実験的・理論的に評価する 11 演算量の増加が精度にどのような影響を及ぼすか？ 数値実験概要 精度の指標 直交性 残差 実験項目 従来のハウスホルダー変換と 2分割のAllReduceアルゴリズムの精度比較 || QTQ - I ||F || A - QR ||F 行列サイズ（m, n）依存性 AllReduceの再帰段数を変えたときの精度比較 計算機環境 12 CPU Xeon 2.80GHz メモリ 4GB コンパイラ GNU C/C++ Compiler 数値実験１ 乱数行列 A ∈Rm×n を Q ∈Rm×n と R∈Rn×n へ分解 1. 2. 従来のハウスホルダー変換 AllReduceアルゴリズム 再帰の段数は1で固定(2分割) 行列サイズ m I 4000 II 1000~5000 13 n 100~500 100 実験結果I（n依存性，m=4000） 残差評価 || A - QR ||F Qの直交性 || QTQ - I ||F 1.00E-12 1.00E-11 1.00E-13 1.00E-12 1.00E-14 1.00E-13 100 200 300 400 N 500 100 200 300 400 N 従来のハウスホルダー変換: 青 AllReduceアルゴリズム: 赤 AllReduce アルゴリズムは，従来法よりむしろ精度が良い 14 500 実験結果II（m依存性，n=100) Qの直交性 || QTQ - I ||F 残差評価 || A - QR ||F 1.00E-12 1.00E-11 1.00E-13 1.00E-12 1.00E-14 1.00E-13 1000 2000 3000 4000 M 5000 1000 2000 3000 4000 M 従来のハウスホルダー変換: 青 AllReduceアルゴリズム: 赤 AllReduce アルゴリズムは，従来法よりむしろ精度が良い 15 5000 数値実験２ 乱数行列 A ∈Rm×n を Q ∈Rm×n と R∈Rn×n へ分解 1. 2. 従来のハウスホルダー変換 AllReduceアルゴリズム 再帰の段数は最大5 (32分割) 行列サイズ: 4000×100 16 実験結果（再帰段数依存性） 残差評価 || A - QR ||F Qの直交性 || QTQ - I ||F 1.00E-12 1.00E-11 1.00E-13 1.00E-12 1.00E-14 1.00E-13 0 1 2 3 再帰の段数 ハウスホルダー変換 4 5 0 1 2 3 再帰の段数 ハウスホルダー変換 再帰段数を増やすことで，（この範囲では）精度が向上する 17 4 5 疑問点 AllReduceアルゴリズムでは，演算量が増加したにもか かわらず，精度がむしろ向上しているのはなぜか？ ＋要因： 計算を小さい行列のQR分解に帰着させることで， 内積のベクトル長が減少 ー要因： ２段階のQR分解により，誤差の蓄積が増大 それぞれの影響を定量的に評価するため，理論的解析が 必要 18 理論的誤差解析 目標 AllReduce型QR分解における後退誤差の評価 ： 計算で得られた上三角行列 ： 分解で使ったﾊｳｽﾎﾙﾀﾞｰ変換を無限精度で蓄積した直交行列 を評価 計算で得られる Q の直交性の評価 ：計算で得られた Q を評価 AllReduceアルゴリズム（再掲） 解析に便利なように記法を変更 上付き添字は分解のステージを表す 下付き添字は行列の上半分／下半分を現す ここではまだ誤差のことは考えない n A1 m (1) Q(1) R 1 1 A (1) R1 (1) A2 (1) Q2 R2(1) R2 R(1) ~(2) Q R Q 後退誤差解析のための図式 backward error Q(1) exact Q(1) exact Q(2) exact computed backward error computed AllReduceアルゴリズム全体の後退誤差 各ステップでの後退誤差の式 より， . AllReduceアルゴリズム全体での後退誤差 後退誤差の評価 右辺の各項をそれぞれ評価する。 の評価 (I) 第１ステージの２個のQR分解の後退誤差 により を定義すると， . これより， . の評価 (II) ハウスホルダー変換に対する誤差評価（Higham, 1996）より， ただし， . （ ：マシンイプシロン） これより， . の評価 同様に，ハウスホルダー変換に対する誤差評価の結果より， 次の式が成り立つ。 (∵ Q(1)は正確な直交行列) (前ページの結果より) AllReduceアルゴリズム全体の後退誤差 以上より，AllReduceアルゴリズム全体の後退誤差は次のよう に評価できる。 のとき，これは通常のハウスホルダーQR分解の後退 の半分程度の大きさとなる。 誤差 AllReduceアルゴリズムの高精度性に対する一つの説明 計算で得られる Q の直交性の評価 同様に，Q の直交性の誤差は次のように評価できる。 のとき，これは通常のハウスホルダーQR分解におけ る直交性の誤差 の半分程度の大きさとなる。 まとめと今後の課題 まとめ ハウスホルダーQR分解のためのAllReduceアルゴリズムの精 度を実験的・理論的に評価した AllReduceアルゴリズムでは，従来のハウスホルダー変換に 比べ，誤差がむしろ小さくなる傾向が見られた 理論的誤差解析により，これを支持する結果を得た 今後の課題 28 再帰的に適用した場合の理論的誤差解析 並列環境での性能評価 二重対角化・三重対角化アルゴリズムへの組み込みと精度 評価
© Copyright 2024 ExpyDoc
