Identify the dependencies (if there are any) in the following loops. Can you think of ways to organize each loop for more parallelism?
-
DO I=1,N-2 A(I+2) = A(I) + 1.ENDDO -
DO I=1,N-1,2 A(I+1) = A(I) + 1.ENDDO -
DO I=2,N A(I) = A(I-1) * 2.B = A(I-1) ENDDO -
DO I=1,N IF(N .GT. M)A(I) = 1. ENDDO -
DO I=1,N A(I,J) = A(I,K) + BENDDO -
DO I=1,N-1A(I+1,J) = A(I,K) + B ENDDO -
for (i=0; i<n; i++) a[i]= b[i];
Imagine that you are a parallelizing compiler, trying to generate code for the loop below. Why are references to A a challenge? Why would it help to know that K is equal to zero? Explain how you could partially vectorize the statements involving A if you knew that K had an absolute value of at least 8.
DO I=1,N
E(I,M) = E(I-1,M+1) - 1.0B(I) = A(I+K) * C
A(I) = D(I) * 2.0ENDDO The following three statements contain a flow dependency, an antidependency and an output dependency. Can you identify each? Given that you are allowed to reorder the statements, can you find a permutation that produces the same values for the variables
C and
B ? Show how you can reduce the dependencies by combining or rearranging calculations and using temporary variables.
B = A + C
B = C + DC = B + D