Technical data

Breaking Data Dependencies
85
In this fragment, each iteration of the loop uses the same locations in the D
array. However, closer inspection reveals that the entire D array is being
used as a temporary. This can be multiprocessed by declaring D to be
LOCAL. The Fortran compiler allows arrays (even multidimensional arrays)
to be LOCAL variables with one restriction: the size of the array must be
known at compile time. The dimension bounds must be constants; the
LOCAL array cannot have been declared using a variable or the asterisk
syntax.
Therefore, this loop can be parallelized. Arrays TOTAL_DISTANCE and A
can be declared SHARE, while array D and variable I should be declared
LOCAL or LASTLOCAL.
Breaking Data Dependencies
Many loops that have data dependencies can be rewritten so that some or all
of the loop can be run in parallel. The essential idea is to locate the
statement(s) in the loop that cannot be made parallel and try to find another
way to express it that does not depend on any other iteration of the loop. If
this fails, try to pull the statements out of the loop and into a separate loop,
allowing the remainder of the original loop to be run in parallel.
The first step is to analyze the loop to discover the data dependencies (see
“Writing Parallel Fortran” on page 71). Once the problem areas are
identified, various techniques can be used to rewrite the code to break the
dependence. Sometimes the dependencies in a loop cannot be broken, and
you must either accept the serial execution rate or try to discover a new
parallel method of solving the problem. The rest of this section is devoted to
a series of “cookbook” examples on how to deal with commonly occurring
situations. These are by no means exhaustive but cover many situations that
happen in practice.
Example 1: Loop Carried Value
INDX = 0
DO I = 1, N
INDX = INDX + I
A(I) = B(I) + C(INDX)
END DO