HUOXIU

ベクトル化コードの実践と考察:ベクトル化技術を用いたコードの高速化方法

出典: Alibaba Cloud Developers

Alibaba テックガイド

マシンを追加することなくハードウェアの性能を最大限に活用するには、アクセラレーションが不可欠です。一般的な処理として並行処理があります。この記事では、ベクトル化コンピューティング技術を詳しく解説し、SIMD命令と、構造化されたベクトル化可能なコードの記述方法を説明します。

I. 計算を加速する技術

計算アクセラレーションには、複数の角度からアプローチできます。ソフトウェアアクセラレーション/ハードウェアアクセラレーション:ソフトウェアの観点からは、ハードウェア性能を最大化すること、ハードウェアの観点からは、クロック速度を可能な限り向上させることです。方向性としては、より高度な同時処理能力を活用することで水平方向に、あるいは単一ポイントの性能を向上させることで垂直方向に実現できます。同時処理能力は、粒度によって、大規模なものから小規模なものまで分類できます。マシンレベルの同時処理(同じタスクを実行するマシンを複数台スタックする)、スレッドレベルの同時処理(マルチスレッド、マルチコアの同時計算を活用する)、または命令レベルの同時処理(単一の命令内で複数のデータポイントを操作する)です。

並行処理は非常に一般的ですが、命令レベルの並行処理とは一体どのように理解すればよいのでしょうか?フォン・ノイマン・アーキテクチャでは、CPUはメモリから命令とデータを読み込み、命令を完了し、その結果をメモリに保存します。通常、1つの命令は1つのデータを処理し、1つの結果を生成します。しかし、SIMD(Single Instruction Multiple Data)命令は、1つの命令で複数のデータを同時に処理できる特殊なタイプのCPU命令です。
SIMD命令はベクトル化実行を行います。これはしばしば「ベクトル化」と訳されますが、これは必ずしも正確な訳ではありません。より適切な用語は「配列ベースの実行」です。これは、命令が単一のデータポイントを処理するのではなく、配列内の複数のデータポイントを一度に処理することを意味します。ベクトルは数値と方向の両方を意味するため、この文脈では「配列」という表現の方がより正確です。SIMD命令を実行すると、複数のデータポイントがメモリからワイドレジスタに同時にロードされ、単一の並列命令がそれらすべてを同時に計算します。例えば、32バイト(256ビット)を処理する命令は、8つの整数を同時に処理できるため、8倍の高速化を実現します。同時に、SIMDはループ回数を削減し、ループジャンプ命令を大幅に削減し、処理をさらに高速化します。SIMD命令は、0個、1個、または2個の配列引数を持つことができます。配列引数が1つの場合、命令は各要素を計算し、結果を対応する位置に書き込みます。引数が 2 つある場合、指定された操作は 2 つの引数に対応する場所で実行され、結果はそれぞれの場所に書き込まれます。
SIMDによるコンパイラ高速化の原理は、ループ文を拡張することでループ回数を減らすことです。ループ拡張の目的は、ループ中のジャンプ文の数を減らすことです。ジャンプ文はパイプラインを混乱させる可能性があるためです。パイプラインは命令をプリロードすることでCPUの停止時間を短縮できるため、ジャンプ命令を減らすことでパイプラインの効率を向上させることができます。
SIMD 命令は、A と B の 4 つの数値ペアを同時に処理し、C に格納される 4 つの結果を生成します。

次のコードは、4 つの浮動小数点数を二乗する方法を示しています。








 void squre( float* ptr ){ for( int i = 0; i < 4; i++ ) { const float f = ptr[ i ]; ptr[ i ] = f * f; }}
上記のコードは SIMD 命令として書き直すことができ、ループを削除して、データをレジスタにロードし、平方を計算し、結果をメモリに書き戻すという 3 つの命令だけで計算を完了できます。






 void squre(float * ptr){ __m128 f = _mm_loadu_ps( ptr ); f = _mm_mul_ps( f, f ); _mm_storeu_ps( ptr, f );} 

II. SIMD拡張命令セット

