バネルジーテスト

コンパイラ理論では、Banerjee テストは依存性テストです。Banerjee テストでは、すべてのループ インデックスが独立していると想定していますが、実際には、これは当てはまらないことがよくあります。Banerjee テストは保守的なテストです。つまり、存在しない依存性は破壊されません。

つまり、テストで保証できるのは依存関係が存在しないということだけです。

次の形式のループの場合:

for ( i = 0 ; i < n ; i ++ ) { c [ f ( i )] = a [ i ] + b [ i ]; /* ステートメント s1 */ d [ i ] = c [ g ( i )] + e [ i ]; /* ステートメント s2 */ }   
         
            

文s1と文s2の間に真の依存関係が存在するのは、次の場合のみです。

${\displaystyle \exists i,j\in \left[0,n-1\right]:i\leq j~~{\textrm {and}}~~f\left(i\right)=g\left(j\right)\!}$

文s1と文s2の間に逆依存関係が存在するのは、次の場合のみです。

${\displaystyle \exists i,j\in \left[0,n-1\right]:i>j~~{\textrm {and}}~~f\left(i\right)=g\left(j\right)\!}$

次の形式のループの場合:

for ( i = 0 ; i < n ; i ++ ) { c [ i ] = a [ g ( i )] + b [ i ]; /* ステートメント s1 */ a [ f ( i )] = d [ i ] + e [ i ]; /* ステートメント s2 */ }   
         
            

文s1と文s2の間に真の依存関係が存在するのは、次の場合のみです。

${\displaystyle \exists i,j\in \left[0,n-1\right]:i<j~~{\textrm {and}}~~f\left(i\right)=g\left(j\right)\!}$

Banerjee のテストの例を以下に示します。

依存性をテストするループは次のとおりです。

for ( i = 0 ; i < 10 ; i ++ ) { c [ i + 9 ] = a [ i ] + b [ i ]; /*ステートメント s1*/ d [ i ] = c [ i ] + e [ i ]; /*ステートメント s2*/ }    
         
            

させて

${\displaystyle {\begin{array}{lcr}f(i)\ =\ i+9\\g(j)\ =\ j+0.\end{array}}}$

したがって、

${\displaystyle {\begin{array}{lcr}a_{0}=9\ ,\ a_{1}=1,\\b_{0}=0\ ,\ b_{1}=1.\\\end{array}}}$

そして${\displaystyle b_{0}-a_{0}=-9.}$

それから

${\displaystyle {\begin{array}{lcr}U_{\max }\ =\ \max \left\{a_{1}\times i-b_{1}\times j\right\}~~{\textrm {when}}~~0\leq j<i<n\\L_{\min }\ =\ \min \left\{a_{1}\times i-b_{1}\times j\right\}~~{\textrm {when}}~~0\leq j<i<n,\\\end{array}}}$

これにより

${\displaystyle {\begin{array}{lcr}U_{\max }\ =\ 9-0=9\\L_{\min }\ =\ 1-0=1.\\\end{array}}}$

さて、境界は${\displaystyle b_{0}-a_{0}}$${\displaystyle 1\leq -9\leq 9.}$

明らかに、-9 は境界内にないため、反依存性は破られています。

${\displaystyle {\begin{array}{lcr}U_{max}\ =\ \max \left\{a_{1}\times i-b_{1}\times j\right\}~~{\textrm {when}}~~\leq i\leq j<n\\L_{min}\ =\ \min \left\{a_{1}\times i-b_{1}\times j\right\}~~{\textrm {when}}~~\leq i\leq j<n.\\\end{array}}}$

つまり、次のようになります。

${\displaystyle {\begin{array}{lcr}U_{max}\ =\ 9-9=0\\L_{min}\ =\ 0-9=-9.\\\end{array}}}$

さて、境界は${\displaystyle b_{0}-a_{0}}$${\displaystyle -9\leq -9\leq 0.}$

明らかに、-9 は境界内にあるため、真の依存関係は壊れていません。

反依存性が破られたため、文の間に反依存性は存在しないと断言できます。

真の依存関係が壊れていないため、ステートメント間に真の依存関係が存在するかどうかはわかりません。

したがって、ループは並列化可能ですが、ステートメントは（潜在的な）真の依存関係の順序で実行する必要があります。

• GCD テスト

• ランディ・アレンとケン・ケネディ。現代のアーキテクチャのためのコンパイラの最適化：依存関係ベースのアプローチ

• アレックス・ラストヴェツキー。異種ネットワーク上の並列コンピューティング