Subject: FYI - on FORALL

From: David Loveman <[email-masked]>
Date: Mon, 27 Jul 92 08:43:43 PDT

I presented a technical note entitled "Element Array Assignment - the
FORALL Statement" at the Third Workshop on Compilers for Parallel
Computers, Vienna, Austria, July 6-9, 1992.  It contained two items
that might be of interest:  an "optimized" scalarization of the single
statement FORALL and a "compendium" of FORALL examples culled from a
variety of sources.  Enjoy!

Efficient Implementation of the FORALL Statement

A forall-stmt has the general form:

FORALL (v1=l1:u1:s1, v2=l1:u2:s2, ..., vn=ln:un:sn [, mask] ) &
      a(e1,...,em) = rhs

A careful analysis of the scalarized definition of FORALL, given the
language prohibitions against side-effects in statements, permits a
more efficient scalarized implementation of FORALL:

templ1 = l1
tempu1 = u1
temps1 = s1
templ2 = l2
tempu2 = u2
temps2 = s2
  ...
templn = ln
tempun = un
tempsn = sn
tempa = a   ! array assignment
DO v1=templ1,tempu1,temps1
  DO v2=templ2,tempu2,temps2
    ...
      DO vn=templn,tempun,tempsn
        IF mask THEN
          tempa(e1,...,em) = rhs
        END IF
      END DO
	  ...
  END DO
END DO
a = tempa   ! array assignment

In many cases, compiler optimizations such as copy propagation can
eliminate the requirement for temporaries for lower bounds, upper
bounds and strides.  Similarly, dependence analysis may eliminate the
requirement for the array temporary.  Thus a FORALL statement such as
(Eugene Albert, Joan D. Lukas, and Guy L. Steele, Jr., Data Parallel
Computers and the FORALL Statement, Journal of Parallel and Distributed
Computing, October 1991)

FORALL (I=1:N, J=1:M:2) A(I,J) = I * B(J)

could be implemented on a scalar machine as

DO I=1,N
  DO J=1,M,2
    A(I,J) = I * B(J)
  END DO
END DO

On a parallel SIMD or MIMD machine it can, of course, be implemented in parallel.

Examples of the FORALL Statement

This section presents examples of the FORALL statement from several
sources:  the Fortran 8x definition, a paper on the FORALL statement by
Albert, Lukas, and Steele, the Thinking Machines Language Reference
Manual, and other sources:

PROGRAM FORALL_EXAMPLES

! the examples assume the following declarations
! initial values are arbitrary
  INTEGER, PARAMETER  :: L = 100, M = 100, N = 100
  INTEGER :: ONE = 1, ZERO = 0
  INTEGER, DIMENSION (L) :: V = (/ 1:L /), U = (/ L:1:-1 /)
  INTEGER, DIMENSION (M,N) :: IND
  REAL, DIMENSION (L) :: R, S = 5.3
  REAL, DIMENSION (M,N) :: A, B, C=26.2
  REAL, DIMENSION (M,N,10) :: G
  IND = SPREAD((/(I,I=1,M)/),2,N)

! examples derived from the Fortran 8x (S8.104) definition of FORALL

  FORALL (I=1:M, J=1:N) A(I,J) = 1.0 / REAL(I + J - 1)
  FORALL (I=1:M, J=1:N, A(I,J) /= 0.0) B(I,J) = 1.0 / A(I,J)
  ! which is the same as
  WHERE (A /= 0.0) B = 1.0 / A

! examples derived from the paper by Albert, Lukas, and Steele
! with natural Fortran 90 equivalents

! right hand side not evaluated, division by 0 does not occur
  FORALL (I=1:L:-1) R(I) = ONE/ZERO
  FORALL (I=1:L, I > 200) R(I) = ONE/ZERO

! operations on rectangular array sections
  ! the FORALL in effect gives a name to a section triplet
  FORALL (I=1:L) R(I) = S(I) ! which is the same as
  R(1:L) = S(1:L) ! which is the same as 
  R = S ! since R and S are both of length L
  FORALL (I=1:10:2, J=10:1:-1) A(I,J) = B(I,J) * C(I,J) 
  ! which is equivalent to
  A(1:10:2, 10:1:-1) = B(1:10:2, 10:1:-1) * C(1:10:2, 10:1:-1)

