理学部情報科学科 金田研究室 指導教官 金田 康正 工藤 誠 メモリ使用量の少ないGCR法の提案 理学部情報科学科 金田研究室 指導教官 金田 康正 工藤 誠
GCR法の特徴 広範囲の非対称問題が解ける 並列性が高い GMRESR法[Vorst,91]の一部として使われている 連立一次方程式の反復解法(Krylov部分空間法)の一つ [Eisenstat, 83] SYMMLQ GMERR Bi-CG QMR CGS Bi-CGSTAB GMRES MINRES GCR CG Method The minimum error approach petrov-Galerkin approach The minimum residual approach Ritz-Galerkin approach Approach Krylov部分空間法の分類 広範囲の非対称問題が解ける 並列性が高い GMRESR法[Vorst,91]の一部として使われている
GCR法の 問題点 計算量が大きい（O(k 2N)の計算が３回） メモリ使用量が大きい（GMRESの約２倍） 計算量大！ メモリ使用量大！
過去の研究 計算量を減らすefficient GCR(eGCR)法が考案された[Yang,95] しかし、依然としてメモリ使用量が大きい という問題は解決されていない！！
提案する２つのアルゴリズム Memory efficient GCR(meGCR)法 Unrolled GCR(uGCR)法
Efficient GCR法 Originalの GCR法 ベクトルuは、過去の分まで覚えておく 各反復で解ｘを ループの外に 出した pの計算が 無くなった ベクトルuは、過去の分まで覚えておく ^
メモリ使用量は既存のアルゴリズムの約半分！ Memory efficient GCR法 覚えておくベクトルはApのみでよい メモリ使用量は既存のアルゴリズムの約半分！ 計算量はeGCR法と同程度 ベクトルuを使用しない ^
Air0はdominantな固有ベクトルの Unrolled GCR法 ループ内で使われている値は、 すべてAir0を使って表すことができる ループの前で、Air0を計算しておく ループ内の計算で必要な(Air0, Ajr0)も 計算しておく Air0はdominantな固有ベクトルの 方向を向いてくるので、 精度の低下が予想される 密行列積（BLAS3）の演算となり、 効率的 ループ内はスカラー計算のみとなる メモリ使用量は meGCRと同じ
計算量の比較 * 1リスタート周期の計算量 dmv dp smv prec bin kmv 2kn 2n 3(k-1) 2k 2k-1 k 計算要素 dmv dp daxpy smv prec bin kmv Dmm 計算量 2kn 2n * GCR 3(k-1) 2k 2k-1 k eGCR 1 meGCR k+1 2 uGCR 4k 注 *は、問題や前処理の 方法によって変わってくる k = リスタート周期(数十～数百) n = 問題サイズ (数万～数百万)
メモリ使用量の比較 2k+3 2 k+3 k+2 5 Vector of length n Buffer of size k 2 GCR eGCR 2 meGCR k+3 uGCR k+2 5 既存の手法の 約半分！ k = リスタート周期(数十～数百) n = 問題サイズ (数万～数百万)
実験環境 計算機: HITACHI SR2201 通信ライブラリ：MPI (Message Passing Interface) （東京大学情報基盤センター） CPU: 300MFlops × 1024PE Main memory: 256MB/PE Communication: 300MB/s 通信ライブラリ：MPI (Message Passing Interface)
Problems Problem 1 Problem 2 Problem3 Toeplitz行列 楕円型偏微分方程式の境界値問題（２次元） 楕円型偏微分方程式の境界値問題（３次元）
meGCR法の実験結果(逐次) 実行時間（秒） リスタート周期32 問題 Problem 1 Problem 2 Problem 3 サイズ 実行時間（秒） リスタート周期32 問題 Problem 1 Problem 2 Problem 3 サイズ 400,000 160,000 64,000 前処理無し GCR 22.8 4860 37.8 eGCR 18.3 3440 27.7 meGCR 17.9 3450 28.7 前処理有り (B-ILU(0)) 21.2 938 21.9 19.8 812 19.9 20.1 825
meGCR法の実験結果（並列、前処理なし） Problem 1 ( n=4,000,000 ) Problem 2 ( n=160,000 ) Problem 3 ( n=512,000 ) リスタート周期はすべて３２
meGCR法の実験結果（並列、B-ILU(0)前処理） Problem 1 ( n=4,000,000 ) Problem 2 ( n=160,000 ) Problem 3 ( n=512,000 ) リスタート周期はすべて３２
uGCR法の実験結果 リスタート周期 8 前処理無し B-ILU(0)前処理 Iteration Time Problem 1 GCR 46 リスタート周期 8 前処理無し B-ILU(0)前処理 Iteration Time Problem 1 (n=400,000) GCR 46 18.5 17 20.3 eGCR 15.4 18.2 meGCR 19.5 uGCR 55 13.5 25 26.7 Problem 3 (n=64,000) 1096 64.8 150 30.6 53.6 29.6 55.7 31.7 1053 43.0 30.1
まとめと考察 GCR法の２つのアルゴリズムを提案した Memory efficient GCR法 Unrolled GCR法 より大きな問題が解ける リスタート周期を大きく 取れるので、収束の悪い 問題が解ける GCR法の２つのアルゴリズムを提案した Memory efficient GCR法 計算量は、既存の方法とほぼ同じ メモリ使用量は、既存の方法の約半分 Unrolled GCR法 計算量、メモリ使用量とも既存の方法より少ない 収束性に問題がなく、実用的！ 精度の問題があるので、今後の研究が必要