• Images
• Videos
• Documents
• Books
• Articles

General form

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)\!}

Example

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.}

Testing for antidependence

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.

Testing for true dependence

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.

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

• Randy Allen and Ken Kennedy. Optimizing Compilers for Modern Architectures: A Dependence-based Approach

• Lastovetsky, Alex. Parallel Computing on Heterogenous Networks