この記事は、Go Parallel に公開されている「What to Do When Auto-Vectorization Fails?」の日本語参考訳です。
概要
この記事は、インテル® デベロッパー・ゾーン (インテル® DZ) のインテル® C++ コンパイラー・フォーラム2 に投稿された問題1 に関する解析の詳細を説明するものです。
あるインテル® DZ のユーザーがコードの現代化ワークショップで実装した簡単なプログラムにおいて、内部 for ループの問題が見つかったと報告してくれました。次に問題に関連するコードを示します。
for (std::size_t i = 0; i < nb_cluster; ++i) {
float x = point[k].red - centroid[i].red;
float y = point[k].green - centroid[i].green;
float z = point[k].blue - centroid[i].blue;
float distance = std::pow(x, 2) + std::pow(y, 2) + std::pow(z, 2);
if (distance < best_distance) {
best_distance = distance;
best_centroid = i;
}
...
注: これは、KmcTestAppV1.cpp の自動ベクトル化された内部 for ループそのものではありません。
このインテル® DZ のユーザーは、ループ変数 ‘i‘ が ‘unsigned int‘ である ‘std::size_t‘ データ型として宣言されているため、内部 for ループがベクトル化されなかったのではないかと疑っています。
変更前のオリジナルのソースコード6 を添付します。詳細ついては、KmcTestAppV1.cpp をご覧ください。
この記事は、ベクトル化や並列化のテクニックに関するチュートリアルではありませんが、以下にこれらのテクニックに関する簡単な概要を示します。
ベクトル化と並列化のテクニックの簡単な概要
現代のソフトウェアは複雑であり、特にデータ集約型の処理において、ピーク・パフォーマンスを達成するためには、現代の CPU (複数の論理処理ユニット (LPU) とベクトル処理ユニット (VPU) を備えたメニーコア) のベクトル化と並列化機能を最大限に利用する必要があります。
VPU は、データセットの複数の値に対して異なる操作を同時に行えるようにします。このテクニックは、ベクトル化と呼ばれます。これにより、同じ処理をスカラーまたはシーケンシャルに行うときと比べ、処理パフォーマンスを向上できます。
並列化は、異なる LPU でデータセットの部分領域を同時に処理できるようにする、別のテクニックです。
ベクトル化と並列化を組み合わせて適用することで、処理パフォーマンスを大幅に向上できます。
一般的なベクトル化のルール
ソースコードのベクトル化に関連する次の一般的なルールを考慮する必要があります。
- 現代の C/C++ コンパイラーのベクトル化機能を使用する必要があります。
- ベクトル化を有効にするには 2 つの方法があります: 1 つはコンパイラーによる自動ベクトル化 (AV) で、もう 1 つは明示的 (explicit) なベクトル化 (EV) です。
- 比較的シンプルな内部 for ループのみベクトル化できます。
- C/C++ の構文の複雑性から (標準テンプレート・ライブラリーや C++ オペレーターなど)、AV や EV のテクニックでは内部 for ループのベクトル化が困難なことがあります。
- 現代の C/C++ コンパイラーで内部 for ループをベクトル化できない場合は、すべてのケースを調査して分析することをお勧めします。
内部 for ループのループ制御変数はどのように定義すべきか
AV テクニックはソースコードを変更する必要がなく、簡単な内部 for ループには最も有効であると考えられます。現代の C/C++ コンパイラーの AV は、’O2‘ や ‘O3‘ 最適化オプションが指定されるとデフォルトで有効になります。
複雑なループで EV を使用する場合、組込み関数や #pragma ディレクティブを使用してベクトル化を強制することが可能ですが、内部 for ループの変更が必要になります。
内部 for ループのループ制御変数はどのように定義すべきでしょうか?
2 つのケースが考えられます。
ケース A – 変数 ‘i’ を ‘int’ として宣言する
...
for( int i = 0; i < n; i += 1 )
{
A[i] = A[i] + B[i];
}
...
そして、
ケース B – 変数 ‘i’ を ‘unsigned int’ として宣言する
...
for( unsigned int i = 0; i < n; i += 1 )
{
A[i] = A[i] + B[i];
}
...
ケース A の変数 ‘i‘ は、符号付きのデータ型 ‘int‘ として宣言されます。
ケース B の変数 ‘i‘ は、符号なしのデータ型 ‘unsigned int‘ として宣言されます。
C/C++ コンパイラーのベクトル化機能を評価するため、ケース A と B を簡単なテストプログラム3 に統合します。
////////////////////////////////////////////////////////////////////////////////////////////////////
// TestApp.cpp - アセンブリー・リストを生成するには、'-S' オプションが必要です。
// Linux*:
// icpc -O3 -xAVX -qopt-report=1 TestApp.cpp -o TestApp.out
// g++ -O3 -mavx -ftree-vectorizer-verbose=1 TestApp.cpp -o TestApp.out
// Windows®:
// icl -O3 /QxAVX /Qvec-report=1 TestApp.cpp TestApp.exe
// g++ -O3 -mavx -ftree-vectorizer-verbose=1 TestApp.cpp -o TestApp.exe
#include <stdio.h>
#include <stdlib.h>
//
////////////////////////////////////////////////////////////////////////////////////////////////////
typedef float RTfnumber;
typedef int RTiterator; // ケース A ではコメントを外します
typedef int RTinumber;
// typedef unsigned int RTiterator; // ケース B ではコメントを外します
// typedef unsigned int RTinumber;
////////////////////////////////////////////////////////////////////////////////////////////////////
const RTinumber iDsSize = 1024;
////////////////////////////////////////////////////////////////////////////////////////////////////
int main( void )
{
RTfnumber fDsA[ iDsSize ];
RTfnumber fDsB[ iDsSize ];
RTiterator i;
for( i = 0; i < iDsSize; i += 1 )
fDsA[i] = ( RTfnumber )( i );
for( i = 0; i < iDsSize; i += 1 )
fDsB[i] = ( RTfnumber )( i );
for( i = 0; i < 16; i += 1 )
printf( "%4.1f ", fDsA[i] );
printf( "\n" );
for( i = 0; i < 16; i += 1 )
printf( "%4.1f ", fDsB[i] );
printf( "\n" );
for( i = 0; i < iDsSize; i += 1 )
fDsA[i] = fDsA[i] + fDsB[i]; // 行 49
for( i = 0; i < 16; i += 1 )
printf( "%4.1f ", fDsA[i] );
printf( "\n" );
return ( int )1;
}
これら 2 つの for ループ (上記コードの行 49 を参照) は容易にベクトル化可能であり4 (vmovups や vaddps などのようにプリフィックス ‘v‘ が付いた命令)、インテル® C++ コンパイラーは、変数 ‘i‘ の宣言方法に関係なく、どちらのケースでも同じベクトル化レポートを生成します。
ケース A と B のベクトル化レポート
...
Begin optimization report for: main()
Report from: Interprocedural optimizations [ipo]
INLINE REPORT: (main())
Report from: Loop nest, Vector & Auto-parallelization optimizations [loop, vec, par]
LOOP BEGIN at TestApp.cpp(37,2)
remark #25045: Fused Loops: ( 37 39 )
remark #15301: FUSED LOOP WAS VECTORIZED
LOOP END
LOOP BEGIN at TestApp.cpp(39,2)
LOOP END
LOOP BEGIN at TestApp.cpp(42,2)
remark #25460: No loop optimizations reported
LOOP END
LOOP BEGIN at TestApp.cpp(45,2)
remark #25460: No loop optimizations reported
LOOP END
LOOP BEGIN at TestApp.cpp(49,2)
remark #15300: LOOP WAS VECTORIZED
LOOP END
LOOP BEGIN at TestApp.cpp(52,2)
remark #25460: No loop optimizations reported
LOOP END
...
ベクトル化レポート4 は、行 493 の for ループがベクトル化されたことを示しています。
...
LOOP BEGIN at TestApp.cpp(49,2)
remark #15300: LOOP WAS VECTORIZED
LOOP END
...
しかし、インテル® C++ コンパイラーは、これら 2 つの for ループを異なる C 言語構造として見なし、異なる 2 つのベクトル化されたバイナリーを生成します。
以下に 2 つのアセンブリー・リストの行 493 の for ループに関連する部分を示します。
ケース A – アセンブリー・リスト (TestApp.cpp のコンパイルで ‘-S’ オプションを指定)
...
..B1.12: # Preds ..B1.12 ..B1.11
vmovups (%rsp,%rax,4), %ymm0 #50.13
vmovups 32(%rsp,%rax,4), %ymm2 #50.13
vmovups 64(%rsp,%rax,4), %ymm4 #50.13
vmovups 96(%rsp,%rax,4), %ymm6 #50.13
vaddps 4128(%rsp,%rax,4), %ymm2, %ymm3 #50.23
vaddps 4096(%rsp,%rax,4), %ymm0, %ymm1 #50.23
vaddps 4160(%rsp,%rax,4), %ymm4, %ymm5 #50.23
vaddps 4192(%rsp,%rax,4), %ymm6, %ymm7 #50.23
vmovups %ymm1, (%rsp,%rax,4) #50.3
vmovups %ymm3, 32(%rsp,%rax,4) #50.3
vmovups %ymm5, 64(%rsp,%rax,4) #50.3
vmovups %ymm7, 96(%rsp,%rax,4) #50.3
addq $32, %rax#49.2
cmpq $1024, %rax #49.2
jb ..B1.12 # Prob 99% #49.2
...
注: 完全なアセンブリー・リストは、TestApp.icc.itype.s5.1 をご覧ください。
ケース B – アセンブリー・リスト (TestApp.cpp のコンパイルで ‘-S’ オプションを指定)
...
..B1.12: # Preds ..B1.12 ..B1.11
lea 8(%rax), %edx #50.13
lea 16(%rax), %ecx #50.13
lea 24(%rax), %esi #50.13
vmovups (%rsp,%rax,4), %ymm0 #50.13
vaddps 4096(%rsp,%rax,4), %ymm0, %ymm1 #50.23
vmovups %ymm1, (%rsp,%rax,4) #50.3
addl $32, %eax #49.2
vmovups (%rsp,%rdx,4), %ymm2 #50.13
cmpl $1024, %eax #49.2
vaddps 4096(%rsp,%rdx,4), %ymm2, %ymm3 #50.23
vmovups %ymm3, (%rsp,%rdx,4) #50.3
vmovups (%rsp,%rcx,4), %ymm4 #50.13
vaddps 4096(%rsp,%rcx,4), %ymm4, %ymm5 #50.23
vmovups %ymm5, (%rsp,%rcx,4) #50.3
vmovups (%rsp,%rsi,4), %ymm6 #50.13
vaddps 4096(%rsp,%rsi,4), %ymm6, %ymm7 #50.23
vmovups %ymm7, (%rsp,%rsi,4) #50.3
jb ..B1.12 # Prob 99% #49.2
...
注: 完全なアセンブリー・リストは、TestApp.icc.utype.s5.2 をご覧ください。
これで (最初にフォーラムに投稿された1) 内部 for ループが自動ベクトル化されない理由が明らかとなりました。原因は、変数 ‘i‘ がどのように宣言されているかではなく、ほかの何かがインテル® C++ コンパイラーのベクトル化エンジンに影響しています。
真の原因を特定するため、皆さんへ質問があります: AV や EV テクニックが適用できなかった場合、どのようなコンパイラー・メッセージが生成されていますか?
インテル® C++ コンパイラーが AV や EV テクニックを適用できなかった場合のベクトル化レポートのメッセージには、次のようなものがあります。
...loop was not vectorized: not inner loop. (ループはベクトル化されません: 内部ループではありません) ...loop was not vectorized: existence of vector dependence. (ループはベクトル化されません: ベクトルの依存関係が存在します) ...loop was not vectorized: statement cannot be vectorized. (ループはベクトル化されません: 文はベクトル化できません) ...loop was not vectorized: unsupported reduction. (ループはベクトル化されません: サポートされないリダクションです) ...loop was not vectorized: unsupported loop structure. (ループはベクトル化されません: サポートされないループ構造です) ...loop was not vectorized: vectorization possible but seems inefficient. (ループはベクトル化されません: ベクトル化可能ですが非効率です) ...loop was not vectorized: statement cannot be vectorized. (ループはベクトル化されません: 文はベクトル化できません) ...loop was not vectorized: nonstandard loop is not a vectorization candidate. (ループはベクトル化されません: 非標準のループはベクトル化の対象となりません) ...loop was not vectorized: dereference too complex. (ループはベクトル化されません: 参照が複雑すぎます) ...loop was not vectorized: statement cannot be vectorized. (ループはベクトル化されません: 文はベクトル化できません) ...loop was not vectorized: conditional assignment to a scalar. (ループはベクトル化されません: スカラーへの条件付き割り当てです) ...warning #13379: loop was not vectorized with "simd". (ループはベクトル化されません: “simd” はベクトル化されません) ...loop skipped: multiversioned. (ループはスキップされました: マルチバージョン化されました)
特に次のメッセージには注意しなければいけません。
...loop was not vectorized: unsupported loop structure.
(ループはベクトル化されません: サポートされないループ構造です)
KmcTestAppV1.cpp6 では、内部 for ループには 3 つのパートがあることが分かります。
パート 1 – 変数 x、ｙ、ｚ の初期化
... float x = point[k].red - centroid[i].red; float y = point[k].green - centroid[i].green; float z = point[k].blue - centroid[i].blue; ...
パート 2 – ポイント x、y、および z 間の距離を計算
... float distance = std::pow(x, 2) + std::pow(y, 2) + std::pow(z, 2); ...
パート 3 – ‘best_distance’ 変数の更新
...
if (distance < best_distance) {
best_distance = distance;
best_centroid = i;
}
...
これら 3 つのパートが同じ内部 for ループに含まれているため、インテル® C++ コンパイラーは for ループ構造を内部定義されているベクトル化テンプレートと一致させることができません。ベクトル化できない原因は、if 条件文を含むパート 3 にあります。
この問題を解決するには、内部 for ループを次の 3 つのパートに分割します。
... // 距離を計算
for( i = 0; i < nb_cluster; i += 1 )
{
float x = point[k].red - centroid[i].red;
float y = point[k].green - centroid[i].green;
float z = point[k].blue - centroid[i].blue; // パフォーマンス改善: ( x * x ) は
distance[i] = ( x * x ) + ( y * y ) + ( z * z ); // std::pow(x, 2) などの代わりに使用
}
// 最適な距離
for( i = 0; i < nb_cluster; i += 1 )
{
best_distance = ( distance[i] < best_distance ) ? ( float )distance[i] : best_distance;
}
// 最適な重心
for( i = 0; i < nb_cluster; i += 1 )
{
cluster[k] = ( distance[i] < best_distance ) ? ( float )i : best_centroid;
}
...
最も重要な 2 つの変更点は、for ループ内の if 条件文に関係します。
変更前 (オリジナル):
...
if( A < B )
{
D = val1
C = val3
}
...
2 つの条件演算 (? : ) を使用するように変更後:
... D = ( A < B ) ? ( val1 ) : ( val2 ) ... C = ( A < B ) ? ( val3 ) : ( val4 ) ...
2 つの条件演算 (? : ) は、3 項式としても知られています。これで、現代の C/C++ コンパイラーは、この C 言語構造を内部定義のベクトル化テンプレートと一致させることができるようになります。
オリジナルと変更後のソースコードのパフォーマンスを評価
2 つのプログラムを、100 万ポイント、1000 クラスター、および 10 回の反復でテストした結果は次のようになりました。
オリジナルバージョン6:
...>KmcTestAppV1.exe
Time: 111.50
最適化およびベクトル化されたバージョン7:
...>KmcTestAppV2.exe
Time: 20.48
最適化およびベクトル化されたバージョン7 は、オリジナルバージョンのプログラム (1 と 6 を参照) よりも、およそ 5.5 倍高速になりました。’Time’ は秒単位です。
まとめ
現代の C/C++ コンパイラーが for ループのベクトル化に失敗した場合、その複雑性を検証することが重要です。インテル® C++ コンパイラーの場合、’opt-report=n‘ オプションを使用できます (n は 3 以上の値)。
多くの場合、C/C++ コンパイラーは for ループ構造を内部定義されているベクトル化テンプレートに一致させることができないため、ベクトル化することができません。例えば、インテル® C++ コンパイラーでは、次のようなベクトル化診断メッセージが表示されます。
...loop was not vectorized: unsupported reduction.
(ループはベクトル化されません: サポートされないリダクションです)
または
...loop was not vectorized: unsupported loop structure.
(ループはベクトル化されません: サポートされないループ構造です)
この場合、for ループをより簡単な構造に変更するか、#pragma ディレクティブ (#pragma simd など) を使用する EV テクニックの利用を検討するか、組込み関数を使用してアルゴリズムを再実装することを考える必要があります。
著者紹介
Sergey Kostrov は、高度な多岐に渡る C/C++ の経験を持つ、インテル® Black Belt 認定ソフトウェア・エンジニアです。組込み系やデスクトップ、科学アルゴリズム、および大規模なデータセットを扱うハイパフォーマンス・コンピューティング向けの高い移植性を備えた C/C++ ソフトウェアの設計と実装のエキスパートです。
ダウンロード
https://software.intel.com/sites/default/files/managed/e4/76/WhatToDoWhenAVFails.zip
ファイルリスト (ソース、アセンブリー・リスト、ベクトル化レポート):
KmcTestAppV1.cpp
KmcTestAppV2.cpp
TestApp.cpp
TestApp.icc.itype.rpt
TestApp.icc.utype.rpt
TestApp.icc.itype.s
TestApp.icc.utype.s
関連情報
1. 符号なし整数によるベクトル化の失敗? (英語)
https://software.intel.com/en-us/forums/intel-c-compiler/topic/698664
2. インテル® DZ のインテル® C++ コンパイラー・フォーラム (英語):
https://software.intel.com/en-us/forums/intel-c-compiler
3. 簡単な for ループのベクトル化を示すテストプログラム:
TestApp.cpp
4. TestApp.cpp に対するインテル® C++ コンパイラーのベクトル化レポート:
TestApp.icc.itype.rpt
TestApp.icc.utype.rpt
5.1. TestApp.cpp プログラムのケース A の完全なアセンブリー・リスト:
TestApp.icc.itype.s
5.2. TestApp.cpp プログラムのケース B の完全なアセンブリー・リスト:
TestApp.icc.utype.s
6. 変更前のソースコード (KmcTestAppV1.cpp オリジナル)
7. 変更後のソースコード (KmcTestAppV2.cpp 最適化とベクトル化)
コンパイラーの最適化に関する詳細は、最適化に関する注意事項を参照してください。
