Qfyilyi

I'm trying to understand a paper concerning the detection of dependence for parallelizing tasks and I'm struggling a bit with an example. Considering A, B, C and D are vectors object:

    do I=2,N

S1:    A(I) = B(I) + C(I)

S2:    D(I) = A(I + 1) + 1

S3:    C(I) = D(I)

Focusing on dependence between S1 and S2. To me, it is a flow dependence S1 -> S2, A is in OUT(S1) and IN(S2) and A is indeed used in S2, verifying the flow dependence definition given by Woolfe & Banerjee. However, the explication states that it is an antidependence S2 -> S1. Is it because we're inside a loop ? And in that case, does it mean that in a loop, any flow dependence is reverse antidependence and inversely ?

Okay, finally it depends not of the object, but of the memory location being used. In this example, A(I) and A(I + 1) may not refer to the same memory (in case there is no aliasing). So there is no dependence between them in the current iteration. However, if we unroll the loop a bit, we get:

do I=2,N

  S1:    A(I) = B(I) + C(I)

  S2:    D(I) = -> A(I + 1) + 1

  S3:    C(I) = D(I)

  S1:    -> A(I + 1) = B(I + 1) + C(I + 1)

  S2:    D(I + 1) = A(I + 2) + 1

  S3:    C(I + 1) = D(I + 1)

Now, the anti dependence appears clearly.

Seems obvious now..