- Mark as New
- Bookmark
- Subscribe
- Mute
- Subscribe to RSS Feed
- Permalink
- Report Inappropriate Content
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
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
Link Copied
1 Reply
- Mark as New
- Bookmark
- Subscribe
- Mute
- Subscribe to RSS Feed
- Permalink
- Report Inappropriate Content
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
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
Topic Options
- Subscribe to RSS Feed
- Mark Topic as New
- Mark Topic as Read
- Float this Topic for Current User
- Bookmark
- Subscribe
- Printer Friendly Page