💡

SIMD並列化ライブラリSmartVectorDotNet開発の知見まとめ(2) SIMD演算の基礎

2024/10/04に公開

SIMD演算とは1つの命令を複数のデータに同時に適用する並列化技術です。
SmartVectorDotNetの根幹を支えるテクノロジですが、通常のスカラ演算とは異なる配慮が必要なケースがあります。

条件分岐

原則として、SIMD演算ではプログラミング言語が提供するフロー制御構文を用いた条件分岐は利用できません。
これは、同時に処理される複数のデータそれぞれが分岐判定において異なる結果となるケースが考えられるからです。
これを解決するため、SIMDにおいてはすべてのコードパスをあらかじめ計算しておき、分岐判定の結果に基づいてピックアップするという戦略をとります。

例えば、以下に示すランプ関数の実装を考えます。

R(x) := \begin{cases} x & (x \ge 0) \\ 0 & (x \lt 0) \\ \end{cases}

これをC#のスカラ演算で実装するならば以下のように書けるでしょう。

public static double Ramp(double x)
    => x < 0 ? 0 : x;

しかし、SIMD演算を用いてベクトル計算をする場合は以下のように書くべきです。

public static Vector<double> Ramp(Vector<double> x)
{
    var xIsLessThanZero = Vector.LessThan(x, Vector<double>.Zero);
    return Vector.ConditionalSelect(
        xIsLessThanZero,
        Vector<double>.Zero,
        x);
}

Vector.LessThanのようなSIMD比較演算命令は条件が真である場合にその要素のビットすべてに対して1を、偽である場合には0を出力します。
Vector.ConditionalSelectは第1項のビットが1であるならば第2項のビットを、第1項のビットが0であるならば第3項のビットを出力します。

このように全コードパスの計算結果を結合することで条件分岐を表現します。
SmartVectorDotNetではCPU SIMD命令による計算を主眼としていますが、GPUプログラミングにおいても同様のテクニックが役立つでしょう。

分岐の適用戦略

分岐を実現する方法は導くことができました。
しかし、パフォーマンスの追求においては更に分岐をどのように利用するかも考える必要があります。

SmartVectorDotNetでは、主要な初等関数のSIMD化メソッドを提供しています。
これら初等関数のうち非代数的なもの、すなわち超越関数は計算機上では何らかの手段（例えばテイラー展開）で近似する必要があります。
この近似は実現可能な範囲で十分に高速ですが、それでも単純な四則演算などに比べれば圧倒的に遅いです。

例として、正弦関数 $\sin x$ の実装を考えます。
この関数の定義域は実数全体、計算機上では浮動小数の表現可能な数字の範囲に当たります。
しかし、マクローリン展開を用いて近似する場合 $x$ が $0$ から離れるほど近似の精度は低下していきます。
幸い正弦関数は周期性と対称性を持っているため、コアロジックは定義域を限定することができます。
ここではひとまず周期性には目をつむり、 $0 \le x$ の定義域を持つコアロジックSinForPositive(x)と正弦関数の対称性を用いて全体の実装Sin(x)を記述してみます。
スカラー演算の場合、例えば次のような実装が考えられます。

public static double Sin(double x)
{
    if(x < 0)
        return -SinForPositive(-x);
    else
        return SinForPositive(x);
}

この実装では $x < 0$ が真のコードパスと偽のコードパスは二者択一であるため $SinForPositive$ は1度だけ実行されます。
しかし、これをそのままベクトル化した場合、

public static Vector<double> Sin(Vector<double> x)
{
    var xIsLessThanZero = Vector.LessThan(x, Vector<double>.Zero);
    return Vector.ConditionalSelect(
        xIsLessThanZero,
        -SinForPositive(-x),
        SinForPositive(x));
}

SinForPositiveは2回実行されてしまうことになります。
このコアロジックは非常に重たいと考えられるため、良い実装とは言えないでしょう。
そこで、実装を次のように書き換えます。

public static Vector<double> Sin(Vector<double> x)
{
    var xIsLessThanZero = Vector.LessThan(x, Vector<double>.Zero);
    var sign = Vector.ConditionalSelect(
        xIsLessThanZero,
        -Vector<double>.One,
        Vector<double>.One);
    return sign * SinForPositive(sign * x);
}

このコードではSinForPositiveは1度だけ実行されるため、最初の実装より好ましいと言えます。

このように、SIMD演算における条件分岐はコアロジックそのものの呼びわけではなく引数や戻り値の変換に適用することを検討すべきです。
重たいコアロジックの実行回数を極力減らす実装を常に意識しましょう。

条件分岐

分岐の適用戦略

Discussion