Banerjee Test

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.

General form

For a loop of the form:
for(i=0; i

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

\exists i, j \in \left 0 , n -1 \right: i \le j ~~ \textrm ~~ f \left ( i \right ) = g \left ( j \right ) \!

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

\exists i, j \in \left 0 , n -1 \right: i > j ~~ \textrm ~~ f \left ( i \right ) = g \left ( j \right ) \!

For a loop of the form:
for(i=0; i

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

\exists i, j \in \left 0 , n -1 \right: i < j ~~ \textrm ~~ f \left ( i \right ) = g \left ( j \right ) \!

Example

An example of Banerjee's test follows below.

The loop to be tested for dependence is:
for(i=0; i<10; i++)

Let

$\begin f(i) \ = \ i + 9 \\ g(j) \ = \ j + 0 . \end$

So therefore,

$\begin a_ = 9 \ , \ a_ = 1, \\ b_ = 0 \ , \ b_ = 1. \\ \end$

and $b_ - a_ = -9.$

Testing for antidependence

Then

$\begin U_ \ = \ \max\left \ ~~ \textrm ~~ 0 \le j < i < n \\ L_ \ = \ \min\left \ ~~ \textrm ~~ 0 \le j < i < n, \\ \end$

which gives

$\begin U_ \ = \ 9 - 0 = 9 \\ L_ \ = \ 1 - 0 = 1. \\ \end$

Now, the bounds on $b_ - a_$ are $1 \le -9 \le 9.$

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

Testing for true dependence

$\begin U_ \ = \ \max\left\ ~~ \textrm ~~ \le i \le j < n \\ L_ \ = \ \min\left\ ~~ \textrm ~~ \le i \le j < n. \\ \end$

Which gives:

$\begin U_ \ = \ 9 - 9 = 0 \\ L_ \ = \ 0 - 9 = -9. \\ \end$

Now, the bounds on $b_ - a_{0}$ are $-9 \le -9 \le 0.$

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''

Compilers