疎行列のデータ配置

疎行列の続きデス。今回はデータ構造について直接説明するのではなく、
その構造のなかでどうデータを配置するかという話デス。

配置には大きく分けて2つの課題がありますデス。

• ソート
• 分散

データは必ずしも均一ではありません。しかしソートすると、 その偏りが制御できます。例えば、

■■
■■■
■■■
■■■■
■■■■
■■■■
■■
■■■■
■■
■■■
■■
■■■

なんて非0の数字が並んでいる疎行列があったとしましょう。そのまま、例えばGPGPUで4スレッド毎にまとめて計算すると(縦4つずつ1セットにして繰り返すと)、以下のようになります。□が4スレッド内の他のスレッドを待っている時間です。

■■□□
■■■□
■■■□
■■■■
■■■■
■■■■
■■□□
■■■■
■■□
■■■
■■□
■■■

待ち時間が多いですね。これを、非0の数字の数でソートすると、以下のようになります。待ち時間の□を減らすことができます(この例ではたまたま□が0個まで減らせています)。ソートすることで、仕事の不均衡を偏らせて、必要ない計算をする箇所を減らすことができたわけです。

■■■■
■■■■
■■■■
■■■■
■■■
■■■
■■■
■■■
■■
■■
■■
■■

反復法で解く場合、反復の前にソートして行を入れ替え、反復法を終えた後に元に戻せば済むため、こういったソートなどの重たい処理も、あまり性能に影響を与えることなく実施できます。

この方法は利用するデータ構造に依存せず利用できます。特に、GPGPU向けに、ELLPACK-Rと組み合わせて広く利用されています。例えば、Sparse matrix-vector multiplication on GPGPU clusters: A new storage format and a scalable implementationでは、ｐJDS (padded Jagged Diagonals Storage)法でソートする説明があります。

一方、OpenMPなんかで並列化する場合、static schedulingを使うことが多く、ソートした上で均一になるよう分散させたほうが都合がよくなります。例えば、4並列で処理する場合は例えば以下のようにソートした上で分散させるわけです。

■■■■
■■■
■■
■■■■
■■■
■■
■■■■
■■■
■■
■■■■
■■■
■■

例えば、地球シミュレータ向け線形ソルバーでは、pDJDS (parallel Descending-order Jagged Diagonal Storage)法でソートして均一になるよう分散して扱う説明があります。

スレッド数が少ない間ならこれでいいんですが、Xeon Phiのように244スレッドなどで処理することになると、これで長さが不十分になってしまいます。どうしたものか。ここから先は、仕事でやってる内容なので秘密です。