{{Short description|Test for determining computer program dependents}} {{notability|date=October 2011}} {{inline|date=January 2021}} In compiler theory, the '''Banerjee test''' is a dependence test. The Banerjee test assumes that all loop indices are independent, however in reality, this is often not true. The Banerjee test is a conservative test. That is, it will not break a dependence that does not exist.
This means that the only thing the test can guarantee is the absence of a dependence.
{| class="wikitable" ! ! Antidependence is broken ! True dependence is broken |- ! True | align="center"| There are no <br /> antidependencies | align="center"| There are no <br /> true dependencies |- ! False | align="center"| There may or may not be <br /> antidependencies | align="center"| There may or may not be <br /> true dependencies |}
==General form== For a loop of the form: <syntaxhighlight lang="c">for(i=0; i<n; i++) { c[f(i)] = a[i] + b[i]; /* statement s1 */ d[i] = c[g(i)] + e[i]; /* statement s2 */ }</syntaxhighlight>
A true dependence exists between statement ''s1'' and statement ''s2'' if and only if :
<math> \exists i, j \in \left [ 0 , n -1 \right] : i \le j ~~ \textrm{and} ~~ f \left ( i \right ) = g \left ( j \right ) \! </math>
An anti dependence exists between statement ''s1'' and statement ''s2'' if and only if :
<math> \exists i, j \in \left [ 0 , n -1 \right] : i > j ~~ \textrm{and} ~~ f \left ( i \right ) = g \left ( j \right ) \! </math>
For a loop of the form: <syntaxhighlight lang="c">for(i=0; i<n; i++) { c[i] = a[g(i)] + b[i]; /* statement s1 */ a[f(i)] = d[i] + e[i]; /* statement s2 */ }</syntaxhighlight>
A true dependence exists between statement ''s1'' and statement ''s2'' if and only if :
<math> \exists i, j \in \left [ 0 , n -1 \right] : i < j ~~ \textrm{and} ~~ f \left ( i \right ) = g \left ( j \right ) \! </math>
==Example==
An example of Banerjee's test follows below.
The loop to be tested for dependence is: <syntaxhighlight lang="c">for(i=0; i<10; i++) { c[i+9] = a[i] + b[i]; /*statement s1*/ d[i] = c[i] + e[i]; /*statement s2*/ }</syntaxhighlight>
Let
<math> \begin{array}{lcr} f(i) \ = \ i + 9 \\ g(j) \ = \ j + 0 . \end{array} </math>
So therefore,
<math> \begin{array}{lcr} a_{0} = 9 \ , \ a_{1} = 1, \\ b_{0} = 0 \ , \ b_{1} = 1. \\ \end{array} </math>
and <math>b_{0} - a_{0} = -9.</math>
===Testing for antidependence===
Then
<math> \begin{array}{lcr} U_{\max} \ = \ \max\left \{a_{1} \times i - b_{1} \times j \right\} ~~ \textrm{when} ~~ 0 \le j < i < n \\ L_{\min} \ = \ \min\left \{a_{1} \times i - b_{1} \times j \right\} ~~ \textrm{when} ~~ 0 \le j < i < n, \\ \end{array} </math>
which gives
<math> \begin{array}{lcr} U_{\max} \ = \ 9 - 0 = 9 \\ L_{\min} \ = \ 1 - 0 = 1. \\ \end{array} </math>
Now, the bounds on <math>b_{0} - a_{0}</math> are <math>1 \le -9 \le 9.</math>
Clearly, -9 is not inside the bounds, so the antidependence is broken.
===Testing for true dependence===
<math> \begin{array}{lcr} U_{max} \ = \ \max\left\{a_{1} \times i - b_{1} \times j \right\} ~~ \textrm{when} ~~ \le i \le j < n \\ L_{min} \ = \ \min\left\{a_{1} \times i - b_{1} \times j \right\} ~~ \textrm{when} ~~ \le i \le j < n. \\ \end{array} </math>
Which gives:
<math> \begin{array}{lcr} U_{max} \ = \ 9 - 9 = 0 \\ L_{min} \ = \ 0 - 9 = -9. \\ \end{array} </math>
Now, the bounds on <math>b_{0} - a_{0}</math> are <math>-9 \le -9 \le 0.</math>
Clearly, -9 is inside the bounds, so the true dependence is not broken.
===Conclusion===
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.
== See also == * GCD test
== References == * Randy Allen and Ken Kennedy. ''Optimizing Compilers for Modern Architectures: A Dependence-based Approach''
* Lastovetsky, Alex. ''Parallel Computing on Heterogenous Networks''
Category:Compilers