自動ベクトル化

並列コンピューティングにおける自動ベクトル化は、自動並列化の特殊なケースであり、コンピュータ プログラムを、一度に1 組のオペランドを処理するスカラー実装から、一度に複数のオペランドのペアに対して 1 つの操作を処理するベクトル実装に変換します。たとえば、特殊なスーパーコンピュータを含む現代の従来のコンピュータでは、通常、次の 4 つの加算などの操作を同時に実行するベクトル操作があります ( SIMDまたはSPMDハードウェア経由)。

${\displaystyle {\begin{aligned}c_{1}&=a_{1}+b_{1}\\c_{2}&=a_{2}+b_{2}\\c_{3}&=a_{3}+b_{3}\\c_{4}&=a_{4}+b_{4}\end{aligned}}}$

ただし、ほとんどのプログラミング言語では、多くの数値を順番に加算するループを記述するのが一般的です。以下は、 Cで記述されたそのようなループの例です。

i = 0 ; i < n ; i ++の場合、c [ i ] = a [ i ] + b [ i ]となります。       
        

ベクトル化コンパイラは、このようなループをベクトル演算のシーケンスに変換します。これらのベクトル演算は、配列a、bおよびからの要素のブロックに対して加算を実行しますc。自動ベクトル化は、コンピュータサイエンスの主要な研究トピックです。^{[引用が必要]}

初期のコンピュータには通常、1 つの論理ユニットがあり、一度に 1 組のオペランドに対して 1 つの命令を実行していました。そのため、コンピュータ言語とプログラムは順番に実行されるように設計されています。しかし、現代のコンピュータは一度に多くの処理を実行できます。そのため、多くの最適化コンパイラは自動ベクトル化を実行し、順次プログラムの一部を並列処理に変換します。

ループのベクトル化は、各オペランドのペアに処理ユニットを割り当てることによって手続き型ループを変換します。プログラムは、ほとんどの時間をこのようなループ内で費やします。したがって、ベクトル化は、特に大規模なデータセットに対して、ループを大幅に高速化できます。ループのベクトル化は、IntelのMMX、SSE、AVX、Power ISAのAltiVec、ARMのNEON、SVE、SVE2、およびRISC-VのVector Extension命令セットに実装されています。

多くの制約により、ベクトル化が妨げられたり、妨害されたりします。パイプラインの同期やデータ移動のタイミングなどにより、ベクトル化によって実行速度が低下する場合があります。ループ依存性分析では、ループ内の命令の データ依存性に基づいて、ベクトル化できるループを識別します。

自動ベクトル化は、ループ最適化やその他のコンパイル時最適化と同様に、プログラムの動作を正確に保持する必要があります。

誤った結果を防ぐために、実行中にすべての依存関係を尊重する必要があります。

一般に、ループ不変依存関係と語彙的前方依存関係は簡単にベクトル化でき、語彙的後方依存関係は語彙的前方依存関係に変換できます。ただし、すべてのステートメント間の依存関係が元の依存関係に忠実であること を保証するために、これらの変換は安全に実行する必要があります。

循環依存関係は、ベクトル化された命令とは独立して処理する必要があります。

ベクター命令の実行中は、整数の 精度(ビット サイズ) を維持する必要があります。内部整数のサイズと動作に基づいて、正しいベクター命令を選択する必要があります。また、混合整数型の場合、精度を失わずに正しく昇格/降格するには、特別な注意が必要です。符号拡張(複数の整数が同じレジスタ内にパックされるため) やシフト操作、または通常は考慮されるキャリー ビットを含む操作では、特別な注意が必要です。

IEEE-754準拠がオフになっていない限り、浮動小数点の精度も維持する必要があります。IEEE -754 準拠がオフになっている場合、操作は高速になりますが、結果が若干異なる場合があります。IEEE-754 を無視しても大きな変化がある場合は、通常、プログラマーのエラーを意味します。

プログラムをベクトル化するには、コンパイラのオプティマイザが最初にステートメント間の依存関係を理解し​​、必要に応じてそれらを再調整する必要があります。依存関係がマッピングされると、オプティマイザは、適切な候補を複数のデータ項目を操作するベクトル命令に変更して、実装命令を適切に配置する必要があります。

