Technical data

84
Chapter 5: Fortran Enhancements for Multiprocessors
At first glance, this loop looks like it cannot be run in parallel because it uses
both W(I) and W(I-K). Closer inspection reveals that because the value of I
varies between K+1 and 2*K, then I-K goes from 1 to K. This means that the
W(I-K) term varies from W(1) up to W(K), while the W(I) term varies from
W(K+1) up to W(2*K). So W(I-K) in any iteration of the loop is never the
same memory location as W(I) in any other iterations. Because there is no
data overlap, there are no data dependencies. This loop can be run in
parallel. Elements W, B, and K can be declared SHARE, while variable I
should be declared LOCAL or LASTLOCAL.
This example points out a general rule: the more complex the expression
used to index an array, the harder it is to analyze. If the arrays in a loop are
indexed only by the loop index variable, the analysis is usually
straightforward though tedious. Fortunately, in practice most array indexing
expressions are simple.
Example 9: Inconsequential Data Dependence
INDEX = SELECT(N)
DO I = 1, N
A(I) = A(INDEX)
END DO
There is a data dependence in this loop because it is possible that at some
point I will be the same as INDEX, so there will be a data location that is
being read and written by different iterations of the loop. In this particular
special case, you can simply ignore it. You know that when I and INDEX are
equal, the value written into A(I) is exactly the same as the value that is
already there. The fact that some iterations of the loop will read the value
before it is written and some after it is written is not important because they
will all get the same value. Therefore, this loop can be parallelized. Array A
can be declared SHARE, while variable I should be declared LOCAL or
LASTLOCAL.
Example 10: Local Array
DO I = 1, N
D(1) = A(I,1) - A(J,1)
D(2) = A(I,2) - A(J,2)
D(3) = A(I,3) - A(J,3)
TOTAL_DISTANCE(I,J) = SQRT(D(1)**2 + D(2)**2 + D(3)**2)
END DO