Privatizing loop variables

loop_private

The loop_private directive and pragma declares a list of variables and/or arrays private to the immediately following Fortran DO or C for loop. loop_private array dimensions must be identifiable at compile-time.

The compiler assumes that data objects declared to be loop_private have no loop-carried dependences with respect to the parallel loops in which they are used. If dependences exist, they must be handled manually using the synchronization directives and techniques.

Each parallel thread of execution receives a private copy of the loop_private data object for the duration of the loop. No starting values are assumed for the data. Unless a save_last directive or pragma is specified, no ending value is assumed. If a loop_private data object is referenced within an iteration of the loop, it must be assigned a value previously on that same iteration.

The form of this directive and pragma is shown in Table 6-2 “Form of loop_private directive and pragma”.

where

C$DIR LOOP_PRIVATE(S)
      DO I = 1, N
C       S IS ONLY CORRECTLY PRIVATE IF AT LEAST
C       ONE IF TEST PASSES ON EACH ITERATION:
        IF(A(I) .GT. 0) S = A(I)
        IF(U(I) .LT. V(I)) S = V(I)
        IF(X(I) .LE. Y(I)) S = Z(I)
        B(I) = S * C(I) + D(I)
      ENDDO 

A potential loop-carried dependence on S exists in this example. If none of the IF tests are true on a given iteration, the value of S must wrap around from the previous iteration. The LOOP_PRIVATE(S) directive indicates to the compiler that S does, in fact, get assigned on every iteration, and therefore it is safe to parallelize this loop.

If on any iteration none of the IF tests pass, an actual LCD exists and privatizing S results in wrong answers.

loop_parallel loops, you must manually privatize loop data requiring privatization. This is easily done using the loop_private directive or pragma.

The following Fortran example shows how loop_private manually privatizes loop data:

      SUBROUTINE PRIV(X,Y,Z)
      REAL X(1000), Y(4,1000), Z(1000)
      REAL XMFIED(1000)
C$DIR LOOP_PARALLEL, LOOP_PRIVATE(XMFIED, J)
      DO I = 1, 4
C   INITIALIZE XMFIED; MFY MUST NOT WRITE TO X:
        CALL MFY(X, XMFIED)
        DO J = 1, 999 
          IF (XMFIED(J) .GE. Y(I,J)) THEN
            Y(I,J) = XMFIED(J) * Z(J)
          ELSE
            XMFIED(J+1) = XMFIED(J)
          ENDIF
        ENDDO
      ENDDO
      END

Here, the LOOP_PARALLEL directive is required to parallelize the I loop because of the call to MFY. The X and Y arrays are in shared memory by default. X and Z are not written to, and the portions of Y written to in the J loop’s IF statement are disjoint, so these shared arrays require no special attention. The local array XMFIED, however, is written to. But because XMFIED carries no values into or out of the I loop, it is privatized using LOOP_PRIVATE. This gives each thread running the I loop its own private copy of XMFIED, eliminating the expensive necessity of synchronized access to XMFIED.

Note that an LCD exists for XMFIED in the J loop, but because this loop runs serially on each processor, the dependence is safe.

Denoting induction variables in parallel loops

To safely parallelize a loop with the loop_parallel directive or pragma, the compiler must be able to correctly determine the loop’s primary induction variable.

The compiler can find primary Fortran DO loop induction variables. It may, however, have trouble with DO WHILE or customized Fortran loops, and with all loop_parallel loops in C. Therefore, when you use the loop_parallel directive or pragma to manually parallelize a loop other than an explicit Fortran DO loop, you should indicate the loop’s primary induction variable using the IVAR=indvar attribute to loop_parallel.

Example 6-3 Denoting induction variables in parallel loops

Consider the following Fortran example:

I = 1 C$DIR LOOP_PARALLEL(IVAR = I) 10 A(I) = ... . . ! ASSUME NO DEPENDENCES . I = I + 1 IF(I .LE. N) GOTO 10

The above is a customized loop that uses I as its primary induction variable. To ensure parallelization, the LOOP_PARALLEL directive is placed immediately before the start of the loop, and the induction variable, I, is specified.

Example 6-4 Denoting induction variables in parallel loops

Primary induction variables in C loops are difficult for the compiler to find, so

ivar is required in all loop_parallel C loops. Its use is shown in the following example:

#pragma _CNX loop_parallel(ivar=i) for(i=0; i<n; i++) { a[i] = ...; . . /* assume no dependences */ . } }

Secondary induction variables

