The topic of this article may not meet Misplaced Pages's general notability guideline. Please help to demonstrate the notability of the topic by citing reliable secondary sources that are independent of the topic and provide significant coverage of it beyond a mere trivial mention. If notability cannot be shown, the article is likely to be merged, redirected, or deleted. Find sources: "Banerjee test" – news · newspapers · books · scholar · JSTOR (October 2011) (Learn how and when to remove this message) |
This article includes a list of references, related reading, or external links, but its sources remain unclear because it lacks inline citations. Please help improve this article by introducing more precise citations. (January 2021) (Learn how and when to remove this message) |
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.
Antidependence is broken | True dependence is broken | |
---|---|---|
True | There are no antidependencies |
There are no true dependencies |
False | There may or may not be antidependencies |
There may or may not be true dependencies |
General form
For a loop of the form:
for(i=0; i<n; i++) { c = a + b; /* statement s1 */ d = c + e; /* statement s2 */ }
A true dependence exists between statement s1 and statement s2 if and only if :
An anti dependence exists between statement s1 and statement s2 if and only if :
For a loop of the form:
for(i=0; i<n; i++) { c = a + b; /* statement s1 */ a = d + e; /* statement s2 */ }
A true dependence exists between statement s1 and statement s2 if and only if :
Example
An example of Banerjee's test follows below.
The loop to be tested for dependence is:
for(i=0; i<10; i++) { c = a + b; /*statement s1*/ d = c + e; /*statement s2*/ }
Let
So therefore,
and
Testing for antidependence
Then
which gives
Now, the bounds on are
Clearly, -9 is not inside the bounds, so the antidependence is broken.
Testing for true dependence
Which gives:
Now, the bounds on are
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
References
- Randy Allen and Ken Kennedy. Optimizing Compilers for Modern Architectures: A Dependence-based Approach
- Lastovetsky, Alex. Parallel Computing on Heterogenous Networks