SIMD 命令が実行されると、データのセットがワイド レジスタ (128 ビット、256 ビット、または 512 ビット) にロードされ、結果が生成されて別のワイド レジスタに配置されます。
SIMD命令は、MMXシリーズ、SSE(ストリーミングSIMD拡張命令)シリーズ、およびAVX(アドバンスト・ベクター・エクステンション)シリーズの拡張命令セットのハードウェアサポートを必要とします。SSE1、SSE2、SSE3、SSE4.1、およびSSE4.2は16バイトレジスタを、AVXとAVX2は32バイトレジスタを、AVX512は64バイトレジスタをそれぞれサポートします。現在、ほとんどのCPUはAVX2をサポートしていますが、AVX512は最新のCPUのみサポートされています。

命令セットはCPUハードウェアのサポートを必要とします。以下のリストは、さまざまな命令セットをサポートするCPUを示しています。

ARMはSIMD拡張命令も導入しました。代表的なSIMD演算には、算術演算(+-*/)に加え、abs、sqrtなどが含まれます。完全な命令セットについては、Intelが提供するユーザードキュメントを参照してください。

https://software.intel.com/sites/landingpage/IntrinsicsGuide/#
では、SIMD命令はどのように生成されるのでしょうか?いくつかの方法があります。
  • コンパイラ自動ベクトル化
    1. 静的コンパイル
    2. ジャストインタイム(JIT)コンパイル

  • 手書きのSIMD命令

III. コンパイラによる静的自動ベクトル化

コンパイラによる自動ベクトル化を行うには、いくつかの条件を満たす必要があります。

1. コードは特定のパラダイムに準拠しており、さまざまなケースが後で詳細に紹介されます。

2. gcc や clang などの一般的に使用されるコンパイラの場合、ベクトル化を有効にするには、コンパイル オプションに -O3 オプションを追加します。

3.1 コンパイラの選択とオプション

コンパイル中に、コンパイル オプションに -O3 または -mavx2 -march=native -ftree-vectorize を追加すると、ベクトル化が有効になります。

ベクトル化を実装できるのは、コンパイラの上位バージョンのみです。GCC 4.9.2以前のバージョンはテストの結果、ベクトル化をサポートしていないことが判明しましたが、GCC 9.2.1はサポートしています。GCCはベクトル化に対してより有利なサポートを提供しています。Clangは一部のコードをベクトル化コードに変換できない場合があります。また、Clangで生成されたベクトル化コードはGCCよりもパフォーマンスが優れている場合もあります(より広いレジスタ命令を使用しているため)。したがって、仕様に準拠したコードを記述し、両方のコンパイラのパフォーマンスを個別にテストすることをお勧めします。



 res[i] = tmpBitPtr[i] & opBitPtr[i]; // 添え字を使用してアドレスにアクセスします。これは clang と gcc の両方でサポートされています。 *(res + i) = *(tmpBitPtr + i) & *(opBitPtr + i); // アドレス演算を使用してメモリにアクセスします。これは clang ではサポートされていませんが、gcc ではサポートされています。 

IV. ベクトル化可能なコードの書き方

プログラミングには、コードのベクトル化されたコードを生成するためにコンパイラーをより適切にガイドするためのベスト プラクティスがいくつかあります。
1. 反復回数は数えられる必要があります。

ループ変数の初期値と最終値は固定する必要があります。例:



反復回数が数えられる「for (int i = 0; i < n; ++i)」メソッドはベクトル化できます。反復回数が数えられない「for (int i = 0; i != n; ++i)」メソッドはベクトル化できません。
2. 関数呼び出しのないシンプルで直接的な計算。
計算には、加算、減算、乗算、除算などの単純な数学演算と、AND、OR、NOTなどの論理演算のみを含める必要があります。switch、if、returnなどのステートメントは含めないでください。

