Technical data

Breaking Data Dependencies
87
C$DOACROSS LOCAL(IX, IY, I)
DO I = 1, N
IX = INDEXX(I)
IY = INDEXY(I)
XFORCE(I) = XFORCE(I) + NEWXFORCE(IX)
YFORCE(I) = YFORCE(I) + NEWYFORCE(IY)
IXX(I) = IXOFFSET(IX)
IYY(I) = IYOFFSET(IY)
END DO
DO 100 I = 1, N
TOTAL(IXX(I),IYY(I)) = TOTAL(IXX(I), IYY(I)) + EPSILON
100 CONTINUE
Here, IXX and IYY have been turned into arrays to hold all the values
computed by the first loop. The first loop (containing most of the work) can
now be run in parallel. Only the second loop must still be run serially.
Before we leave this example, note that, if we were certain that the value for
IXX was always different in every iteration of the loop, then the original loop
could be run in parallel. It could also be run in parallel if IYY was always
different. If IXX (or IYY) is always different in every iteration, then
TOTAL(IXX,IYY) is never the same location in any iteration of the loop, and
so there is no data conflict.
This sort of knowledge is, of course, program-specific and should always be
used with great care. It may be true for a particular data set, but to run the
original code in parallel as it stands, you need to be sure it will always be true
for all possible input data sets.
Example 3: Recurrence
DO I = 1,N
X(I) = X(I-1) + Y(I)
END DO
This is an example of recurrence, which exists when a value computed in one
iteration is immediately used by another iteration. There is no good way of
running this loop in parallel. If this type of construct appears in a critical
loop, try pulling the statement(s) out of the loop as in the previous example.
Sometimes another loop encloses the recurrence; in that case, try to
parallelize the outer loop.