GPUを用いた疎行列の格納形式による行列ベクトル積の評価 コンピュータサイエンス専攻2年 200920710　久保田　悠司 指導教員　　高橋　大介

研究の背景 GPU （Graphics Processing Unit）は個人のPC に搭載されるようになり，身近なものとなっている GPUの性能は年々上昇し，ピーク演算性能はCPU を上回っている 近年，GPUを汎用な演算に用いるGPGPU （General-Purpose computation on GPU）が注 目されている GPGPU 元々グラフィック演算を専門とするアクセラレータであるGPU を，より汎用的で自由度の高い計算に用いること 特に，N体問題や連立一次方程式などの科学技術計算によく用いられる

研究の目的 科学技術計算に用いられる連立一次方程式の多 くは疎行列を対象 疎行列は零が多いため，それを省略して格納 反復法で解くため，疎行列ベクトル積の性能が重要 疎行列は零が多いため，それを省略して格納 格納形式には様々な種類があり，行列ごとに最適 な格納形式は異なる GPU上での疎行列ベクトル積の高速化 格納形式を変換してから疎行列ベクトル積を行う 今回はその第一歩として， GPU上で各格納形式 を実装し，性能を評価する

GPUアーキテクチャ(Tesla C1060) 複数のコアを搭載したメニーコアプロセッサ それぞれのコアでスレッドを同時に実行できる 今回は，共有メモリは使用しない SP DP 共有メモリ （16KB） グローバルメモリ （4GB） ストリーミング プロセッサ 倍精度 ユニット マルチプロセッサ （SM）

CUDA(Compute Unified Device Architecture) NVIDIA社が提供している統合開発環境 C言語と同様の記述が可能 GPU上でのプログラムはスレッド単位で実行さ れる CUDAにおけるメモリ参照 32バイト，64バイト，128バイトごと 連続するスレッドで連続するメモリ領域にアクセスするほうが効率が良い 参照するメモリの先頭が64バイト，または，128バイト境界でアラインメント（整列）されていると，さらに効率が上がる

疎行列の格納形式 CRS（Compressed Row Storage）形式 行方向に走査し，零要素を省く CCS（Compressed Column Storage）形式 列方向に走査し，零要素を省く この2つの形式は格納が容易である val： 4 1 2 6 3 5 非零要素の配列 colind： 非零要素の列番号 7 9 rowptr： 上２つの配列での各行の先頭を表す配列 val： 1 3 4 2 6 5 非零要素の配列 rowind： 非零要素の行番号 7 9 colptr： 上２つの配列での各列の先頭を表す配列

1行あたりの非零要素数が多い順に行を並べ替える 疎行列の格納形式（2） JDS（Jagged Diagonal Storage）形式 1行あたりの非零要素数が多い順に行を並べ替える 行方向へ非零要素を詰める val： 2 4 1 6 5 3 非零要素の配列 colind： 非零要素の列番号 8 9 ptr： 上２つの配列での各列の先頭を表す配列 perm： 元の行列の行番号を表す配列 max： 各行の非零要素数の最大値

CUDAによる実装 CPU上でプログラムを起動 デバイスメモリに領域を確保し，ホストメモリか らデータを転送する スレッドを生成し，GPU上で動作させるプログ ラムを実行 結果をホストメモリへ転送する ホストメモリ CPU GPU デバイスメモリ デバイスからホストへ データ転送 ホストからデバイスへ データ転送 プログラムを起動 プログラムを実行

CUDAを用いた行列ベクトル積（CRS形式） 1 2 3 1 2 3 SP ＝ SP DP 共有 メモリ × ＝ y[0] = val[0] * x[colind[0]-1] + val[1] * x[colind[1]-1] val： 4 1 2 6 3 5 colind： 7 9 rowptr： 1 2 3 4 x： 入力ベクトルの配列

CUDAを用いた行列ベクトル積（CCS形式） 1 2 3 1 2 3 SP ＝ SP DP 共有 メモリ × ＝ ＋ 同じアドレスに 書き込むときは 排他制御が必要 y[rowind[0]-1] += val[0] * x[0] y[rowind[1]-1] += val[1] * x[0] val： 4 2 6 1 5 3 rowind： 7 9 colptr： 1 2 3 4 x： 入力ベクトルの配列

