Next: Forall Mask Insertion Up: Optimizations Previous: Forall Dependency

Forall Loop Interchange

Loop interchange is a transformation that exchanges two levels of a nested loop. Loop interchange rearranges the execution order of the statement instances associated with a loop. Loop interchange is one of the most powerful restructuring transformations [65]. It may be used to enhance vectorization, parallelization and memory access of DO-loops. Since is already vectorized and parallelized, our compiler uses loop interchange to improve memory accesses. The transformation is valid since semantics do not specify execution order.

Fortran language stores array in usual column-major order. The Fortran 90D/HPF compiler orders the triplets according to the column major. For example,


                forall(i=1:N,j=1:N) a(i,j) =  b(i, j)

This should be written


           do j=..
              do i=..
                 a(i,j) = b(i, j)
              enddo
           enddo

The rule is that the first index of will be written the last. This can be used to reduce bank conflicts, to enhance efficiency, and to decrease the number of page faults in a virtual memory system by improving the locality of programs.


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