RBP 法

図5.2にRBP法の概略図，Algorithm8にRBP法を既存の疎行列格納方式に適用する 手順を示す．

Algorithm8では，疎行列内の非ゼロ要素を先頭から順に，図5.2中，斜線の四角で囲ま れた要素のように連続しているか，もしくは図5.2中，丸で囲んだ要素のように不連続な のかを確認していく．RBP法では，圧縮を行う単位を1行中の連続した非ゼロ要素に限 定することで，非ゼロ要素の列番号に必要となる要素の参照回数，計算量が少なくなる．

























a b c d 0 0 e f 0 g 0 0 h i 0 0 0 0 0 0 0 j k 0 0 0 l 0 0 m n 0 0 0 0 0 o p q r 0 0 0 0 0 0 s 0 0 0 0 0 0 t u 0 0 0 0 0 v w x y























 a b

a b a b a b a b a b

a b cccc dddd a b

a b a b a b a b a b a b a b a b a b

a b ccc ddd a b

a b

a b ccccccccccccccccccccc ddddddddddddddddddddd

o p o p o p o p

o p q r o p

o p o p o p o p o p

o p qqq rrr o p

o p

o p qqqqqqqqqq rrrrrrrrrr

v w v w v w v w

v w xx yy v w

v w v w v w v w v w v w

v w xxxx yyyy v w

v w xxxxxxxxxxxx yyyyyyyyyyyy e f e f e f e f e f e f e f e f e f e f e f e f e f e f e f e f e f e f e f e f e f e f e f e f e f e f e f e f e f e f e f e f e f e f h i

h i h i h i h i h i h i h i h i h i h i h i h i h i h i h i h i h i h i h i h i h i h i h i

j k j k j k j k j k j k j k j k j k j k j k j k j k j k j k j k j k j k j k j k j k

BLOCK(1) Values: (a, b, c, d) Columns: (0, 1, 2, 3)→(0, 3)

BLOCK(2) Values: (e, f) Columns: (6, 7)→(6, 7) BLOCK(3)

Values: (h, i) Columns: （4, 5)→(4, 5)

BLOCK(4) Values: (j, k) Columns: (5, 6)→(5, 6)

m n m n m n m n m n m n m n m n m n m n m n m n m n m n m n m n m n m n m n m n m n m n m n m n m n m n m n

BLOCK(5) Values: (m, n) Columns: (5, 6)→(5, 6)

BLOCK(6) Values: (o, p, q, r) Columns: (4, 5, 6, 7)→(4, 7)

t u t u t u t u t u t u t u t u t u t u t u t u t u t u t u t u t u t u t u t u t u t u t u t u t u t u t u t u t u t u t u t u t u t u t u t u t u t u t u t u t u t u 0 0

0 0



0









 x y



BLOCK(8) Values: (v, w, x, y) Columns: (4, 5, 6, 7)→(4, 7)

BLOCK(7) Values: (t, u) Columns: (5, 6)→(5, 6)

RBP

Group of Compressed BLOCK

BLOCK(1) BLOCK(2) BLOCK(3) BLOCK(4) BLOCK(8) BLOCK(5) BLOCK(6) BLOCK(7)

Group of Non-consective elements

g, l, s

図 5.2: RBP法の概略図

疎行列内の非ゼロ要素を1つずつ確認していくだけで，非ゼロ要素が連続しているかどう かを確認でき，連続した非ゼロ要素の場合には列番号を削減することでメモリ使用量を削 減することが可能である．

BCCOOでは疎行列を複数行または複数列に渡る小さいブロックに分割し，その基準と

なる位置情報のみを格納することで，位置情報の削減を行う．RBP法は変換の速度を重 視するため各行中の連続した非ゼロ要素を対象としているため，BCCOOに比べメモリ使 用量の削減率が低くなる可能性がある．しかしBCCOOでは範囲の広いブロックを用い ることで，SpMVに不必要な0要素が含まれメモリ使用量が増加する可能性があることか ら，メモリ使用量が最も少なくなるよう最適化するため，複数のブロックサイズでの変換 を試し，最も良い結果を採用する．そのため疎行列内の非ゼロ要素に対する参照回数は RBP法の1要素1回に比べ数倍となる．よってRBP法に比べBCCOOは変換時間が大幅 に長くなる．