! computational use of subscript values in one dimension
  FORALL (I=1:100) R(I) = I 
  ! which is equivalent to the use of an array constructor
  R = (/ 1:100 /)

! certain cases of spreading
  FORALL (I=1:10, J=1:20) A(I, J) = S(I) 
  ! which is equivalent to the implied spread
  A(1:10, 1:20) = SPREAD(S(1:10), DIM=2, NCOPIES=20) 

! vector valued subscripts
  FORALL (I=1:L) R(V(I)) = S(I)         ! which is equivalent to 
  R(V(1:L)) = S(1:100)                  ! which is equivalent to
  R(V) = S                       ! since V and S are of length 100

  FORALL (I=1:10, J=1:10)  &
     A(V(I), U(J)) = S(I)                
  ! which is equivalent to the implied spread
  A(V, U) = SPREAD( S, DIM=2, NCOPIES=100)

! permutation of two axes
  FORALL (I=1:M, J=1:N)  A(I,J) = B(J, I) ! which is equivalent to
  A = TRANSPOSE(B)

! examples derived from the paper by Albert, Lukas, and Steele
! without natural Fortran 90 equivalents

! skewed sections of arrays
  FORALL (I=1:100) A(I, I) = B(I, I) ! diagonal
  FORALL (I=1:100) A(I, I) = B(I+1, I-1)
  FORALL (I=1:M, J=1:N, K=1:10, I+J+K .EQ. 3*(N+1)/2)   &
     A(I+J-K, J) = G(I, J, K)

! use of multiple subscript values in an expression
  FORALL (I=1:10, J=1:20, K=1:30)   &
     G(I, J, K) = I + J + K
  ! which is (not obviously) equivalent to
  G(1:10, 1:20, 1:30) = SPREAD(SPREAD((/ 1:10 /), 2, 20), 3, 30)  & 
                      + SPREAD(SPREAD((/ 1:20 /), 1, 10), 3, 30)  &
                      + SPREAD(SPREAD((/ 1:30 /), 1, 10), 2, 20) 

! multi-dimensional array-valued subscripts
  FORALL (I=1:100, J=1:100) R(IND(I, J)) = B(I, J)

! scatter addressing
  FORALL (I=1:100) A(U(I), V(I)) = S(I)
  FORALL (I=2:100) R(I) = R(I/2) ! array representing a binary tree

! axis transpositions with more than 2 axes
  FORALL (I=1:100, J=1:100, K=1:100) G(I, J, K) = G(J, K, I)
  FORALL (I=1:100, J=1:100, K=1:100) G(I, J, K) = G(J, 11-K, I+1)

! parallel prefix operations
  FORALL(I=1:100) R(I) = SUM(S(1:I))

! examples derived from Thinking Machines CM Fortran Reference Manual

! zeros the upper right triangle of C
  FORALL (I=1:M, J=1:N, I<J) C(I,J) = 0

! assigns each array element its index along the 2nd axis
  FORALL (I=1:N) G(:, I, :) = I

! assigns consecutive integers to all elements of array A
  FORALL (I=1:M, J=1:N) A(I,J) = (I-1)*N + J - 1

! 2 ways to replicate a vector along the 2nd dimension of A
  FORALL (J=1:N) A(:,J) = R
  ! which is equivalent to the implied spread
  A = SPREAD(R, 2, N)

! assign diagonal of A to R
  FORALL (I=1:M) R(I) = A(I,I)

! rotate square matrix A counter-clockwise
  FORALL (I=1:N, J=1:N) A(I,J) = A(J,N-I+1)

! 2 ways to transpose an array
  FORALL (I=1:N, J=1:N) A(I,J) = A(J,I)
  A = TRANSPOSE(A)

!  other examples

  FORALL (I=1:M, K=1:N) A(I,K) = SUM(A(I,:) * B(:,K))
  ! which is equivalent to
  A = MATMUL(A,B)

  FORALL (I=1:L) R(I) = SUM(S(:),MASK=V(:)==I)

END PROGRAM FORALL_EXAMPLES