Secondary induction variables are variables used to track loop iterations, even though they do not appear in the Fortran DO statement. They cannot appear in addition to the primary induction variable in the C for statement.

Such variables must be a function of the primary loop induction variable, and they cannot be independent. Secondary induction variables must be assigned loop_private.

Example 6-5 Secondary induction variables

The following Fortran example contains an incorrectly incremented secondary induction variable:

C WARNING: INCORRECT EXAMPLE!!!! J = 1 C$DIR LOOP_PARALLEL DO I = 1, N J = J + 2 ! WRONG!!!

In this example, J does not produce expected values in each iteration because multiple threads are overwriting its value with no synchronization. The compiler cannot privatize J because it is a loop-carried dependence (LCD). This example is corrected by privatizing J and making it a function of I, as shown below.

C CORRECT EXAMPLE: J = 1 C$DIR LOOP_PARALLEL C$DIR LOOP_PRIVATE(J) ! J IS PRIVATE DO I = 1, N J = (2*I)+1 ! J IS PRIVATE

As shown in the preceding example, J is assigned correct values on each iteration because it is a function of I and is safely privatized.

Example 6-6 Secondary induction variables

In C, secondary induction variables are sometimes included in

for statements, as shown in the following example:

/* warning: unparallelizable code follows */ #pragma _CNX loop_parallel(ivar=i) for(i=j=0; i<n;i++,j+=2) { a[i] = ...; . . . } }

Because secondary induction variables must be private to the loop and must be a function of the primary induction variable, this example cannot be safely parallelized using loop_parallel(ivar=i). In the presence of this directive, the secondary induction variable is not recognized.

To manually parallelize this loop, you must remove j from the for statement, privatize it, and make it a function of i.

The following example demonstrates how to restructure the loop so that j is a valid secondary induction variable:

#pragma _CNX loop_parallel(ivar=i) #pragma _CNX loop_private(j) for(i=0; i<n; i++) { j = 2*i; a[i] = ...; . . . } }

This method runs faster than placing j in a critical section because it requires no synchronization overhead, and the private copy of j used here can typically be more quickly accessed than a shared variable.

save_last[(list)]

A save_last directive or pragma causes the thread that executes the last iteration of the loop to write back the private (or local) copy of the variable into the global reference.

The save_last directive and pragma allows you to save the final value of loop_private data objects assigned in the last iteration of the immediately following loop.

The values for this directive and pragma must be assigned in the last iteration. If the assignment is executed conditionally, it is your responsibility to ensure that the condition is met and the assignment executes. Inaccurate results may occur if the assignment does not execute on the last iteration. For loop_private arrays, only those elements of the array assigned on the last iteration are saved.

The form of this directive and pragma is shown in Table 6-3 “Form of save_last directive and pragma”.

save_last must appear immediately before or after the associated loop_private directive or pragma, or on the same line.

#pragma _CNX loop_parallel(ivar=i)
#pragma _CNX loop_private(atemp, x, y)
#pragma _CNX save_last(atemp, x)
for(i=0;i<n;i++) {
  if(i==d[i]) atemp = a[i];
  if(i==e[i]) atemp = b[i];
  if(i==f[i]) atemp = c[i];
  a[i] = b[i] + c[i];
  b[i] = atemp;
  x = atemp * a[i];
  y = atemp * c[i];
}
. 
. 
. 
if(atemp > amax) {
. 
. 
. 

In this example, the loop_private variable atemp is conditionally assigned in the loop. In order for atemp to be truly private, you must be sure that at least one of the conditions is met so that atemp is assigned on every iteration.

When the loop terminates, the save_last pragma ensures that atemp and X contain the values they are assigned on the last iteration. These values can then be used later in the program. The value of y, however, is not available once the loop finishes because y is not specified as an argument to save_last.

save_last directive and pragma is misleading.

The following Fortran code provides an example of this:

C$DIR LOOP_PARALLEL
C$DIR LOOP_PRIVATE(S)
C$DIR SAVE_LAST
      DO I = 1, N
        IF(G(I) .GT. 0) THEN
          S = G(I) * G(I)
        ENDIF
      ENDDO

While it may appear that the last value of S assigned is saved in this example, you must remember that the SAVE_LAST directive applies only to the last (Nth) iteration, with no regard for any conditionals contained in the loop. For SAVE_LAST to be valid here, G(N) must be greater than 0 so that the assignment to S takes place on the final iteration.

Obviously, if this condition is predicted, the loop is more efficiently written to exclude the IF test, so the presence of a SAVE_LAST in such a loop is suspect.