Subject: combining-send intrinsics

From: Guy Steele <[email-masked]>
Date: Wed, 6 May 92 18:02:56 EDT

Proposal for HPF combining-send intrinsics

Guy L. Steele Jr.
Thinking Machines Corporation
Version of May 6, 1992

For every reduction operation XXX in the language, introduce a new
intrinsic subroutine XXX_SEND:

   XXX_SEND(SOURCE,DEST,IDX1,...)

Arguments IDX1,... are optional.  The number of IDX arguments
must equal the rank of DEST.  The SOURCE and all the IDX arguments
must be conformable.

For every element s in SOURCE, the corresponding elements ij of IDXj
are used to carry out the operation

	DEST(i1,i2,...,in) = XXX_operation(DEST(i1,i2,...,in), s)

and all such operations performed by a single call are done *as if
serially* in *some* (processor-dependent) order for each element s.
Thus the call

      CALL SUM_SEND(SOURCE,DEST,IDX1,IDX2,...,IDXn)

*could* be implemented as

      DO J1=LBOUND(SOURCE,1),UBOUND(SOURCE,1)
        DO J2=LBOUND(SOURCE,2),UBOUND(SOURCE,2)
          ...
            DO Jk=LBOUND(SOURCE,k),UBOUND(SOURCE,k)
              DEST(IDX1(J1,J2,...,Jk),
     &             IDX2(J1,J2,...,Jk),
     &             ...
     &             IDXn(J1,J2,...,Jk)) =
     &        DEST(IDX1(J1,J2,...,Jk),
     &             IDX2(J1,J2,...,Jk),
     &             ...
     &             IDXn(J1,J2,...,Jk)) + SOURCE(J1,J2,...,Jk)
            END DO
          ...
        END DO
      END DO

where k is the rank of SOURCE.  (However, this nest of DO loops
makes a greater commitment to the particular order in which the
combining operations are carried out than the order--namely, none!-
guaranteed by the XXX_SEND intrinsic.  This matters when the
combining operation is not both associative and commutative,
for example floating-point addition.)

Example:  The C* operation

        x[v] += a;

where x, v, and a are all parallel arrays, and a and v conform,
may be rendered

      CALL SUM_SEND(A,X,V)

If all elements of V were distinct, one could write this in
Fortran 90 as

      X(V) = X(V) + A

The proposed intrinsic SUM_SEND "works" even if V contains
duplicate values.  Note that the two-dimensional case

      X(V,W) = X(V,W) + A

must be rendered using SPREAD:

      CALL SUM_SEND(A,X,SPREAD(V,DIM=2,NCOPIES=SIZE(X,2)),
     &                  SPREAD(W,DIM=1,NCOPIES=SIZE(X,1)))

in order to duplicate the cross-product effect of ordinary array
subscripting.  (I chose to propose a definition of XXX_SEND that does
*not* perform such a cross product of indices because it is more
general and in practice more useful without the cross-product effect
built in.)