Subject: Your example

From: Richard Shapiro <[email-masked]>
Date: Tue, 21 Jul 92 11:14:35 EDT

Date: Mon, 20 Jul 92 16:22:58 -0700
   From: Alan Karp <[email-masked]>
   Reply-To: "Alan Karp" <[email-masked]>

   >From [email-masked] Mon Jul 20 15:19:25 1992
   Return-Path: <[email-masked]>
   From: Richard Shapiro <[email-masked]>
   Date: Mon, 20 Jul 92 16:55:58 EDT
   To: [email-masked]
   In-Reply-To: Alan Karp's message of Mon, 20 Jul 92 12:03:50 -0700 <[email-masked]>
   Subject: FORALL example

      I would like to see your example of a FORALL loop that can not be
      expressed with a DO loop plus directives.

   Let me first state that since there is a way to rewrite ANY forall contruct
   (it's NOT a loop!) into a set of DO loops and array sized temporaries, you
   could win this argument "by definition".  Since I assume that's not what
   you mean, let me propose some "rules" I consider reasonable (and we can
   discuss this as well).

	   1) Any rewrite can't introduce a temporary larger than a scalar.

   ----> I disagree. The compiler will generate large temporaries so I
   ----> can, too.

Not necessarily true. The compiler can stripmine out some temporaries I can't.

   This is a clarity/optimization issue. If I have to create a temporary or
   two for each FORALL construct, I might wind up with 30 or 40 temporaries
   cluttering up a FORALL-laden subroutine.

   ----> I agree, but it is a matter of balance. Introducing one or two
   ----> temporaries per loop isn't a problem; introducing 100 is. We
   ----> need to see what real code looks like and if it can be rewritten
   ----> conveniently. 

I showed you an example from real code. I'm an applications developer; not
a compiler writer, and I know what I'd have to do if I didn't have FORALL.

	   2) The directives can't change the semantics of the DO loop.
	      (i.e. the DO loop must have the desired result without the
	      directive present.)

   This is a property we'd like to preserve for directives. 

   ----> This goes without saying unless I am trying to do an
   ----> asynchronous calculation. If I tell the compiler to ignore a
   ----> true dependence, then I clearly don't care if the meaning
   ----> changes. This rule goes under the category of giving enough
   ----> rope. 

	   3) I'm not willing to generate more than one DO loop nest.

   If I'm going to generate a bunch of DO loops, then I might as well stick
   with F77.  

   ----> Why not, unless you need to generate dozens? My point is that it
   ----> is better to stick to F77 then add something dangerous like
   ----> FORALL.

Here is a major point  of disagreement: I don't accept that single stament
FORALL is dangerous. I can see your point about block FORALL, that unless I
see the FORALL part, the statement A(I) = A(I+1) has a different meaning.
However, I don't believe this argument applies to single statement FORALL,
since the FORALL is part of the same statement.

   That said, here is an example:

	   INTEGER,DIMENSION(M,N) :: INDEX1,INDEX2,INDEX3,INDEX4
	   REAL A(M,N)

	   FORALL (I=1:M,J=1:N) A(INDEX3(I,J),INDEX4(I,J)) =
	  & SUM(A,MASK=(I.EQ.INDEX1) .AND. (J.EQ.INDEX2))

   This example may look contrived, but it actually represents something I'd
   like to express in a 3-D finite element code I'm writing.  I want to do the
   equivalent of a histogramming (or SEND_WITH_ADD) operation on the array A.

   ----> I don't get the histogram analogy although I could generate one
   ----> by changing your tests. I do agree that this example is a good
   ----> one. 

   This can be re-written:

	   INTEGER INDEX1(M,N),INDEX2(M,N),INDEX3(M,N),INDEX4(M,N)
	   REAL A(M,N),TEMP(M,N)

	   DO I = 1,M
	     DO J = 1,N
	       TEMP(M,N) = SUM(A,MASK=(I.EQ.INDEX1) .AND. (J.EQ.INDEX2))
	     ENDDO
	   ENDDO
	   DO I = 1,M
	     DO J = 1,N
	       A(INDEX3(I,J),INDEX4(I,J)) = TEMP(I,J)
	     ENDDO
	   ENDDO

   I have to do this several times, and the "A" arrays are all different
   sizes. This means I need to explicitly allocate several TEMPs. If I'm tight on
   memory as it is, these extra temps are going to hurt me.

   ----> Sorry, but I disagree. The compiler will have to generate a temp
   ----> as large as the result, so you might still blow memory.

   Notice that I've taken 1 line of code and expanded it to 10. Notice also
   that I'v now put an order of evaluation on TEMP. I could remove this with a
   directive, but what do I gain?  The advantage of the FORALL construct is
   that it provides a means to specify that there is no order, and the RHS is
   to be fully evaluated for all indices befor I do the assignment.  It is a
   mistake to think of a FORALL as a loop, just because it can be implemented
   that way.  Does this help clarify anything?

   ----> I concede that you need more lines of code without FORALL. In
   ----> fact, I think the example I gave is more onerous to the
   ----> programmer. However, I don't see that you have imposed any
   ----> ordering on the evaluation of TEMP since the compiler is free to
   ----> execute the loop iterations in any order. I would also write a
   ----> slightly different routine.

   ----> INTEGER INDEX1(M,N),INDEX2(M,N),INDEX3(M,N),INDEX4(M,N)
   ----> REAL A(M,N)
   ----> ALLOCATABLE TEMP(:,:)
   ---->
   ----> ALLOCATE (TEMP(M,N))  ! Takes care of different shapes for each temp
   ----> TEMP = A
   ----> DO I = 1,M
   ---->    DO J = 1, N
   ---->       A(INDEX3(I,J),INDEX4(I,J)) =
   ---->*         SUM(TEMP,MASK=(I.EQ.INDEX1).AND.(J.EQ.INDEX2))
   ---->    ENDDO
   ----> ENDDO
   ----> DEALLOCATE (TEMP)     ! See, I only need 1 temp
   ---->
   ----> This code does manually what the compiler would do with FORALL.

Not true. You have only given one possible implementation of this. This
particular exmaple is a scatter-add, and it can be done without creating
any temporaries if one has the appropriate hardware.

   ----> The difference is that I can see that I want the old values of
   ----> A. With FORALL I can interpret your statement as meaning "Use the
   ----> current values of the elements of A, not the value on loop entry".
   ----> 
   ----> What do you say? Should we forward this correspondence to the
   ----> Forum?

Yes, let's forward this conversation to the forum (which I have done).

	   Rich Shapiro