CUDAを用いた行列ベクトル積（JDS形式） 1 2 3 1 2 3 SP SP DP 共有 メモリ × ＝ ＝ val： 2 4 1 6 5 3 colind： 8 9 ptr： perm： max： y[perm[0]] = val[0] * x[colind[0]-1] + val[4] * x[colind[4]-1] + val[7] * x[colind[7]-1] 1 2 3 4 x： 入力ベクトルの配列

評価 各格納形式での行列ベクトル積の実行速度を計測 計測はGPU上での実行時間のみ 倍精度演算を使用 評価環境 メモリの確保やデータ転送は含めない 反復法のように，GPU上で何度も呼び出すアプリケーションを想定 倍精度演算を使用 評価環境 CPU AMD Opteron 2350×2 メモリ 16GB GPU NVIDIA Tesla C1060 4GB 理論ピーク性能 78GFLOPS 開発環境 CUDA SDK 2.3 コンパイラ nvcc （-O3） version 2.3

評価（2） 評価ではUniversity of Florida Sparse Matrix Collectionから以下の疎行列を用いた 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%

評価結果 今回用いた疎行列では， JDS形式が高速 早 性能 CCS形式は他の形式と比べ， 大きな差がある 遅

考察 CCS形式が最も低速 JDS形式とCRS形式のちがい 今回の評価では，JDS形式が最も高速 それぞれのスレッド間で同じアドレスに書き込む場合に，排他制御を用いているため JDS形式とCRS形式のちがい 各スレッドのデータへの参照の仕方 JDS形式の方が，連続するスレッドが連続するメモリ領域にアクセスするため，効率が良い 今回の評価では，JDS形式が最も高速

連立一次方程式の求解による評価 連立一次方程式 反復法 CRS形式とJDS形式について評価 　　は疎行列、　　は　　の要素がすべて1となるようなベクトルを用いた 反復法 何度も計算を反復させることで理想的な値に近づけて行く Bi-CGSTAB法を用い，前処理は行わない 反復の上限は5０００回 CRS形式とJDS形式について評価 JDS形式については，CRS形式で入力し，反復法を行う前にJDS形式に変換する 本研究の最終目的は，入力された疎行列によって 最適な格納形式に変換してから計算を行うため

連立一次方程式の求解による評価結果 遅 早 反復回数が少ないため，変換に要する時間の割合が多い CRS形式と同等以下の実行時間 CRS形式に対するJDS形式の実行時間の割合

関連研究 SILC（Simple Interface for Library Collections） [梶山ら，2005] 行列計算ライブラリインターフェース CPU上で疎行列の格納形式を変更し，行列ベクトル積の高速化を行った CG on GPU-enhanced Clusters [A.Cevahir，et al，2009] GPUクラスタ上での共役勾配法の実装 異なる格納形式の疎行列ベクトル積を数回実行し，最も高速なものを選択

まとめ CUDAを用いて，3つの格納形式での疎行列 ベクトル積を実装し，性能を評価した 　 ベクトル積を実装し，性能を評価した 評価結果から，今回用いた疎行列ではJDS形式が 最も高速であることがわかった JDS形式では，GPU上で効率の良いメモリ参照を行 うことができるからだと考えられる 連立一次方程式の求解による評価では，反復回数 によって最適な格納形式に違いが生じることがわ かった

今後の課題 他の疎行列での評価 他の格納形式の実装 各格納形式での行列ベクトル積の高速化 最適な格納形式への変換アルゴリズム より多くの疎行列で評価を行い，疎行列と格納形式との関連性を調べたい 他の格納形式の実装 本研究では3つの格納形式で実装し評価を行ったが，他の格納形式での実装，評価を行いたい 各格納形式での行列ベクトル積の高速化 共有メモリの使用や，アラインメントを考慮した実装を行うことで，高速化が可能 最適な格納形式への変換アルゴリズム 入力された疎行列によって，最適な格納形式に変換するアルゴリズムを実現したい

ご清聴ありがとうございました

audikw_1 tmt_sym msdoor mario002 ldoor F1

s3dkt3m2 x104 crankseg_2 nd24k

CPUでの性能評価 CPU1コアでの実行速度