疎行列ベクトル積における格納形式の自動最適化 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)  複数のコアを搭載したメニーコアプロセッサ  それぞれのコアでスレッドを同時に実行できるストリーミングマルチプロセッサ（SM）グローバルメモリ（4GB）ストリーミングプロセッサ倍精度ユニット SP SP SP SP SP SP SP SP DP 共有メモリ（16KB） 4 CUDA(Compute Unified Device Architecture)  NVIDIA社が提供している統合開発環境  C言語と同様の記述が可能  GPU上でのプログラムはスレッド単位で実行される  CUDAでのメモリ参照    32バイト，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]] + val[1] * x[colind[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 y[rowind[0]] += val[0] * x[0] 同じアドレスに書き込むときは y[rowind[1]] += val[1] * x[0] 排他制御が必要 1 3 5 7 9 1 2 3 4 入力ベクトルの配列 SP 0 SP 1 SP 2 SP 3 SP SP SP SP 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]] + val[5] * x[colind[5]] + val[8] * x[colind[8]] 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 開発環境 CUDA SDK 2.3 コンパイラ nvcc （-O3） version 2.3 12 評価（2） of Florida Sparse Matrix Collectionから以下の疎行列を用いた  評価ではUniversity Matrix Size 非零要素数 mario002 389874 1167685 2.995032 tmt_sym 726713 2903837 3.995851 s3dkt3m2 90449 1921955 21.24905 msdoor 415863 10328399 24.83606 ldoor 952203 23737339 24.92886 F1 343791 13590452 39.53115 audikw_1 943695 39297771 41.64245 x104 108384 5138004 47.40556 crankseg_2 63838 7106348 111.3185 nd24k 72000 14393817 199.9141 1行あたりの非零要素数 13 評価結果 2.5 早 GFLOPS 性能 2 1 0.5 遅 CCS形式では排他制御を行うため低速 1.5 0 CRS JDS 1行あたりの非零要素数が少ないときは CRS形式が高速 1行あたりの非零要CCS 素数が多いときは JDS形式が高速行列の種類少 1行あたりの非零要素数多 14 考察  JDS形式では連続するスレッドが連続するメモリ領域にアクセスするため効率が良い  しかし，1要素を計算する時のメモリ参照の回数が多い  1行あたりの非零要素数が少なくなるとCRS形式でのメモリアクセスの効率が上がる  1行あたりの非零要素数が少ないときはCRS形式の方が実行速度が向上する 15 関連研究  SILC（Simple Interface for Library Collections） [梶山ら，2005]   行列計算ライブラリインターフェース CPU上で疎行列の格納形式を変更し，行列ベクトル積の高速化を行った  CG on GPU-enhanced Clusters [A.Cevahir， et al，2009]   GPUクラスタ上での共役勾配法の実装異なる格納形式の疎行列ベクトル積を数回実行し，最も高速なものを選択 16 まとめ  CUDAを用いて，各格納形式の疎行列ベクトル積を実装し，性能を評価した  評価結果から，1行あたりの非零要素数によって，各格納形式での行列ベクトル積の実行速度に違いが生じる   多いときはJDS形式が高速少ないときはCRS形式が高速  最適な格納形式の選択には，1行あたりの非零要素数を考慮する必要がある 17 今後の課題  他の疎行列での評価  より多くの疎行列で評価を行い，より正確な疎行列と格納形式との関連性を調べたい  他の格納形式の実装  3つの格納形式で実装し評価を行ったが，他の格納形式での実装，評価を行いたい  CCS形式の行列ベクトル積の高速化  CCS形式では排他制御を行うため，低速であったが，排他制御の回数を減らすことで高速化できる  疎行列の格納形式選択アルゴリズムの実現  本研究の目的は，最適な格納形式を動的に選択することであるため，今回の結果を考慮した選択アルゴリズムを実現したい 18 ご清聴ありがとうございました 19