最初のステップは、依存関係グラフを構築し、どのステートメントが他のどのステートメントに依存しているかを特定することです。これには、各ステートメントを調べて、ステートメントがアクセスするすべてのデータ項目を特定し、配列アクセス修飾子を関数にマッピングし、すべてのステートメントですべてのアクセスが他のすべてのアクセスに依存しているかどうかをチェックすることが含まれます。エイリアス分析を使用すると、さまざまな変数がメモリ内の同じ領域にアクセスしている (または交差している) ことを証明できます。

依存関係グラフには、距離がベクター サイズ以下のすべてのローカル依存関係が含まれます。したがって、ベクター レジスタが 128 ビットで、配列タイプが 32 ビットの場合、ベクター サイズは 128/32 = 4 になります。他のすべての非循環依存関係は、同じベクター命令で同時アクセスが発生しないため、ベクター化を無効にすることはありません。

ベクトルのサイズが 4 つの int と同じであると仮定します。

for ( i = 0 ; i < 128 ; i ++ ) { a [ i ] = a [ i -16 ]; // 16 > 4 なので無視しても安全a [ i ] = a [ i -1 ]; // 1 < 4 なので依存グラフ上に留まる}        
       
       

オプティマイザーはグラフを使用して、強く接続されたコンポーネント(SCC) をクラスター化し、ベクトル化可能なステートメントを残りのステートメントから分離できます。

たとえば、ループ内に 3 つのステートメント グループ (SCC1+SCC2)、SCC3、SCC4 の順で含まれているプログラム フラグメントを考えてみましょう。この場合、2 番目のグループ (SCC3) のみがベクトル化されます。最終的なプログラムには、各グループに 1 つずつ、合計 3 つのループが含まれ、中間のループのみがベクトル化されます。オプティマイザーは、ステートメントの実行順序に違反することなく最初のループと最後のループを結合することができず、必要な保証が無効になります。

一部のわかりにくい依存関係は、特定の慣用句に基づいてさらに最適化できます。

たとえば、次の自己データ依存関係は、右側の値 ( RHS ) が取得されて左側の値に格納されるため、割り当て内でデータが変更されることはありません。

a [ i ] = a [ i ] + a [ i + 1 ];    

スカラーによる自己依存性は変数除去によってベクトル化できます。

ループのベクトル化の一般的なフレームワークは、次の 4 つの段階に分かれています。

• Prelude : ループ独立変数をループ内で使用する準備を行う場所です。通常、これには、ベクトル命令で使用される特定のパターンを持つベクトル レジスタへの変数の移動が含まれます。これは、実行時の依存関係チェックを挿入する場所でもあります。チェックによってベクトル化が不可能であると判断された場合は、Cleanupに分岐します。
• ループ: すべてのベクトル化されたループ (またはベクトル化されていないループ)。元のコードに出現する順に SCC クラスターで区切られます。
• 後述: ループに依存しないすべての変数、誘導、および削減を返します。
• クリーンアップ: ループの最後の反復がベクトル サイズの倍数ではない場合、または実行時チェックによってベクトル処理が禁止されている場合は、プレーンな (ベクトル化されていない) ループを実装します。

一部のベクトル化は、コンパイル時に完全にチェックできません。たとえば、ライブラリ関数は、処理するデータが呼び出し元によって提供される場合、最適化を無効にすることができます。このような場合でも、実行時の最適化により、ループをオンザフライでベクトル化できます。

この実行時チェックはプレリュードステージで行われ、レジスタまたはスカラー変数に渡される変数に応じて、可能な場合はフローをベクトル化された命令に誘導し、そうでない場合は標準処理に戻ります。

次のコードは、外部パラメータに依存しないため、コンパイル時に簡単にベクトル化できます。また、どちらもローカル変数であり、実行スタック内にのみ存在するため、言語では、他の変数と同じメモリ領域を占有しないことが保証されています。

int a [ 128 ]; int b [ 128 ]; // bを初期化する 
 


( i = 0 ; i < 128 ; i ++ )の場合、a [ i ] = b [ i ] + 5 ;     
        

一方、以下のコードでは、参照がポインタであり、指すメモリが重複する可能性があるため、メモリ位置に関する情報がありません。

void compute ( int * a 、int * b ) { int i ; for ( i = 0 ; i < 128 ; i ++ 、a ++ 、b ++ ) * a = * b + 5 ; }    

     
             
            

aとbの両方のアドレスとループ反復空間 (128) をランタイムに簡単にチェックするだけで、配列が重複しているかどうかがわかり、依存関係が明らかになります。(C99 以降では、パラメータをrestrictキーワード (ここでは) で修飾すると、 aとbが指すメモリ範囲が重複していないことがコンパイラに伝えられ、上記の例と同じ結果になります。) int *restrict a, int *restrict b

既存のアプリケーションを動的に分析して、コンパイラのさらなる進歩や手動コード変更によって活用できるSIMD並列処理の潜在的な可能性を評価するツールがいくつか存在します。^[1]

例としては、数値データの 2 つのベクトルを乗算するプログラムがあります。スカラー アプローチは次のようになります。

i = 0 ; i < 1024 ; i ++の場合、c [ i ] = a [ i ] * b [ i ]となります。       
        

これをベクトル化すると次のようになります。

( i = 0 ; i < 1024 ; i += 4 )の場合、c [ i : i + 3 ] = a [ i : i + 3 ] * b [ i : i + 3 ] となります。         
        

ここで、c[i:i+3] は c[i] から c[i+3] までの 4 つの配列要素を表し、ベクトル プロセッサは 1 つのベクトル命令に対して 4 つの操作を実行できます。4 つのベクトル操作は 1 つのスカラー命令とほぼ同じ時間で完了するため、ベクトル アプローチは元のコードよりも最大 4 倍高速に実行できます。

コンパイラには 2 つの異なるアプローチがあります。1 つは従来のベクトル化手法に基づいており、もう 1 つはループ アンローリングに基づいています。

従来のベクター マシンで使用されるこの手法は、ループ レベルで SIMD 並列性を見つけて活用しようとします。これは、次の 2 つの主要なステップで構成されます。

1. ベクトル化できる最も内側のループを見つける
2. ループを変換してベクトルコードを生成する

最初のステップでは、コンパイラはベクトル化を妨げる可能性のある障害を探します。ベクトル化の主な障害は、ベクトルの長さよりも短い実際のデータ依存性です。その他の障害には、関数呼び出しや短い反復回数などがあります。

ループがベクトル化可能であると判断されると、ループはベクトル長でストリップマイニングされ、ループ本体内の各スカラー命令は対応するベクトル命令に置き換えられます。以下に、上記の例を使用して、このステップのコンポーネント変換を示します。

• 剥ぎ取り後

i = 0 ; i < 1024 ; i + = 4の場合、j = 0 ; j < 4 ; j ++ の場合、c [ i + j ] = a [ i + j ] * b [ i + j ]となります。         
           
            

• 一時配列を使用したループ分散後

i = 0 ; i < 1024 ; i + = 4の場合{ j = 0 ; j < 4 ; j ++の場合tA [ j ] = A [ i + j ] ; j = 0 ; j < 4 ; j ++の場合tB [ j ] = B [ i + j ] ; j = 0 ; j < 4 ; j ++の場合tC [ j ] = tA [ j ] * tB [ j ] ; j = 0 ; j < 4 ; j ++の場合C [ i + j ] = tC [ j ] ; }         

              
              
                
              

• ベクトルコードに置き換えた後

for ( i = 0 ; i < 1024 ; i += 4 ) { vA = vec_ld ( & A [ i ]); vB = vec_ld ( & B [ i ]); vC = vec_mul ( vA , vB ); vec_st ( vC , & C [ i ]); }         

      
      
       
     

この比較的新しい手法は、特にベクトル長が短い最新のSIMDアーキテクチャを対象としています。^[2]ループを展開して基本ブロック内のSIMD並列処理の量を増やすこともできますが、この手法ではループではなく基本ブロック内のSIMD並列処理を活用します。2つの主要なステップは次のとおりです。

1. 最も内側のループはベクトルの長さの係数で展開され、大きなループ本体を形成します。
2. 同型のスカラー命令 (同じ操作を実行する) は、依存関係によって妨げられない限り、ベクター命令にパックされます。

このアプローチの段階的な変換を示すために、同じ例が再度使用されます。

• ループ展開後（ベクトルの長さで、この場合は4と仮定）

for ( i = 0 ; i < 1024 ; i += 4 ) { sA0 = ld ( & A [ i + 0 ]); sB0 = ld ( & B [ i + 0 ]); sC0 = sA0 * sB0 ; st ( sC0 , & C [ i + 0 ]); ... sA3 = ld ( & A [ i + 3 ]); sB3 = ld ( & B [ i + 3 ]); sC3 = sA3 * sB3 ; st ( sC3 , & C [ i + 3 ]); }         

      
      
        
     
          
      
      
        
     

• 梱包後

( i = 0 ; i < 1024 ; i += 4 )の場合{ ( sA0 、sA1 、sA2 、sA3 ) = ld ( & A [ i + 0 : i + 3 ]); ( sB0 、sB1 、sB2 、sB3 ) = ld ( & B [ i + 0 : i + 3 ]); ( sC0 、sC1 、sC2 、sC3 ) = ( sA0 、sA1 、sA2 、sA3 ) * ( sB0 、sB1 、sB2 、sB3 ); st (( sC0 、sC1 、sC2 、sC3 )、& C [ i + 0 : i + 3 ]); }         

         
         
                 
        

• コード生成後

for ( i = 0 ; i < 1024 ; i += 4 ) { vA = vec_ld ( & A [ i ]); vB = vec_ld ( & B [ i ]); vC = vec_mul ( vA , vB ); vec_st ( vC , & C [ i ]); }         

      
      
       
     

ここで、sA1、sB1、... はスカラー変数を表し、vA、vB、vC はベクトル変数を表します。

自動ベクトル化商用コンパイラのほとんどは、従来のループレベルのアプローチを使用していますが、IBM XLコンパイラ^{[3] [旧ソース]}は両方を使用しています。

ループ本体にif文が存在する場合、変数の複数の値をマージするためにすべての制御パスで命令を実行する必要があります。一般的なアプローチの1つは、一連のコード変換を実行することです：述語→ベクトル化（上記の方法のいずれかを使用）→ベクトル述語の削除→スカラー述語の削除。^[4]次のコードは、これらの変換を示す例として使用されています。

i = 0 ; i < 1024 ; i ++の場合、A [ i ] > 0の場合、C [ i ] = B [ i ]です。それ以外の場合、D [ i ] = D [ i -1 ] です。       
       
          
    
          

• 予測後

( i = 0 ; i < 1024 ; i ++ ) { P = A [ i ] > 0 ; NP = ! P ; C [ i ] = B [ i ]; ( P ) D [ i ] = D [ i -1 ] ; ( NP ) }       

        
      
           
         

ここで、(P) はステートメントを保護する述語を表します。

• ベクトル化後

for ( i = 0 ; i < 1024 ; i += 4 ) { vP = A [ i : i + 3 ] > ( 0 , 0 , 0 , 0 ); vNP = vec_not ( vP ); C [ i : i + 3 ] = B [ i : i + 3 ]; ( vP ) ( NP1 , NP2 , NP3 , NP4 ) = vNP ; D [ i + 3 ] = D [ i + 2 ]; ( NP4 ) D [ i + 2 ] = D [ i + 1 ]; ( NP3 ) D [ i + 1 ] = D [ i ]; ( NP2 ) D [ i ] = D [ i -1 ]; ( NP1 ) }         

            
      
           
         
               
               
                 
                 

• ベクトル述語を削除した後

for ( i = 0 ; i < 1024 ; i += 4 ) { vP = A [ i : i + 3 ] > ( 0 , 0 , 0 , 0 ); vNP = vec_not ( vP ); C [ i : i + 3 ] = vec_sel ( C [ i : i + 3 ], B [ i : i + 3 ], vP ); ( NP1 , NP2 , NP3 , NP4 ) = vNP ; D [ i + 3 ] = D [ i + 2 ]; ( NP4 ) D [ i + 2 ] = D [ i + 1 ]; ( NP3 ) D [ i + 1 ] = D [ i ]; ( NP2 ) D [ i ] = D [ i -1 ]; ( NP1 ) }         

            
      
        
         
               
               
                 
                 

• スカラー述語を削除した後

for ( i = 0 ; i < 1024 ; i += 4 ) { vP = A [ i : i + 3 ] > ( 0 , 0 , 0 , 0 ); vNP = vec_not ( vP ); C [ i : i + 3 ] = vec_sel ( C [ i : i + 3 ], B [ i : i + 3 ], vP ); ( NP1 , NP2 , NP3 , NP4 ) = vNP ; if ( NP4 ) D [ i + 3 ] = D [ i + 2 ]; if ( NP3 ) D [ i + 2 ] = D [ i + 1 ]; if ( NP2 ) D [ i + 1 ] = D [ i ]; if ( NP1 ) D [ i ] = D [ i -1 ]; }         

            
      
        
         
        
        
        
          

ベクトルコードですべての制御パスの命令を実行する必要があることは、スカラーベースラインと比較してベクトルコードの速度を低下させる主な要因の1つです。制御フローが複雑になり、スカラーコードでバイパスされる命令が増えるほど、ベクトル化のオーバーヘッドが大きくなります。このベクトル化のオーバーヘッドを削減するには、スカラー分岐がスカラー命令をバイパスするのと同様に、ベクトル分岐を挿入してベクトル命令をバイパスすることができます。^[5]以下では、AltiVec述語を使用して、これを実現する方法を示します。

• スカラーベースライン（オリジナルコード）

i = 0 ; i < 1024 ; i ++の場合{ A [ i ] > 0の場合{ C [ i ] = B [ i ]の場合; B [ i ] < 0の場合D [ i ] = E [ i ]の場合; } }       

       
    
          
           
              
    

• 制御フローが存在する場合のベクトル化後

for ( i = 0 ; i < 1024 ; i += 4 ) { vPA = A [ i : i + 3 ] > ( 0 , 0 , 0 , 0 ); C [ i : i + 3 ] = vec_sel ( C [ i : i + 3 ], B [ i : i + 3 ], vPA ); vT = B [ i : i + 3 ] < ( 0 , 0 , 0 , 0 ); vPB = vec_sel ( ( 0 , 0 , 0 , 0 ), vT , vPA ); D [ i : i + 3 ] = vec_sel ( D [ i : i + 3 ], E [ i : i + 3 ], vPB ); }         

           
        
        
           
        

• ベクトルブランチを挿入した後

for ( i = 0 ; i < 1024 ; i += 4 ) { if ( vec_any_gt ( A [ i : i + 3 ], ( 0 , 0 , 0 , 0 ))) { vPA = A [ i : i + 3 ] > ( 0 , 0 , 0 , 0 ); C [ i : i + 3 ] = vec_sel ( C [ i : i + 3 ], B [ i : i + 3 ], vPA ); vT = B [ i : i + 3 ] < ( 0 , 0 , 0 , 0 ); vPB = vec_sel ( ( 0 , 0 , 0 , 0 ), vT , vPA ); vec_any_neがvPB 、( 0、0、0、0 )の場合) D [ i : i + 3 ] = vec_sel ( D [ i : i + 3 ] 、E [ i : i + 3 ] 、vPB ) ; } }​​         

         
    
            
            
               
               
             
                
    

ベクトル分岐の最終コードには、注意すべき点が 2 つあります。まず、vPA の述語定義命令も、vec_any_gt を使用して外側のベクトル分岐の本体内に組み込まれます。次に、vPB の内部ベクトル分岐の収益性は、vPA がすべてのフィールドに偽値を持つことを前提として、vPB がすべてのフィールドに偽値を持つ条件付き確率に依存します。

スカラー ベースラインの外側の分岐が常に実行され、ループ本体のほとんどの命令がバイパスされる例を考えてみましょう。上記の中間ケースでは、ベクター分岐がなく、すべてのベクター命令が実行されます。ベクター分岐のある最終コードは、比較と分岐の両方をベクター モードで実行し、スカラー ベースラインよりもパフォーマンスが向上する可能性があります。

ほとんどのCおよびC++コンパイラでは、プログラマの労力と保守性を犠牲にして、 組み込み関数を使用して手動でベクトル化することが可能になります。

• 連鎖（ベクトル処理）
• ベクトルプロセッサ

• GCCコンパイラの自動ベクトル化プロジェクト ページ
• Clang / LLVMコンパイラの自動ベクトル化ドキュメント
• Intel C++ コンパイラ クラシックの自動ベクトル化開発者ガイド