リダクション演算がボトルネックになりやすい理由
リダクション演算 とは前のデータに依存する演算を指します。例えば以下の式、
sum = a[0] + a[1] + a[2] + ... + a[99]
は2値の和を求めるadd命令を利用すると、
sum1 = a[0] + a[1],
sum2 = sum1 + a[2],
sum3 = sum2 + a[3],
...
sum = sum98 + a[99]
となり、横方向の逐次的な依存となります。
CPUのパイプラインでは、このような横方向の依存はSIMD化ができず、命令レベルの並列性(ILP)が下がってしまいます。また、計算量に比べてデータのメモリアクセスが多くなり、メモリ帯域がボトルネックになりやすいという特徴があります。
SIMD(Single Instruction, Multiple Data) は、一つの命令で複数のデータを同時に処理する「並列計算方式」です。画像処理や数値計算など、同じ演算を大量のデータに適用する際、CPUの拡張命令(SSE, AVX, NEONなど)やGPUを利用した高速化に用いられます。
転置データのSIMDを利用したリダクション演算の効率化
128bitで32bitデータを4レーン扱うSIMD命令では、
| a0 | a1 | a2 | a3 | ← 4 レーン (NEON 128bit の例)
のような構造で4つの32bitデータを同時に加算することが可能です。
ここで、例えば16要素の配列を4レーンSIMDで処理することを考えます。
転置しない場合
a0, a1, a2, a3 | a4, a5, a6, a7 | a8, a9, a10, a11 | a12, a13, a14, a15
これをSIMDでロードすると
v0 = [a0, a1, a2, a3]
v1 = [a4, a5, a6, a7]
v2 = [a8, a9, a10, a11]
v3 = [a12, a13, a14, a15]
となり、このままだと、水平加算が必要となるため、SIMD化の効果は得られません。
転置した場合
このデータを転置した場合は、
v0 = [a0, a4, a8, a12]
v1 = [a1, a5, a9, a13]
v2 = [a2, a6, a10, a14]
v3 = [a3, a7, a11, a15]
となります。このデータ構造であれば、各レーンが独立した部分和を持ち、SIMDによる縦方向の加算の後、最後に水平加算（リダクション）を行うことで効率化することができます。
v0 = a0 + a4 + a8 + a12
v1 = a1 + a5 + a9 + a13
v2 = a2 + a6 + a10 + a14
v3 = a3 + a7 + a11 + a15
sum = reduce(v0 + v1 + v2 + v3)
この効果は、水平加算の回数が大幅に削減され、
- NEON なら vpaddq の回数が減る
- SVE なら svaddv の負担が減る
といった効率化につながります。