Given the following code there is a backwards dependency.
for(int i=0; i<n; i++) {
(S1): d[i] = a[i-1] * d[i];
(S2): a[i] = b[i] + c[i];
}
My question is how to define / identify these backwards dependencies. As I can't really find a scheme for myself to do this.
This is how I'm currently tackling the issue:
In this example S1 has a anti-dependency on S2 as S1 first reads and S2 writes to the variable.
Further we learned to create a direction vector:
Iteration: read: write
v1:
S1(9) a[8]
S2(9) - a[9]
v2:
S1(10) a[9] -
S2(10) - a[10]
Which would result in direction vecor D_v: D_v = v2 - v1 = (i - 1) - i = -1 = >
Now the solution is to reorder the statements, which is possible as S1 and S2 have no dependencies within the loop.
for(int i=0; i<n; i++) {
(S1): a[i] = b[i] + c[i];
(S2): d[i] = a[i-1] * d[i];
}
Which would result in S1 has a true-dependency on S2 as S1 first writes and S2 reads the variable.
If I repeat to create the direction vector:
Iteration: read: write
v1:
S1(9) - a[9]
S2(9) a[8] -
v2:
S1(10) - a[10]
S2(10) a[9] -
Which would now result in the direction vector D_v: D_v = v2 - v1 = (i + 1) - i = +1 = <
The direction vector now is < instead of > (or +1 instead of -1)
But I just don't see the connection between direction vector and backwards dependency? Is this purly on < or > ?? Can someone clarify how to identify backward dependencies and why exactly the reordering is no backwards dependency anymore (At best with this example)?
As from my point of view we still depend on the last iteration of the loop. But my resources (lecture) says that this is not an backwards dependency anymore and we could vectorize the loop.