Subject: 2 cents on functions in FORALL

From: David Loveman <[email-masked]>
Date: Tue, 30 Jun 92 10:31:06 PDT

The 3 current FORALL proposals, Guy's, mine, and Marc's, all provide
roughly comparable definitions of single assignment FORALL.  These
definitions all allow functions, including user functions, subject only
to a restriction of the form:

     A function reference appearing in any expression in the 
     forall-assignment must not redefine any subscript name.

and the general Fortran 90 restriction (7.1.7):

     The evaluation of a function reference must neither affect nor be 
     affected by the evaluation of any other entity within the statement.

Thus the issue of functions in FORALL is more one of implementation -
finding cases where a parallel implementation is correct and a scalar
implementation is not required.  The meaning of function references in
FORALL is given in all 3 proposals by "scalarizations" such as the one
following.  I believe it is *very* important to preserve this form of
scalar semantics for FORALL.  It both allows for a straightforward
scalar implementation and answers questions such as "how many times is
the mask evaluated."  

   A forall-stmt of the general form:

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

   is equivalent to the following standard Fortran 90 code:

   !evaluate subscript and stride expressions in any order
   templ1 = l1
   tempu1 = u1
   temps1 = s1
   templ2 = l2
   tempu2 = u2
   temps2 = s2
     ...
   templn = ln
   tempun = un
   tempsn = sn

   !then evaluate the scalar mask expression
   DO v1=templ1,tempu1,temps1
     DO v2=templ2,tempu2,temps2
       ...
         DO vn=templn,tempun,tempsn
           tempmask(v1,v2,...,vn) = mask
         END DO
   	  ...
     END DO
   END DO

   !then evaluate the expr in the forall-assignment 
   !(and lhs subscripts) 
   !for all valid combinations of subscript names 
   !for which the scalar mask expression is true
   DO v1=templ1,tempu1,temps1
     DO v2=templ2,tempu2,temps2
       ...
         DO vn=templn,tempun,tempsn
           IF (tempmask(v1,v2,...,vn)) THEN
             !in any order
             tempe1(v1,v2,...,vn) = e1
               ...
             tempem(v1,v2,...,vn) = em
             temprhs(v1,v2,...,vn) = rhs
           END IF
         END DO
   	  ...
     END DO
   END DO

   !then perform the assignment of these values to 
   !the corresponding elements of the array being assigned to
   DO v1=templ1,tempu1,temps1
     DO v2=templ2,tempu2,temps2
       ...
         DO vn=templn,tempun,tempsn
           IF (tempmask(v1,v2,...,vn)) THEN
             a(tempe1(v1,v2,...,vn),...,tempem(v1,v2,...,vn)) 
                  = temprhs(v1,v2,...,vn)
           END IF
         END DO
	     ...
     END DO
   END DO

It's worth noting(1) that there is a more efficient scalarized definition 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 (2)

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.

(1) Loveman, David.  "Element Array Assignment - the FORALL Statement,"
presented at Third Workshop on Compilers for Parallel Computers,
Vienna, Austria, July 6-9, 1992.

(2) 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.