Technical data

Analyzing Data Dependencies for Multiprocessing
81
The rest of this section is devoted to analyzing sample loops, some parallel
and some not parallel.
Example 1: Simple Independence
DO 10 I = 1,N
10 A(I) = X + B(I)*C(I)
In this example, each iteration writes to a different location in A, and none
of the variables appearing on the right-hand side is ever written to, only read
from. This loop can be correctly run in parallel. All the variables are SHARE
except for I, which is either LOCAL or LASTLOCAL, depending on
whether the last value of I is used later in the code.
Example 2: Data Dependence
DO 20 I = 2,N
20 A(I) = B(I) - A(I-1)
This fragment contains A(I) on the left-hand side and A(I-1) on the right.
This means that one iteration of the loop writes to a location in A and that
the next iteration reads from that same location. Because different iterations
of the loop read and write the same memory location, this loop cannot be run
in parallel.
Example 3: Stride Not 1
DO 20 I = 2,N,2
20 A(I) = B(I) - A(I-1)
This example looks like the previous example. The difference is that the
stride of the DO loop is now two rather than one. Now A(I) references every
other element of A, and A(I-1) references exactly those elements of A that are
not referenced by A(I). None of the data locations on the right-hand side is
ever the same as any of the data locations written to on the left-hand side.
The data are disjoint, so there is no dependence. The loop can be run in
parallel. Arrays A and B can be declared SHARE, while variable I should be
declared LOCAL or LASTLOCAL.