ただし、例外がいくつかあります。一部の三角関数(sin、cosなど)や算術関数(pow、logなど)は、libに組み込みのベクトル化実装が提供されているため、自動的にベクトル化できます。
3. 最も内側のループ
最も内側のループのみをベクトル化できます。
4. 連続したメモリ空間へのアクセス
関数の計算パラメータと結果は、連続した空間に格納され、単一の SIMD 命令を介してメモリからレジスタにロードされる必要があります。


 for (int i=0; i<SIZE; i+=2) b[i] += a[i] * x[i]; // 連続した空間にアクセスします。ベクトル化できます。 for (int i=0; i<SIZE; i+=2) b[i] += a[i] * x[index[i]] // 連続していない空間にアクセスします。ベクトル化できません。
5. データは独立している
これは並列計算であるため、最も重要な点です。同じ並列命令に属する複数の独立した命令で演算される数値は互いに関連づけられません。そうでなければ並列処理は不可能であり、逐次計算しか選択肢がありません。

データ依存関係に関連するシナリオはいくつかあります。










 for (j=1; j<MAX; j++) A[j]=A[j-1]+1; // ケース 1 書き込んでから読み取るため、ベクトル化できません for (j=1; j<MAX; j++) A[j-1]=A[j]+1; // ケース 2 読み取ってから書き込むため、ベクトル化できません for (j=1; j<MAX; j++) A[j-4]=A[j]+1; // ケース 3 読み取ってから書き込む場合でも、4 セットのデータがベクトルを形成する場合は、同じデータ セット内に依存性がないため、ベクトル化できます // ケース 4 書き込んでから書き込むため、ベクトル化できません (この場合はケースなし) for (j=1; j<MAX; j++) B[j]=A[j]+A[j-1]+1; // ケース 5 読み取り後に読み取り。書き込み操作がないため、ベクトル化には影響しません。 for (j=1; j<MAX; j++) sum = sum + A[j]*B[j] // ケース 6 これはベクトル化できます。同じ変数を読み取り、毎回別の変数に書き込みますが、最初にワイド レジスタを使用して合計を表し、各パスのデータを個別に累積してから、ループ終了後にワイド レジスタに値を累積することができます。 `for (i = 0; i < size; i++) { c[i] = a[i] * b[i]; }` // ケース 7。 これには、 `c` のメモリ空間が `a` および `b` のメモリ空間と交差するかどうかを確認する必要があります。 `c` が `a` または `b` のエイリアスである場合、たとえば `c = a + 1` であれば `c[i] = a[i + 1]` となり、`a` と `c` にはメモリの重複があります。
上記の例では、ケース3、5、6はベクトル化可能です。これらは比較的特殊なケースであり、一般的には依存関係の問題を明示的に回避するコードを記述することが推奨されます。依存関係が確認され、それでもベクトル化を使用したい場合は、SIMDコードを手動で記述できます。
6. ポインタの代わりに配列を使う
ポインタは配列と同様の効果を実現できますが、配列を使用すると予期しない依存関係が発生する可能性が低くなります。さらに、ポインタを使用する場合、コンパイラでさえも状況によってはベクトル化が可能かどうかを判断できない場合があります。配列はコンパイラが容易にベクトル化できるため、この懸念は解消されます。
7. ループ カウンターを配列のインデックスとして使用します。
ループカウンタを配列のインデックスとして直接使用すると、コンパイラの理解が容易になります。他の値をインデックスとして使用すると、ベクトル化が可能かどうかを判断するのが難しくなります。例えば、


 for(int i = 0;i < 10;i++) a[i] = b[i] // これはより良い for(int i =0,index=0;i < 10;i++) a[index++]=b[index] // これはベクトル化できない
8. より効率的なメモリレイアウトを使用する
データは理想的には16バイトまたは32バイトに揃える必要があります。配列要素は、構造体やクラスではなく、プリミティブデータ型であることが望ましいです。複雑な構造の場合、同じ配列内の各オブジェクトの同一要素は連続して格納されません。
9. ループの反復回数は命令幅の整数倍である必要はありません。
一部の古いコンパイラでは、ループの反復回数は命令幅の整数倍でなければなりません。例えば、4バイトのint型を処理する128ビット命令では、4つのint型を同時に処理できるため、ループの反復回数は4の倍数でなければなりません。したがって、コードを記述する際には、2つのループを使用する必要があります。最初の部分では、残りのデータを4の倍数でループし、2番目の部分では最後に残った少量のデータをループします。
最新のコンパイラはこのような状況を自動的に処理できます。コードを2つの部分に分割することなく、通常のロジックに従ってコードを記述できます。コンパイラは2つのロジック部分を自動的に生成します。