まずAlgorithm8中，2行目から7行目までは，非ゼロ要素の連続部に対して行う処理 である．RBP法では図5.2中“a, b, c, d”等のように，連続した非ゼロ要素の情報に関して 1ブロックとして考え，最終的にRBP法を適用する疎行列格納方式へブロック単位で格 納する．また，連続した非ゼロ要素の値については圧縮の影響がないため，連続している 間，Valuesにただ格納するだけである(8，3行目)．

4行目から6行目に示す処理は非ゼロ要素の列番号数を削減する処理であり，RBP法の 最も重要な処理である．各ブロックのColumnsのデータ数を削減するため，SpMVの計 算に必要な先頭と末尾の要素のみを取り出し格納する（図5.2中，各ブロックのColumns の矢印左側がデータ数を削除する前，矢印右側がデータを削除した後のColumnsの配列 である）．この結果，どれだけ長く連続した非ゼロ要素をBLOCK化した場合でも，列番 号を表すために必要となる要素数は2となるため，疎行列内に連続した非ゼロ要素が多く 存在したり連続数が長い場合，大きなメモリ使用量の削減が可能である．

7行目の「BLOCKを適用する疎行列格納方式で格納」は，既存の疎行列格納方式に対 して，ブロック化した非ゼロ要素を格納していく処理である．格納する際には，各ブロッ クを本来の１つ非ゼロ要素と同等に扱い格納する（つまりV aluesとColumnsの複数の 要素を一つの塊として考える）．この過程は，CSRやELLなどの既存の格納方式にて値 や列番号などを格納する方法をブロック化された非ゼロ要素に対して適用することを意味 する．例えばCSRであれば，ブロック化された非ゼロ要素の複数の値をそのまま値配列 に，圧縮された2つの列番号は列番号の配列に，1つの値を扱う場合と同様に格納する．

8行目，9行目では，i番目の非ゼロ要素が不連続だった場合の処理を記述している．図 中の“g, l, s”のような不連続な非ゼロ要素をCSR形式で格納する．この時，ELLなどの CSRとは異なる格納方式においても，不連続な非ゼロ要素は連続した非ゼロ要素とは別 の空間にCSR形式で格納する．連続部と不連続部を分離して格納する理由は，メモリア クセス効率を向上させるためである．RBP法のように，不連続な非ゼロ要素については CSR方式で格納することで，連続した非ゼロ要素の列番号を格納している配列または行 列は必ず連続した非ゼロ要素に対しアクセスすることとなる．これによりスレッドが１回 の反復で必ず2つの値を参照する．1スレッドのアクセス数が固定であれば，warp内のス レッドが一定のインデックスでスライドし，アクセスすることが可能である．そのため，

warp内の各スレッドは常にコアレスドアクセスを行うことが可能である．

ただし圧縮により，既存格納方式と同様の処理では格納できない場合も存在する．その 際には配列の追加等，正しくSpMVの計算が行えるように変更を加える必要がある．本 稿では代表的な疎行列格納方式であるCSR，ELLの格納方式に則ったブロックの格納方 法を，図5.3を用いて次の節から説明を行う．

RBP法は複数の値をブロック化するというシンプルな方法を取っているため，他の疎 行列格納方式に対しても，多少の変更のみで同様にRBP法を適用可能であると考えられ る．例えば，ELLの派生系であるELL-RはELLと同様の方法でRBPを適用可能である．

PatCompでは，COO形式で格納されているFEMモデルで生成された疎行列を Pat-Compへ直接変換し，反復法のSpMVで使用することを想定している．RBP-CSRでは CSRで格納されている疎行列からの変換，RBP-ELLではELLで格納されている疎行列 からの変換を行い，反復法内のSpMVで使用することを想定する．既存疎行列格納方式 ではGPUメモリ容量の制約で数値シミュレーションが実行できない場合，容易に適用可 能なメモリ使用量削減手法がRBP法である．現在多くの数値シミュレーションにおいて CSRやELLで疎行列が格納されているため，利便性を高めることを目的に本稿ではCSR

からRBP-CSRへ，ELLからRBP-ELLへの変換を想定する．ただしCOOから直接変換 を行うことも容易に実装することが可能である．