Banerjee test

<h2 id="general-form">General form</h2>
For a loop of the form:

for(i=0; i<n; i++) {
 c[f(i)] = a[i] + b[i]; /* statement s1 */
 d[i] = c[g(i)] + e[i]; /* statement s2 */
}

A true dependence exists between statement s1 and statement s2 if and only if :

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

An anti dependence exists between statement s1 and statement s2 if and only if :

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

For a loop of the form:

for(i=0; i<n; i++) {
 c[i] = a[g(i)] + b[i]; /* statement s1 */
 a[f(i)] = d[i] + e[i]; /* statement s2 */
}

A true dependence exists between statement s1 and statement s2 if and only if :

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

<h2 id="example">Example</h2>
An example of Banerjee's test follows below.
The loop to be tested for dependence is:

for(i=0; i<10; i++) {
 c[i+9] = a[i] + b[i]; /*statement s1*/
 d[i] = c[i] + e[i]; /*statement s2*/
}

Let

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

So therefore,

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

and 
 
 
 
 
 b
 
 0
 
 
 −
 
 a
 
 0
 
 
 =
 −
 9.
 
 
 {\displaystyle b_{0}-a_{0}=-9.}

<h3>Testing for antidependence</h3>
Then

 
 
 
 
 
 
 
 
 U
 
 max
 
 
  
 =
  
 max
 
 {
 
 
 a
 
 1
 
 
 ×
 i
 −
 
 b
 
 1
 
 
 ×
 j
 
 }
 
  
  
 
 
 when
 
 
  
  
 0
 ≤
 j
 <
 i
 <
 n
 
 
 
 
 
 L
 
 min
 
 
  
 =
  
 min
 
 {
 
 
 a
 
 1
 
 
 ×
 i
 −
 
 b
 
 1
 
 
 ×
 j
 
 }
 
  
  
 
 
 when
 
 
  
  
 0
 ≤
 j
 <
 i
 <
 n
 ,
 
 
 
 
 
 
 {\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}}}

which gives

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

Now, the bounds on 
 
 
 
 
 b
 
 0
 
 
 −
 
 a
 
 0
 
 
 
 
 {\displaystyle b_{0}-a_{0}}
 
 are 
 
 
 
 1
 ≤
 −
 9
 ≤
 9.
 
 
 {\displaystyle 1\leq -9\leq 9.}

Clearly, -9 is not inside the bounds, so the antidependence is broken.

<h3>Testing for true dependence</h3>

 
 
 
 
 
 
 
 
 U
 
 m
 a
 x
 
 
  
 =
  
 max
 
 {
 
 
 a
 
 1
 
 
 ×
 i
 −
 
 b
 
 1
 
 
 ×
 j
 
 }
 
  
  
 
 
 when
 
 
  
  
 ≤
 i
 ≤
 j
 <
 n
 
 
 
 
 
 L
 
 m
 i
 n
 
 
  
 =
  
 min
 
 {
 
 
 a
 
 1
 
 
 ×
 i
 −
 
 b
 
 1
 
 
 ×
 j
 
 }
 
  
  
 
 
 when
 
 
  
  
 ≤
 i
 ≤
 j
 <
 n
 .
 
 
 
 
 
 
 {\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}}}

Which gives:

 
 
 
 
 
 
 
 
 U
 
 m
 a
 x
 
 
  
 =
  
 9
 −
 9
 =
 0
 
 
 
 
 
 L
 
 m
 i
 n
 
 
  
 =
  
 0
 −
 9
 =
 −
 9.
 
 
 
 
 
 
 {\displaystyle {\begin{array}{lcr}U_{max}\ =\ 9-9=0\\L_{min}\ =\ 0-9=-9.\\\end{array}}}

Now, the bounds on 
 
 
 
 
 b
 
 0
 
 
 −
 
 a
 
 0
 
 
 
 
 {\displaystyle b_{0}-a_{0}}
 
 are 
 
 
 
 −
 9
 ≤
 −
 9
 ≤
 0.
 
 
 {\displaystyle -9\leq -9\leq 0.}

Clearly, -9 is inside the bounds, so the true dependence is not broken.

<h3>Conclusion</h3>
Because the antidependence was broken, we can assert that anti dependence does not exist between the statements.
Because the true dependence was not broken, we do not know if a true dependence exists between the statements.
Therefore, the loop is parallelisable, but the statements must be executed in order of their (potential) true dependence.

<h2 id="see-also">See also</h2>
<ul><li><a href="/facts/GCD_test/DwplNMNk">GCD test</a></li></ul>

<ul><li>Randy Allen and Ken Kennedy. Optimizing Compilers for Modern Architectures: A Dependence-based Approach</li></ul>
<ul><li>Lastovetsky, Alex. Parallel Computing on Heterogenous Networks</li></ul>

Banerjee test open-in-new

Banerjee test