疎行列の密化(SpMVのSIMD化）

 部分的にでも密にできるところは、密にして並列度を高めよう、という発想です。サーベイした限り、この方法は見つかりませんでした。まずは、密化前の疎行列です。(instance19)

これを転置します。

y[m,1]=A[m,n]*X[n,1] 転置前

yt[1,m]=Xt[1,n]*At[n,m] 転置後

これを密化すると、つぎのようになります。

こうすると、SIMD化による性能向上が期待できます。AVXでは、単精度256bit,8個の並列演算まで可能です。

このインスタンスの場合、NonZero要素数が8万に対して、SIMD化しなければMAC演算数はそのまま8万、SIMD化によりMAC演算数は2万になるので、25%に演算数を削減できます。

（実際は、Load時Mask処理と後で述べる水平加算処理がプラスされます。）