how to identify dependency between statements automatically

sabbinenisunil — Tue, 24 Aug 2010 20:41:54 GMT

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

how to identify dependency between statements automatically

jimdempseyatthecove — Wed, 25 Aug 2010 15:37:51 GMT

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

topic how to identify dependency between statements automatically in Intel® Moderncode for Parallel Architectures

how to identify dependency between statements automatically

how to identify dependency between statements automatically