疎行列のデータ構造

疎行列のデータ構造のまとめの続き。
ELLPACKを中心に、ELLPACK-R形式、SELLPACK形式についてまとめます。

前回と同じく以下の配列があるとします。

1	7	0	0
0	2	8	0
5	0	3	9
0	6	0	4

前回説明したELLPACK形式。これに行中の0以外の値の個数を加えたのがELLPACK-R形式です。

column					values					row length
0	1	*			1	7	*			2
1	2	*			2	8	*			2
0	2	3			5	3	9			3
1	3	*			6	4	*			2

今回は縦方向に並べます。

column: 0 1 0 1 1 2 2 3 * * 3 *
values: 1 2 5 6 7 8 3 4 0 0 9 0
rl:     2 2 3 2

これのSpMVするプログラムはこうなります。

for (i = 0; i < M; ++i)
    for (j = 0; j < rl[i]; ++j)
        Y[i] += values[i + j*M] * X[column[i + j*M]];

この方式の利点はif文が必要なくなるということです。またGPGPUの場合4スレッドや8スレッドがセットで同じ回数繰り返す必要があります。そのため、回る回数が事前に分かると効率良くスレッド群(wrap)を割り当てることができます。更に縦方向にデータが並ぶため複数スレッドでデータを共有でき、メモリ効率も向上します。そんな次第で、ELLPACK-R形式はGPGPU向けの標準データ構造として広く使われています。

4スレッドや8スレッドでセットで処理するデータが、一箇所にまとまるよう複数行ごとに分割したのがSELLPACK形式です。Sliced ELLPACK形式の名の通り、複数行(S行)ごとに分断したデータ構造です。以下はS=2の例。

column					values
0	1				1	7
1	2				2	8
--------------------
0	2	3			5	3	9
1	3	*			6	4	*

column:    0 1 1 2 0 1 2 3 3 3
values:    1 2 7 8 5 6 3 4 9 0
row_start: 0 4 10

データ構造ではrow_startを使うことでパディングを減らします。CSR形式に近くなりました。ただし、Sで分けたグループ内では1行内の0以外の数が同じになるようパディングします。これのSpMVするプログラムはこうなります。

for (i = 0; i < M; ++i) {
    off = row_start[i/S];
    next = row_start[i/S + 1];
    for (j = 0; j < (next - off ) / S; ++j)
        Y[i] += values[i%S + j*S + off] * X[column[i%S + j*S + off]];
}

このSELLPACK形式は元々GPGPU向けに開発されましたが、実はSIMDプロセッサのように4演算毎、8演算毎に高速に演算できる場合、Sを8などに固定したSELLPACK形式が効率よいことが分かり、SIMD向けに注目されているデータ構造です。

更にSELLPACK形式のデータを例えば8つずつセットになるようパディングするなどしたSELL-P形式もありますが、ここでは省きます。

続きはまた今度