GPUを用いた疎行列の格納形式による行列ベクトル積の評価 1 コンピュータサイエンス専攻1年 200920710 久保田悠司指導教員高橋大介研究の背景  GPU （Graphics Processing Unit）は個人のPC に搭載されるようになり，身近なものとなっている  GPUの性能は年々上昇し，ピーク演算性能はCPU を上回っている  近年，GPUを汎用な演算に用いるGPGPU （General-Purpose computation on GPU）が注目されている  GPGPU   元々グラフィック演算を専門とするアクセラレータである GPU を，より汎用的で自由度の高い計算に用いること特に，N体問題や連立一次方程式などの科学技術計算によく用いられる 2 研究の目的  科学技術計算に用いられる連立一次方程式の多くは疎行列を対象  反復法で解くため，疎行列ベクトル積の性能が重要  疎行列は零が多いため，それを省略して格納  格納形式には様々な種類があり，行列ごとに最適な格納形式は異なる  GPU上での疎行列ベクトル積の高速化  格納形式を変換してから疎行列ベクトル積を行う  今回はその第一歩として，を実装し，性能を評価する GPU上で各格納形式 3 GPUアーキテクチャ(Tesla C1060)  複数のコアを搭載したメニーコアプロセッサ  それぞれのコアでスレッドを同時に実行できる  今回は，共有メモリは使用しないグローバルメモリ（4GB）ストリーミングプロセッサ倍精度ユニットストリーミングマルチプロセッサ（SM） SP SP SP SP SP SP SP SP DP 共有メモリ（16KB） 4 CUDA(Compute Unified Device Architecture)  NVIDIA社が提供している統合開発環境  C言語と同様の記述が可能  GPU上でのプログラムはスレッド単位で実行される  CUDAにおけるメモリ参照    32バイト，64バイト，128バイトごと連続するスレッドで連続するメモリ領域にアクセスするほうが効率が良い参照するメモリの先頭が64バイト，または，128バイト境界でアラインメント（整列）されていると，さらに効率が上がる 5 疎行列の格納形式  CRS（Compressed  4 0  2  0 0 0 6 1 行方向に走査し，零要素を省く 0 2 0 5 1 0 3  0 val： 4 1 2 2 6 3 1 5 非零要素の配列 colind： 1 4 3 1 2 4 2 3 非零要素の列番号 rowptr：  CCS（Compressed  4 0  2  0 0 0 6 1 Row Storage）形式 1 3 4 7 9 上２つの配列での各行の先頭を表す配列 Column Storage）形式列方向に走査し，零要素を省く 0 2 0 5 1 0 3  0 val： 4 2 6 1 2 5 1 3 非零要素の配列 rowind： 1 3 3 4 2 4 1 3 非零要素の行番号 colptr： 1 3 5 7 9 上２つの配列での各列の先頭を表す配列  この2つの形式は格納が容易である 6 疎行列の格納形式（2）  JDS（Jagged Diagonal Storage）形式 1行あたりの非零要素数が多い順に行を並べ替える行方向へ非零要素を詰める 4 0  2  0 0 0 6 1 0 2 0 5 1 0 3  0 4 1  2    2 6 3   1 5  2 6 3 4 1    1 5    2  val： 2 4 1 2 6 1 5 3 非零要素の配列 colind： 1 1 2 3 2 4 3 4 非零要素の列番号 ptr： 1 5 8 9 上２つの配列での各列の先頭を表す配列 perm： 3 1 4 2 元の行列の行番号を表す配列 3 各行の非零要素数の最大値 max： 7 CUDAによる実装 ③ ④ CPU ホストからデデバイスからバイスへホストへ GPU データ転送データ転送プログラムを起動プログラムを実行デバイスメモリ ② CPU上でプログラムを起動デバイスメモリに領域を確保し，ホストメモリからデータを転送するスレッドを生成し，GPU上で動作させるプログラムを実行結果をホストメモリへ転送するホストメモリ ① 8 CUDAを用いた行列ベクトル積（CRS形式） 4 0  2  0 0 0 6 1 0 2 0 5 4 1 2 2 6 3 1 5 colind： 1 4 3 1 2 4 2 3 x： 1 2 3 1 1   4  1  1 4  8 2   6 0 2  3  ＝  ×   ＝  3 2  1  6  2  3  4  26 3        0 4 1  2  5  3     17 val： rowptr： 0 y[0] = val[0] * x[colind[0]-1] + val[1] * x[colind[1]-1] 1 3 4 7 9 1 2 3 4 入力ベクトルの配列 SP 0 SP 1 SP 2 SP 3 SP SP SP SP DP 共有メモリ 9 CUDAを用いた行列ベクトル積（CCS形式） 4 0  2  0 0 0 6 1 0 2 0 5 4 2 6 1 2 5 1 3 rowind： 1 3 3 4 2 4 1 3 x： 1 2 3 1 1  4  1  0   0  1 4  8  0   0   2  3  0  6 0  2  ＋  ＋  ＋   ＝   × ＝ 2  1 6  2  0  3  4  26 3  3               0  4  0 1  2 5  3 0         17 val： colptr： 0 1 3 5 7 9 1 2 3 4 SP 0 SP 1 SP 2 SP 3 SP SP y[rowind[0]-1] 同じアドレスに+= val[0] * x[0] SP SP 書き込むときは y[rowind[1]-1] += val[1] * x[0] 排他制御が必要 DP 入力ベクトルの配列共有メモリ 10 CUDAを用いた行列ベクトル積（JDS形式） 2 6 3 4 1    1 5    2  4 0  2  0 0 0 6 1 0 2 0 5 1 1  0  2  × ＝ 3  3     0  4  val： 2 4 1 2 6 1 5 3 colind： 1 1 2 3 2 4 3 4 ptr： 1 5 8 9 perm： 3 1 4 2 max： 3 x： 0 1 2 3  4  1  1 4  8   6 2  3  ＝   2  1  6  2  3  4  26      1 2  5  3  17 y[perm[0]] = val[0] * x[colind[0]-1] + val[4] * x[colind[4]-1] + val[7] * x[colind[7]-1] SP 0 SP 1 SP 2 SP 3 SP SP SP SP DP 共有メモリ 11 1 2 3 4 入力ベクトルの配列評価  各格納形式での行列ベクトル積の実行速度を計測  計測はGPU上での実行時間のみ   メモリの確保やデータ転送は含めない反復法のように，GPU上で何度も呼び出すアプリケーションを想定  倍精度演算を使用  評価環境 CPU GPU CPU AMD Opteron 2350×2 メモリ 16GB GPU NVIDIA Tesla C1060 メモリ 4GB 理論ピーク性能 78GFLOPS 開発環境 CUDA SDK 2.3 コンパイラ nvcc （-O3） version 2.3 12 評価（2） of Florida Sparse Matrix Collectionから以下の疎行列を用いた  評価ではUniversity Matrix Size 非零要素数非零要素率 tmt_sym 726713 5080961 0.00096% mario002 389874 2097566 0.00138% ldoor 952203 42493817 0.00469% audikw_1 943695 77651847 0.00872% msdoor 415863 19173163 0.01109% F1 343791 26837113 0.02271% s3dkt3m2 90449 3686223 0.04506% x104 108384 8713602 0.07418% crankseg_2 63838 14148858 0.34719% nd24k 72000 28715634 0.55393% 13 評価結果今回用いた疎行列では， JDS形式が高速早 3 GFLOPS 性能 2.5 2 1.5 CRS 1 JDS CCS 0.5 遅 0 CCS形式は他の形式と比べ，疎行列の種類大きな差がある 14 考察  CCS形式が最も低速  それぞれのスレッド間で同じアドレスに書き込む場合に，排他制御を用いているため  JDS形式とCRS形式のちがい   各スレッドのデータへの参照の仕方 JDS形式の方が，連続するスレッドが連続するメモリ領域にアクセスするため，効率が良い  今回の評価では，JDS形式が最も高速 15 関連研究  SILC（Simple Interface for Library Collections） [梶山ら，2005]   行列計算ライブラリインターフェース CPU上で疎行列の格納形式を変更し，行列ベクトル積の高速化を行った  CG on GPU-enhanced Clusters [A.Cevahir， et al，2009]   GPUクラスタ上での共役勾配法の実装異なる格納形式の疎行列ベクトル積を数回実行し，最も高速なものを選択 16 まとめ  CUDAを用いて，3つの格納形式での疎行列ベクトル積を実装し，性能を評価した  評価結果から，今回用いた疎行列ではJDS形式が最も高速であることがわかった  JDS形式では，GPU上で効率の良いメモリ参照を行うことができるからだと考えられる 17 今後の課題  他の疎行列での評価  より多くの疎行列で評価を行い，疎行列と格納形式との関連性を調べたい  他の格納形式の実装  本研究では3つの格納形式で実装し評価を行ったが，他の格納形式での実装，評価を行いたい  各格納形式での行列ベクトル積の高速化  共有メモリの使用や，アラインメントを考慮した実装を行うことで，高速化が可能  最適な格納形式への変換アルゴリズム  入力された疎行列によって，最適な格納形式に変換するアルゴリズムを実現したい 18 ご清聴ありがとうございました 19