Community
cancel
Showing results for 
Search instead for 
Did you mean: 
sabbinenisunil
Beginner
45 Views

how to identify dependency between statements automatically

suppose if there are two statements in a for loop
for(i=0;i {

A(I) = B ( I ) + C(I)
B(I + 2) = A(I - 1) + C(I -1)
A(I + 1) = B(2*I + 3) + 1
}
suppose if we run these for I values like 1,2,3

FOR I value 1
S(2) :A(2) = B(2) + C(2)
T(2) :B(4) = A(1) + C(1)
U(2) :A(3) = B(7) + 1
FOR I value 2
S(3) :A(3) = B(3) + C(3)
T(3) :B(5) = A(2) + C(2)
U(3) :A(4) = B(9) + 1

here in B(5) has to be wait for A(2).in sequential programming is concerned it is ok.suppose if it is parallel program it will create ambiguity.

how to identify this types of loop automatically in a program
0 Kudos
1 Reply
jimdempseyatthecove
Black Belt
45 Views

Let's ignore for the moment the issue of when I=0 and you have negative indexing.

B(2) = A(-1) + C(-1)

Which may or may not be a problem

The parallelization tool (i.e. compiler) generally parallelizes the loop by slicing the iteration space.

The compiler can test for dependencies by determining if one slice modifies a different slices data. If so then it generally will not parallize the loop unless directed otherwise.

In this situation, as you have pointed out, you have a temporal issue accross the junctures of the slices.
Not only for the backwards reference of A but also for the forward reference of B.

Your example has a forward look on B at B(2*I +3) with backwards reference (from B(2*I+3)) being modified. Also, the 3rd statement can be boosted out of the loop and written only once. I know that your example is a dummied up piece of code.

Jim Dempsey
Reply