V. 手書きSIMDコード

コンパイラは単純なロジックをSIMD命令に変換できますが、ベクトル化を妨げないようにコーディングスタイルを慎重に検討する必要があります。しかし、複雑なロジックの中には、各オペランドを個別に干渉なく計算する必要があることを人間が理解していても、コンパイラによって自動的にベクトル化できないものがあり、そのような場合にはベクトル化が利用できます。このような状況では、SIMDコードを手動で記述できます。典型的な例は、文字列をすべて小文字に変換することです。

5.1 SIMDコード例と異なるコンパイラのパフォーマンス比較



















































 const static char not_case_lower_bound = 'A' ; const static char not_case_upper_bound= 'Z' ; static void lowerStrWithSIMD ( const char * src, const char * src_end, char * dst) { const auto flip_case_mask = 'A' ^ 'a' ;
# ifdef __SSE2__ const auto bytes_sse = sizeof (__m128i); const auto * src_end_sse = src_end - (src_end - src) % bytes_sse;     const auto v_not_case_lower_bound = _mm_set1_epi8(not_case_lower_bound - 1 ); const auto v_not_case_upper_bound = _mm_set1_epi8(not_case_upper_bound + 1 ); const auto v_flip_case_mask = _mm_set1_epi8(flip_case_mask);     for (; src < src_end_sse; src += bytes_sse, dst += bytes_sse) { /// load 16 sequential 8-bit characters const auto chars = _mm_loadu_si128( reinterpret_cast < const __m128i *>(src));         /// find which 8-bit sequences belong to range [case_lower_bound, case_upper_bound] const auto is_not_case = _mm_and_si128(_mm_cmpgt_epi8(chars, v_not_case_lower_bound), _mm_cmplt_epi8(chars, v_not_case_upper_bound));         /// keep lip_case_mask _mm_and_si128(v_flip_case_mask, is_not_case);         /// flip case by applying calculated mask const auto xor_mask = _mm_and_si128(v_flip_case_mask, is_not_case); const auto cased_chars = _mm_xor_si128(chars, xor_mask);         /// store result back to destination _mm_storeu_si128( reinterpret_cast <__m128i *>(dst), cased_chars); } # endif     for (; src < src_end; ++src, ++dst) if (*src >= not_case_lower_bound && *src <= not_case_upper_bound) *dst = *src ^ flip_case_mask; else *dst = *src; } static void lowerStr ( const char * src, const char * src_end, char * dst) { const auto flip_case_mask = 'A' ^ 'a' ;
for (; src < src_end; ++src, ++dst) if (*src >= not_case_lower_bound && *src <= not_case_upper_bound) *dst = *src ^ flip_case_mask; else *dst = *src; }

上記の2つの関数は、文字列内の大文字を小文字に変換します。最初の関数はSIMD(128ビット命令)を使用し、2番目の関数はより従来的なアプローチを使用します。最初の関数は128ビット命令(16バイト)を使用し、理論上はベクトル化されていない命令と比較して16倍の高速化を実現します。一方、2番目の関数は構造が明確で自動的にベクトル化できるため、異なるコンパイラ(gバージョン9.3.0とclang 12.0.0)を使用してコンパイルパフォーマンスをテストします。

