2015年4月12日日曜日

疎行列のデータ構造

疎行列のデータ構造のまとめの続き。
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形式もありますが、ここでは省きます。

続きはまた今度

0 件のコメント:

コメントを投稿