1
2
はじめに n 目的 4倍精度演算より高速な3倍精度演算を実現する l 倍精度では足りないが4倍精度は必要ないケースに欲しい l 4倍精度に比べてデータサイズが小さい Ø 少なくともメモリ律速な計算では4倍精度よりデータ 転送時間を減らすことが可能 Ø PCIeやノード間通信がボトルネックとなりやすい GPUクラスタ環境に有効か n 研究概要 l DD型4倍精度演算 DD演算 に基づく3倍精度演算 Ø D+S型 D+I型3倍精度浮動小数点フォーマット Ø DD演算を用いた3倍精度演算 l Level1-3のBLASルーチンにおける性能評価 3
DD演算 n DD型4倍精度演算 DD演算 l Dekker(1971)の手法に基づく l Baileyらの実装が有名 QDライブラリ l 倍精度型2個で4倍精度型を表現する Double Double l 2桁の筆算方式のアルゴリズム 倍精度浮動小数点演算の みで構成される Higher-part (binary64) DD-type Quadruple Precision 52#bits Lower-part (binary64) 52#bits 104#bits 4
D+S型3倍精度 n DD型4倍精度 Double Double, 指数部11bit+仮数部104bit Higher-part (binary64) Lower-part (binary64) 52#bits DD-type Quadruple Precision 52#bits 104#bits n D+S型3倍精度 Double+Single, 指数部8bit+仮数部75bit Higher-part (binary64) D+S type Triple Precision 8#bits Lower-part (binary32) 8#bits 23#bits 52#bits 75#bits l DD演算と同一のアルゴリズムを使用し 下位桁の計算の一 部に単精度演算を用いる D+S演算を考えた Ø GPUでは単精度演算が倍精度演算より高速 l しかし実際にはキャストが多発しDD演算より低速となった 5
3倍精度演算 n DD演算を用いてD+S型を計算 l DD演算より高速な3倍精度演算は不可能であったため3倍 精度型によるメモリアクセス時間の節約効果のみに着目 l グローバルメモリ上の3倍精度データをレジスタ上で4倍 精度 DD型 に変換し DD演算を用いて計算する FPU 6
D+S型の問題点 n DD型4倍精度 Double Double, 指数部11bit+仮数部104bit Higher-part (binary64) Lower-part (binary64) 52#bits DD-type Quadruple Precision 52#bits 104#bits n D+S型3倍精度 Double+Single, 指数部8bit+仮数部75bit Higher-part (binary64) D+S type Triple Precision 8#bits Lower-part (binary32) 8#bits 23#bits 52#bits 75#bits Ø D+S型はDD型の下位部 倍精度型 を単精度型に格納 Ø 指数部が8bitに制限されてしまう問題があった 7
D+I型3倍精度 n DD型4倍精度 Doubled Double, 指数部11bit+仮数部104bit Higher-part (binary64) Lower-part (binary64) 52#bits DD-type Quadruple Precision 52#bits 104#bits n D+I型3倍精度 Double+Integer, 指数部11bit+仮数部72bit Higher-part (binary64) D+I type Triple Precision Lower-part (32-bit integer) 20#bits 52#bits 72#bits Ø DD型の下位部 倍精度型 の上位32bitを32bit整数型に 格納 ビット列をそのままコピー Ø 共用体とビット演算で実装する 8
D+I型における丸め処理 n DD型 D+I型変換時の丸め処理 l DD型の下位部 倍精度型 の上位32bitを32bit整数型に そのまま格納すると0への丸め 切り捨て になる l 最近接偶数丸めを実現する処理を実装 host device forceinline void Waos_to_T2soa_rn (const cuddreal dd, double &d, int32_t &i){ union double_int64 u; int64_t odd, border; d = dd.x; u.double_ = dd.y; 0への丸め 切り捨て i = (int32_t)(u.int64_ >> 32); odd = u.int64_ & 0xFFFFFFFF; border = 0x80000000; if (odd < border){ 最近接偶数丸め } else if (odd > border) { i++; } else { if (i&1 == 1) i++; } }; 9
BLASへの適用と性能評価 n BLASへの適用 l Level-1: AXPY (y = αx + y) l Level-2: GEMV (y = αax + βy) l Level-3: GEMM (C = αab + βc) n 性能評価 l Tesla M2050 (ECC-enabled) l CUDA 4.1 n Byte/Flop比による性能予測 l AXPYとGEMVは3倍 4倍精度でもメモリ律速 Ø 3倍精度は単精度の3倍 4倍精度は単精度の4倍の実行 時間となる l GEMMは演算律速 10
AXPY (y=αx+y) (Tesla M2050) AXPY (Relative Execution Time) 4.5 4倍精度 Relative Execution Time 4 3.5 3倍精度 3 2.5 倍精度 2 1.5 単精度 1 0.5 0 10000 Single (CUBLAS) Double (CUBLAS) D+S-Triple 100000 N 1e+06 1e+07 D+I-Triple DD-Quadruple メモリ律速 計算時間はデータサイズ 精度 に比例 11
GEMV (y=αax+βy) (Tesla M2050) GEMV (Relative Execution Time) 5 Relative Execution Time 4.5 4倍精度 4 3.5 3倍精度 3 2.5 倍精度 2 1.5 単精度 1 0.5 0 0 1000 2000 3000 Single (CUBLAS) Double (CUBLAS) D+S-Triple 4000 N 5000 6000 7000 8000 D+I-Triple DD-Quadruple メモリ律速 計算時間はデータサイズ 精度 に比例 12
GEMM (C=αAB+βC) (Tesla M2050) GEMM (Relative Execution Time) 4倍精度 3倍精度 30 Relative Execution Time 25 20 15 演算律速 3倍精度 4倍精度ともに同 一のDD演算を用いているため計算時間 は変わらない 10 5 0 倍精度 単精度 0 500 Single (CUBLAS) Double (CUBLAS) D+S-Triple 1000 N 1500 2000 D+I-Triple DD-Quadruple 13
まとめ n 結論 l 計算がメモリ律速となるケース AXPY, GEMV において 4倍精度演算より高速な3倍精度演算が実現できた Ø 単精度比で3倍精度は3倍 4倍精度は4倍の実行時間 l 演算律速となるケース GEMM では3倍精度と4倍精度 の性能はほぼ等しくなる Ø 内部は同一のDD演算を用いているため l 今回の事例ではD+S型とD+I型の性能はほぼ同一 指数部 と仮数部長のトレードオフを考慮して使い分けるべき Ø D+S 指数部8bit+仮数部75bit Ø D+I 指数部11bit+仮数部72bit n 今後の課題 l 実アプリケーションにおいて3倍精度が有効なケースを示 す GPUクラスタ環境など 14
15
はじめに 1/2 n 高精度演算の需要 l 悪条件問題や 高い精度の解を得るためなど より正確に計算 するために用いられる l 高精度演算を行うと一般に計算時間は増大する しかし反復解 法ではそうであるとは限らない n 反復解法と高精度演算 l 求解までの計算時間 1反復あたりの実行時間 反復回数 l 丸め誤差の影響により 収束までに必要な反復回数が理論的に 必要とされる回数より増加することがある l CG法などのクリロフ部分空間法では 高精度演算を用いること で丸め誤差が減少することにより 反復回数を減らせるケース がある [Hasegawa2003]など 高精度演算を用いることで1反復あたりの実行時間がx倍に増 えても 反復回数が1/x倍より少なくなれば 求解までのトー タルの計算時間は減らせる 高精度演算を高速化に使える 16
はじめに 2/2 n GPUにおける4倍精度演算の疎行列反復解法への適用 l 4倍精度BiCGStab 前処理なし を実装し倍精度版と性能比較 l 4倍精度演算を用いることで1反復あたりの実行時間が2倍に増 えても 反復回数が1/2倍より少なくなれば 求解までのトータ ルの計算時間は減らせる Ø 4倍精度演算の理論演算コストは倍精度の約20倍であるが AXPY, GEMVはメモリ律速となり実行時間は倍精度の約2倍 Ø BiCGStab法を構成するベクトル演算はSpMVがLevel-2であ る以外はLevel-1演算でありメモリ律速となる可能性が高い 実際に倍精度の代わりに4倍精度を用いることで疎行列反復解法 を高速化できるケースはあるのか 17
実装 n 実装の方針 l ベクトル演算単位でGPUのカーネル関数にする Ø スカラ値の計算はCPUで行う l 倍精度版と4倍精度版は四則演算の精度のみが異なる それ以外 の理由による演算結果の違いが生じないように起動スレッド数 などを含めプログラムの計算内容は倍精度 4倍精度で共通 Ø ただし収束判定のノルム計算は倍精度で足りるため 倍精 度 4倍精度ともにCUBLASのDNRM2を使用 Ø 倍精度版の性能はCUBLAS, cusparse使用の場合と互角 l SpMV CRS形式 CRS-vector[Bell2008]に基づく実装 n 4倍精度化 l DD型4倍精度演算を使用 l すべてのデータが4倍精度 入力行列も4倍精度とする l メモリ上の4倍精度データの配置はSoA Structure of Arrays レイアウト DD型の上位 下位部を格納する倍精度配 列を個々に確保する 18
性能評価 n 評価環境 l GPU NVIDIA Tesla M2050 l CPU Xeon E5630 2.53GHz, 4-core 2 l Software CentOS6.3, CUDA5.0, gcc 4.4.6 (-O3), nvcc 5.0 (-O3 arch sm_20) n 評価方法 l 倍精度 4倍精度BiCGStabの収束までの実行時間を測定 Ø 反復部分のみを測定 PCIeデータ転送時間は含まない l 収束の定義 b = (1... 1)T, x0 = (0... 0)Tで 収束条件ε = 1e-12 反復回数の上限10,000回 l 実験に用いた疎行列はフロリダ大の疎行列コレクションから Ø 208種類の行列のうち倍精度で収束したもの 51種類 Ø 4倍精度で倍精度よりも反復回数が減少したもの 30種類 Ø そのなかからベストケース8種類の結果を示す 19
倍精度に対する4倍精度BiCGStab法 相対実行時間 相対反復回数 [4倍精度/倍精度] (Tesla M2050) [4倍精度/倍精度] 2.5! 2.0! 1.5! 収束までの時間 1反復あたりの実行時間 反復回数 1.0! 0.5! 0.0! u 収束までの時間 右8種類の行列は4倍精度を用いることで 倍精度よりも収束までの時間が短くなった u 1反復あたりの実行時間 4倍精度が倍精度の約1.0-2.2倍 平均約 1.5倍 右側の行列は4倍精度と倍精度の 差が小さい傾向にある u 反復回数 右側の行列は4倍精度を用いることによる 反復回数の減少量が大きい傾向にある20
行列の特性 n 4倍精度で倍精度より高速になった8種類の行列の特性 l 問題サイズが小さいか非ゼロ要素率が小さい l そもそもGPU向きではない問題であると考えられる Matrix Kind Rows Non- zeros Circuit simulamon problem 2395 17319 Circuit simulamon problem 11341 98523 Circuit simulamon problem 1814 14579 sequence Circuit simulamon problem circuit_2 4510 21199 Subsequent circuit dc2 116835 766396 simulamon problem Counter- example problem Pd 8081 13036 ElectromagneMcs problem dw2048 2048 10114 TSOPF_RS_b9_c6 Power network problem 7224 54082 add20 coupled adder_trans_01 Non- zeros [%] Number of Itera;ons DP QP QP/DP 0.302 822 743 0.077 3916 2474 0.443 299 205 0.90 0.63 0.69 0.104 741 469 0.006 2539 1607 0.63 0.63 0.020 229 161 0.241 2495 1774 0.104 1319 488 0.70 0.71 0.37 21
実行時間の内訳 1反復あたりの実行時間の内訳 4倍精度 100%! 80%! その他 DNRM2 60%! 40%! 20%! DOT SpMV 0%! l BiCGStab法では一般にSpMVが実行時間の多くを占めることが多い l DOTやDNRM2が支配的となるケースがある 22
SpMV DOTの相対実行時間 SpMV DOTの相対実行時間 [4倍精度/倍精度] SpMV! 2.5! DOT! 2.0! 1.5! 1.0! 0.5! 0.0! l 相対実行時間は1-2倍程度 Ø SpMV 約1.4-2.5倍 DOT 約1.3-2.1倍 l 4倍精度の実行時間が倍精度の2倍以下になるケースがある Ø 問題サイズが小さい場合カーネル起動時間などがボトルネック Ø SpMVは精度によらずインデクス行列の取り扱いコストが一律 23
GFlops 22! 20! 18! 16! 14! 12! 10! 8! 6! 4! 2! 0! Flops Performance of SpMV (Tesla K20) 倍精度 (DP) 4 倍精度 (QP) 0! 50! 100! 150! 200! Matrix Number 倍精度 SpMV の性能順にソート
まとめ n GPUにおける4倍精度BiCGStab法 l 1反復あたりの計算時間は倍精度の2倍程度 Ø 2倍以下となるケースがある l 4倍精度を用いることで倍精度よりも収束までの計算時間が短く なるケースがあった l 疎行列反復解法の高速化にあたっては 問題によって適切な解 法 前処理の選択とともに4倍精度の使用も検討の余地がある n 今後の課題 l 前処理 : 前処理を行うと性能に関して議論が変わる可能性がある Ø 倍精度 並列性の低い前処理 vs 4倍精度 l 他の精度 3倍精度など 混合精度 l GPUクラスタ環境における実装と評価 25