データ依存の関係とは、連続したいくつかのループに含まれている各演算の実行順序を制限する関係のことです。ベクトル化によって演算の実行順序が並び替えられるため、自動ベクトライザでは任意のデータ依存性の解析を自由に使用できなければなりません。
データの依存関係によりベクトル化が妨げられる例を次に示します。この例に示す配列の各要素の値は、前の繰返しで計算された前後の要素の値により決まります。
データ依存性を持つループの例:
REAL DATA(0:N)
INTEGER I
DO I=1, N-1
DATA(I) =DATA(I-1)*0.25+DATA(I)*0.5+DATA(I+1)*0.25
END DO
上記の例に示すループは、ベクトル化できません。 これは、現在の要素 DATA(I) への WRITE が直前の要素 DATA(I-1) の使用に依存しており、この要素が直前の反復時にすでに書き込まれ変更されているためです。このことは、次の例に示すように、最初の 2 回の反復における配列のアクセスパターンを見ればわかります。
データ依存性を持つループをベクトル化したものの例:
I=1: READ DATA (0)
READ DATA (1)
READ DATA (2)
WRITE DATA (1)
I=2: READ DATA(1)
READ DATA (2)
READ DATA (3)
WRITE DATA (2)
このループが示す通常のシーケンスでは、2 回目の反復時に読み込まれる DATA(1) の値は、最初の反復時に書き込まれます。ベクトル化を行うためには、元のループのセマンティクスを変えることなく、対象となるすべての反復を並列に実行しなければなりません。
データ依存性の解析とは、2 つのメモリアクセスの重なり合う条件を見つけることです。その条件は、1 つのプログラムの中で参照を 2 回行うと仮定した場合は、次の 2 つの事項によって規定されます。
参照した変数がメモリ内の同一 (オーバラッピング) 領域および配列参照の別名であるかどうか
添字間の関係
IA-32 の場合、配列参照のためのデータ依存アナライザは一連のテストとして構成され、時間とスペースコストに加えて性能においても段階的に強化していきます。どれか 1 つの次元の中にでも独立性が認められれば、それによって依存関係が排除できるため、最初は 1 次元ずつ単純な検定をいくつか実行します。宣言されている次元境界を超える恐れのある多次元配列参照は、テストを実施する前に、線形形式に変換できます。
簡単なテストとして、高速最大公約数 (GCD) テストや拡張限界テストなどを使用できます。GCD テストでは、ループ・インデックスの係数の GCD で定数項を均等に等分できない場合、データの独立性が証明されます。拡張限界テストでは、添字式において極値がオーバラップする可能性があるかどうかをチェックします。どのような簡単なテストでもデータの独立性を証明できなかった場合は、Fourier-Motzkin 消去法を使用する強力な階層化された依存関係ソルバを最終的に用いて、すべての次元におけるデータの依存関係に関する問題を解決します。