データ依存性とは、連続したいくつかのループに含まれている各演算の実行順序を制限する関係のことです。ベクトル化を行うと各演算の実行順序が変わるため、自動ベクトライザはデータ依存性の解析が自由にできる何らかの仕組みを持っていなければなりません。例として、データ依存性を持つコードを下に示します。この例に示した配列の各要素の値は、その要素自体とその要素の前後の要素によって決まります。
float data[N]; int i;
for (i=1; i<N-1; i++) { data[i]=data[i-1]*0.25+data[i]*0.5+data[i+1]*0.25; } |
この例に示したループはベクトル化しません。なぜなら、現在の要素 data[i] に書き込まれる内容は、その前の反復のときに 1 つ前の要素 data[i-1] にどんなデータが書き込まれたかによって決まるからです。この例は、わかりやすくするために最初の 2 回の反復で配列がどのようにアクセスするかを表したものです:
for(i=0; i<100; i++) a[i]=b[i]; アクセス パターン 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] の値は 1 回目の反復のときに書き込まれたものになります。ベクトル化を行うためには、元のループのセマンティクスを変えることなく、対象となるすべての反復を並列に実行しなければなりません。
データ依存性の解析とは、2 つのメモリアクセスの重なり合う条件を見つけることです。その条件は、1 つのプログラムの中で参照を 2 回行うと仮定した場合は、次の 2 つの事項によって規定されます:
C++ コンパイラのデータ依存性解析機構で解析をするときは、使用する時間とメモリ領域を次第に増やしながら判定する一連の検定 (判定法) を実行します。どれか 1 つの次元の中にでも独立性が認められれば、それによって依存関係が排除できるため、最初は 1 次元ずつ単純な検定をいくつか実行します。宣言済みの次元境界にまたがる可能性のある多次元配列参照については、線形化された形に変換してから各検定を適用できます。この単純な検定の中には、高速 GCD 検定と拡張限界検定があります。高速 GCD 検定は、ループ添字のすべての係数の最大公約数を求め、その最大公約数で定数項を割り切れない場合を「独立性あり」と判定します。拡張限界検定は、添字式の極値同士の重なり合っていないのを判定します (GCD = greatest common divisor、最大公約数)。
どの単純な検定でも独立性を証明できなかった場合は、最終的に Fourier-Motzkin 法の消去を用いた強力な階層型依存性解法を使用して、すべての次元におけるデータ依存性問題を解きます。