データ依存性とは、連続したいくつかのループに含まれている各演算の実行順序を制限する関係のことです。ベクトル化によって演算の実行順序が並び替えられるため、自動ベクトライザーでは任意のデータの依存性の解析を自由に使用できなければなりません。
データの依存関係によりベクトル化が妨げられる例を次に示します。この例に示す配列の各要素の値は、前の繰返しで計算された前後の要素の値により決まります。
例 1: データ依存性を持つループ |
---|
int i; void dep(float *data) { for (i=1; i<100; i++) data[i] = data[i-1]*0.25 + data[i]*0.5 + data[i+1]*0.25; } |
上記の例に示すループは、ベクトル化できません。これは、現在の要素 DATA(I) への WRITE が直前の要素 DATA(I-1) の使用に依存しており、この要素が直前の反復時にすでに書き込まれ変更されているためです。このことは、次の例に示すように、配列のアクセスパターンの最初の 2 回の反復を見ればわかります。
例 2: データ依存性を持つループをベクトル化したもの |
---|
for(i=0; i<100; i++) a[i]=b[i]; has access pattern read b[0] write a[0] read b[1] write a[1] 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 法の消去を用いた強力な階層型依存性解法を使用して、すべての次元におけるデータ依存性問題を解きます。