コンパイルオプション
SIMD/通常>
解釈 (レイテンシ比が 1 未満の場合、SIMD が優れており、1 より大きい場合、後者の自動ベクトル化が優れています)。
g++>
1.9
コンパイラは命令を自動的にベクトル化して 256 個の命令を生成し、128 ビットに比べてパフォーマンスが 2 倍になりました。
g++>
0.99
これら 2 つは似ていますが、コンパイラは自動的にベクトル化して 128 ビットの命令を生成します。
g++>
0.09
-O2 は自動的にベクトル化できません。
クラング++>
3.1
自動ベクトル化により 512 ビットの命令が生成されます。これは 128 ビットの命令よりも 3 倍以上高速です。
クラング++>
1.6
コンパイラは自動的にベクトル化され、256 ビットの命令を生成しました。
クラング++>
0.93
コンパイラは自動的に 128 ビットの命令を生成しました。
クラング++>
0.09
-O1はベクトル化できません
結論: 同じ最適化レベルでは、clang はより広範囲の命令を生成し、パフォーマンスが向上します。

5.2 SIMD命令の解釈

最も単純な SIMD 命令は、2 つの数値の加算を実行します。


 const __m128i dst = _mm_add_epi32(左、右);

この命令は4組の整数を加算し、その結果を格納します。`__m128i`128ビット幅のレジスタを示し、4つの整数(4バイト、32ビット)を格納し、4つの整数を保持できます。`_mm_and_epi32`SIMD命令です。`_mm`は128ビットレジスタ、`add` は加算、`epi32` は32ビット整数を示します。SIMD命令の命名規則:SIMD命令は、レジスタ幅、演算タイプ、パラメータ幅の3つの意味を表す必要があります。


異なるデータ型を異なる幅のレジスタにマッピングするための構文:

16バイト
32バイト
64バイト
32ビット浮動小数点数
__m128
__m256
__m512
64ビット浮動小数点数
__m128d
__m256d
__m512d
整数
__m128i
__m256i
__m512i
レジスタ幅。たとえば、128 ビット レジスタは _mm で始まります。マッピング関係については次の表を参照してください。
命令の接頭辞
レジスタビット幅
_mm
128
_mm256
256
_mm512
512
xor、and、intersect などの演算タイプ。

パラメータ幅: パラメータ内の単一データエントリのビット数。この情報は命令サフィックスに含まれています。例えば、浮動小数点数が32ビットで倍精度浮動小数点数が64ビットの場合、128ビットレジスタは4つの浮動小数点数または2つの倍精度浮動小数点数を受け入れることができます。一部の命令はパラメータを受け入れないため、パラメータ幅情報は含まれません。例えば、epi16は16ビットのintを表します。詳細については、以下の表を参照してください。
コマンドサフィックス
データラインあたりのビット数
データ型
エピソード8
8
整数
エピソード16
16
整数
pi16
16
整数
エピ32
32
整数
パイ32
32
整数
エピ64
64
整数
pu8
8
署名なし>
epu8
8
署名なし>
epu16
16
署名なし>
epu32
32
署名なし>
追伸
32
フロート
日付
64
ダブル
たとえば、関数`__m128 _mm_div_ps (__m128 a, __m128 b)`は、`__mm` (128 ビット レジスタを示す)、`div` (除算を示す)、および `ps` (演算パラメータが 32 ビット浮動小数点数であることを示す) で始まる命令名に基づいて、それぞれ 4 つの 32 ビット単精度浮動小数点数を含む 2 つの配列を同時にロードし、2 つの配列の対応する位置で除算演算を実行し、4 つの除算結果を返します。
通常、命令の結果の幅はパラメータの幅と一致しますが、例外もあります。
SIMD命令を用いて2つのベクトルを実行する場合、2つのベクトル内の対応するデータは個別に演算されます。ただし、例外がいくつかあります。例えば、同じベクトル内の隣接するデータに対して演算が行われる場合があり、これは水平演算と呼ばれます。例えば、 __m128i _mm_hadd_epi16 (__m128i a, __m128i b)命令は、aとbの隣接するデータを順番に加算します。aの値が[1,2,3,4]で、bの値が[5,6,7,8]の場合、結果は[1+2,3+4,5+6,7+8]となります。
2つのベクトル内のすべてのデータが計算に使用されますが、例外もあります。マスクは計算に含めるデータを制御します。マスク内の数字の位置(例:1)は、計算におけるその数字の位置を示します。例えば、関数 ` __m128i _mm_mask_add_epi16 (__m128i src, __mmask8 k, __m128i a, __m128i b) ` は、`k` をマスクとして使用します。`k` の位置が 1 の場合、`a` と `b` の対応する位置の合計が返されます。`k` の位置が 0 の場合、`src` に対応する位置の数値が返されます。
SIMD 命令セットには、算術、比較、暗号化、ビット演算、論理演算、統計と確率、ビットシフト、メモリの読み込みと保存、シャッフルなどの機能が含まれます。
1. SIMDメモリ操作
SIMDメモリ操作は、データをレジスタにロードし、対応するSIMD型を返します。16ビットデータをロードする命令は`_mm_load_si128` 、64ビットデータをロードする命令は ` _mm256_load_ps`です。どちらの命令も、データがアライメントされている必要があります。データがアライメントされていない場合は、 `_mm_loadu_si128``_mm256_loadu_ps`が使用されます
2. SIMD初期化レジスタ命令
0 に初期化する命令。_mm_setzero_ps_mm256_setzero_si256 はレジスタを 0 に初期化し、初期化操作には依存関係はありません。
特定の値に初期化します。`_mm [256]_set_XXX`は各ポイントを異なる値に初期化し、 `_mm[256]_set1_XXX`は各ポイントを同じ値に初期化します。`[256]` は256が存在するかどうかを示します。256が存在する場合、 `_mm_set_epi32(1,2,3,4) ` は整数 `[1,2,3,4]` を順に初期化します。初期化の順序が逆の場合は、 `_mm_setr_epi32(1,2,3,4)`を使用します
3. ビット演算命令
float と int には、AND、OR、XOR など、多くのビット演算命令があります。NOT 命令を実行する最も速い方法は、すべて 1 の XOR を実行することです。また、すべて 1 を得る最も速い方法は、2 つの 0 を比較して等しいかどうかを調べることです。以下のコード例をご覧ください。






 __m128i ビットワイズノット (__m128i x) { const __m128i ゼロ = _mm_setzero_si128(); const __128i ワン = _mm_cmpeq_epi32(ゼロ、ゼロ); 戻り値 _mm_xor_si128(x、ワン);}
