From: Guy Steele <[email-masked]>
Date: Wed, 20 May 92 18:03:57 EDT

Proposal for HPF combining-send intrinsics

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

[Note the addition of COPY_SEND, by analogy with COPY_PREFIX and
COPY_SUFFIX, to achieve what the Connection Machine calls
send_with_overwrite.]

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.
So if multiple elements of SOURCE are sent to the same destination
element, they will all be properly combined with the destination element.
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.)

In addition, the intrinsic COPY_SEND has the behavior that
for every element s in SOURCE, the corresponding elements ij of IDXj
are used to carry out the 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.
So if multiple elements of SOURCE are sent to the same destination
element, some one of them will be assigned and the rest effectively
discarded.

Example:  The C* operation

        x[v] += a;

where x, v, and a are all parallel arrays, and a and v conform,intrinsics-send-proposal, version 2
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.)