Row Block Packing method (RBP 法 )
5.10 RBP 法の適用可能な疎行列
cant rma10
consph parabolic_fem
pwtk thermal2
af_shell9 F1 nd24k
dielFilterV2real Cube_Coup_dt0
Bump_2911 Queen_4147
UT_Heart1 UT_Heart2 100
101 102 103 104 105 106
Convert time (msec)
CSR RBP-CSR ELL RBP-ELL ELL-R RBP-ELL-R PatComp(1) PatComp(8)
図 5.17: Convert time of each formats
RBP法は既存の疎行列格納方式に対し圧縮を行う手法である．そのため図5.17では CSR，ELL，ELL-Rに比べ，RBP-CSR，RBP-ELL，RBP-ELL-Rの変換時間は長くなっ ている．既存の疎行列格納方式の変換時間から，RBP法を適用した疎行列格納方式の変 換時間を差し引いた時間が，RBP法のオーバヘッドである
しかしながら，既存の疎行列格納方式へのRBP法の適用時間を含めても，RBP法を用 いた疎行列格納方式を使用したGMRESの演算時間は，既存の疎行列格納方式を用いた 演算時間と遜色ない．
RBP-CSRとPatComp(1)への変換時間を比較すると，RBP-CSRの方が平均で1529倍 の高速化を達成している．またRBP-CSRと並列化を行ったPatComp(8)の変換時間を比 較すると，RBP-CSRの方が平均で10倍高速な結果となった．RBP-ELLやRBP-ELL-R
とPatCompへの変換時間を比較しても，RBP法の変換は非常に高速な結果となってい
る．よってRBP法が目的として掲げていたメモリ使用量を削減しながらも高速な変換手 法を達成していることを確認した．
た場合，各時間ステップごとに非ゼロ要素の位置情報を含め更新が必要となるが，RBP 法では変換が高速であることから更新のコストが非常に少ない．
また反復法の収束までに必要な反復回数が少ない問題にもRBP法は有効である．反復 回数が少なくなることでSpMVに対し変換に要する時間が支配的になることから変換が 高速なRBP法が有効となる．本章でのGMRES評価実験では用いていないが，収束性を 改善するための前処理を反復法と併用するケースが多々ある．反復法の前処理を使用する ことで収束性は大きく改善されることから，反復回数は少なくなる．そのような場合には 変換に要する時間が支配的となることからRBP法が活用できると考える．
次にRBP法を用いて従来の疎行列格納方式よりメモリ使用量が削減可能な条件を検討 する．まずRBP-CSRのメモリ使用量を疎行列内の連続した非ゼロ要素のブロック数を用 いて表すと式（5.4)となる．ここでNconは疎行列内に存在する連続した非ゼロ要素のブ ロック数を表す．N，Nz，Nnonはこれまでと同様に疎行列の行数，非ゼロ要素数，不連 続な非ゼロ要素数である．また値の格納には8byte，その他の要素の格納には4byte必要 と仮定する．
M emU sageRBP−CSR = 4×3(N + 1) + 4×2Ncon+ 8(Nz−Nnon) + 4Nnon+ 8Nnon (5.4) 式（5.4）を用いて従来手法であるCSRよりメモリ使用量を削減可能な条件を式（5.5） に示す．疎行列内の非ゼロ要素を一度参照するだけで，その疎行列がRBP法でメモリ使 用量削減可能か判別することが可能である．
8Nz+ 4Nz+ 4(n+ 1)>4×3(N + 1) + 4×2Ncon+ 8(Nz−Nnon) + 4Nnon+ 8Nnon (5.5)
次にRBP-ELLのモリ使用量を疎行列内の連続した非ゼロ要素の数に着目し表すと式
（5.6)となる．ここでNzperrowは1行あたり連続した非ゼロ要素の値の数（不連続な非ゼ ロ要素の値を除く）．Nconperrow は1行あたり連続した非ゼロ要素のブロック数を表す．
M ax(Nzperrow)，M ax(Nconperrow)は全ての行の内最も大きいNzperrow，Nconperrowの値を 表す．
M emU sageRBP−ELL = 8N ×M ax(Nzperrow) + 2×4N×M ax(Nconperrow)
+8Nnon+ 4Nnon+ 4(N + 1) (5.6) 式（5.6）より，既存手法であるELLよりRBP-ELLのメモリ使用量が少なくなる条件 を式（5.7）に示す．RBP-ELLも疎行列内の連続した非ゼロ要素の数，不連続な非ゼロ 要素の数を調査することでメモリ使用量削減が可能か判別することが可能である．また RBP-ELL-RもRBP-ELLと同様の条件式（5.7）により判別可能である．
8N ×K+ 4N ×K >8N ×M ax(Nzperrow) + 2×4N×M ax(Nconperrow)
+8Nnon+ 4Nnon+ 4(N + 1) (5.7) PatCompとRBP法の使い分けとして，まず式（4.2），式（5.5）と式（5.7）を使用し て対象となる疎行列をそれぞれの疎行列格納方式で格納した際のおおよそのメモリ使用 量を算出し，使用するGPUのメモリ容量に合わせた選択を行う．PatCompのメモリ使用
量の方がRBP-CSRのメモリ使用量より少ない傾向にあるため，PatCompを用いること
でRBP法より大規模な数値シミュレーションを扱うことが可能である．しかしPatComp ではCOOからの変換時間がRBP法に比べ非常に長いことから，シミュレーションの時 間ステップごとにFEMモデルの形状が変化する場合，時間ステップ毎に変換が必要とな り，変換時間が非常に大きくなる．このような場合にはRBP法を選択することで変換時 間がボトルネックとなることを抑制することが可能である．
5.11 おわりに
RBP法はPatCompのボトルネックとなっていた疎行列からの変換時間を短縮するため，
圧縮方法を単純化した手法である．RBP法により変換処理を高速に行うことで，PatComp が適していない時間ステップごとに疎行列の形状が変化する問題に対してもメモリ使用量 の削減を達成することが可能である．
FDMやFEMで生成される疎行列は，ある領域とその隣接する領域からの影響を反映 するため，疎行列には連続した非ゼロ要素が多々出現する．従来の疎行列格納方式では連 続した非ゼロ要素が存在した場合であっても，全ての非ゼロ要素の情報を格納していた．
しかしSpMVは先頭と末尾の非ゼロ要素の列番号のみで実行可能である．そこでRBP法 では連続した非ゼロ要素の先頭と末尾の列番号のみを格納することで，列番号に関する情 報量を減らし，メモリ使用量の削減を行う．
RBP法と同様に連続した非ゼロ要素に着目した疎行列格納方式であるBCCOOでは複 数行，複数列に渡る固定サイズのブロックを用いて疎行列を分割し，各ブロックごとに位 置情報を与えることで，位置を示す要素数を削減している．しかし固定サイズのブロック を用いていることから0要素が含まれ，メモリ使用量が増加することもあるため，最適な ブロックサイズを設定するために多くの変換時間を必要としていた．そこでRBP法では 変換時間を短縮するため，列番号の削減を行う対象範囲を1行中の連続した非ゼロ要素に 限定することで，圧縮を行い，変換するために必要な時間を既存手法に比べ短くなるよう 設計した．
5.4節，5.5節においてRBP法のCSRとELLに対する適用方法について述べた．連続 した非ゼロ要素を1つのBlockとし，従来の非ゼロ要素1個と同じ扱いをすることで，従 来手法であるCSR，ELLへ容易に適用可能である．また不連続な非ゼロ要素に関しては，
連続した非ゼロ要素とは別の領域に格納する．領域を分割することで，不連続な非ゼロ要
素の格納に必要となるメモリ使用量を削減すると共に，SpMV演算性能を向上させる狙い がある．
RBP-CSR，RBP-ELLを使用したSpMVは，連続した非ゼロ要素の先頭の列番号を反 復ごとにインクリメントすることで本来必要となる列番号を復元する．従来手法である CSRやELLは反復毎にアクセス速度が低速なGlobal memoryへアクセスするため，長い メモリアクセス時間を消費する．一方RBP法はレジスタの値をインクリメントするだけ で列番号を得ることができるため，Global memoryへのメモリアクセス回数削減による 演算時間の短縮も期待することができる．
本章ではRBP法の趣意である既存の疎行列格納方式CSRやELLより少ないメモリ使 用量で疎行列を格納しながらも，変換に必要となる時間が短い疎行列格納方式が達成され ているか確認するため，評価実験を行った．評価実験では実際の数値シミュレーションで 使用された疎行列を用いて評価を行った．
まず最初のメモリ使用量の評価実験において，RBP法は既存手法であるCSRやELL に比べ最大27%以上，平均で11％以上のメモリ使用量削減を達成した．またBCCOOと FEMで使用された疎行列で比較すると平均で3.4%メモリ使用量が多い結果となったが，
BCOOOは変換時間に多くの時間を要する．RBP法は変換時間がBCCOOに比べ格段に
変換に必要となる計算量が少ないながらもメモリ使用量は3.4%の差であり，時間発展ご とに変換を要する問題においてはRBP法は非常に有効である．
SpMV演算時間の評価ではRBP法を用いたRBP-CSR，RBP-ELL共に平均で1.5倍以 上の高速化を達成した．この結果からRBP法は既存手法に比べて演算性能を損なうこと なくメモリ使用量の削減が可能な手法であることを確認した．
またRBP法は，変換処理が反復法のボトルネックとならないよう変換処理を単純化し 高速化を測った．結果としてGMRESを用いた反復法の演算時間の評価では，変換時間 を含めても既存の格納方式と遜色ない演算時間で処理が完了することを確認した．また逐 次処理でのPatCompの変換時間と比較して1529倍，8並列での変換と比較して10倍の 高速化を達成した．これらの結果からRBP法の目的である変換処理の高速に行いながら もメモリ使用量の削減を可能にすることを達成した．