4. 浮動小数点命令
浮動小数点命令は、基本的な算術演算(+、-、*、/)と拡張演算(sqrt)をサポートします。便利な関数としては、 `_mm_min_ss(a, b) ` などがあります。32ビット浮動小数点数の場合、1/x を実行するには、対応するSIMD命令は`_mm_rcp_ps` 対応するSIMD命令`_mm_rsqrt_ps`です。SIMD命令を使用すると、演算を1つの命令で完了できるため、速度が向上します。
たとえば、2 つの配列を加算する場合、[a,b,c,d]+[e,f,g,h]=[a+e,b+f,c+g,d+h]、対応する SIMD 命令は_mm_hadd_ps _mm_hadd_pd _mm256_hadd_pd 、および_mm256_hadd_psです
5. 非並列命令を使用することで高速化も実現できます。
一部の命令は一度に1つのデータしか処理できませんが、それでも高速化を実現できます。例えば`_mm_min_ss`命令は2つの浮動小数点数の最小値を取得します。この命令はジャンプ命令や分岐命令を回避し、1命令で計算を完了できます。同様に、最大値を取得する命令は`_mm_max_sd`です

5.3 手書きSIMD命令の欠点

SIMD命令を手書きで書くのは一見魅力的に見えますが、移植性が低いという大きな問題があります。512ビット命令を手書きで書いて、それをAVX命令セットをサポートしていないマシンで実行しようとすると、問題が発生します。したがって、最善の解決策は、コンパイラのベクトル化仕様に準拠したコードを記述し、ベクトル化はコンパイラに任せることです。最新のコンパイラはこれらの問題を処理してくれます。

VI. 結論

最新のコンパイラは、ベクトル化を自動化できるほどインテリジェントです。コンパイラのバージョンをアップグレードするだけでなく、開発者はコーディングスキルを向上させ、上記で定義された仕様に準拠したコードを作成することで、コンパイラが効率的な実行コードを生成できるようにする必要があります。