Next: Building Array Descriptors Up: Architecture of the Previous: Communication Analysis

Sequentialization

The computation assigned to each processor element will be executed sequentially. Fortran 90D/HPF has to do sequentialization for the program with forall statements after modifing the bounds of forall statements.

There are two main problems in sequentialization: how to create a legal sequentialized version of the parallel construct and reduce the space needed for array temporaries. The fetch-before-store semantics of an array operation or of a forall statement can be stated as follows: the entire right-hand side must be fetched and evaluated before any results can be stored in the left-hand side. Thus, the array operation

 
      a = b + a

or forall statement

 
      forall (i=1:N) a(i) = b(i) + a(i)

can be correctly interpreted by the following two loops:

 
      do i=1,N
        tmp(i) = b(i) + a(i) 
      end do
      do i=1,N
        a(i) = tmp(i)
      end do
Here, the array temporary can be eliminated without changing the semantics of the original forall statement as follows:
 
      do i=1,N
        a(i) = b(i) + a(i) 
      end do
However, the temporary array cannot be simply eliminated for the following forall statement:
 
      forall (i=1:N) a(i) = b(i) + a(i-1)
Various techniques, such as loop reversal, loop interchange, and loop skewing can be applied to eliminate the array temporary in some cases. Sequentialization algorithms can be found in [43], which include algorithms for finding a correct sequentialization, and the use of loop reversal and loop interchange. But these methods exhibit poor spatial locality [44]. The current Fortran 90D/HPF compiler does not perform the loop transformations and complex dependency analysis needed to eliminate temporary usage. However, the compiler checks whether the left hand side () array is used in the right hand side () of the statement. If not, the compiler does not create a temporary.


zbozkus@
Thu Jul 6 21:09:19 EDT 1995