データ依存性

データ依存性とは、連続したいくつかのループに含まれている各演算の実行順序を制限する関係のことです。ベクトル化を行うと各演算の実行順序が変わるため、自動ベクトライザはデータ依存性の解析が自由にできる何らかの仕組みを持っていなければなりません。例として、データ依存性を持つコードを下に示します。この例に示した配列の各要素の値は、その要素自体とその要素の前後の要素によって決まります。

データ依存性を持つループ

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[1]
WRITE data[1]

i=2: READ data[1]
READ data[1]
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 法の消去を用いた強力な階層型依存性解法を使用して、すべての次元におけるデータ依存性問題を解きます。