# Banerjee test

> Mediated Wiki article. Canonical URL: https://mediated.wiki/source/Banerjee_test
> Markdown URL: https://mediated.wiki/source/Banerjee_test.md
> Source: https://en.wikipedia.org/wiki/Banerjee_test
> Source revision: 1337865502
> License: Creative Commons Attribution-ShareAlike 4.0 International (https://creativecommons.org/licenses/by-sa/4.0/)

{{Short description|Test for determining computer program dependents}}
{{notability|date=October 2011}}
{{inline|date=January 2021}}
In [compiler theory](/source/compiler_theory), the '''Banerjee test''' is a [dependence test](/source/dependence_analysis). 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](/source/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

---
Adapted from the Wikipedia article [Banerjee test](https://en.wikipedia.org/wiki/Banerjee_test) by Wikipedia contributors ([contributor history](https://en.wikipedia.org/wiki/Banerjee_test?action=history)). Available under [Creative Commons Attribution-ShareAlike 4.0 International](https://creativecommons.org/licenses/by-sa/4.0/). Changes may have been made.