Subject: Re: Forall

From: [email-masked] (Min-You Wu)
Date: Mon, 22 Jun 92 22:30:34 EDT

> > We can allow FORALL index in the IF statement, as long as the user
> > can ensure there is no dependence between FORALL instances.
> > It there is a dependence, we have to define the semantics first
> > (IF-THEN and ELSE executed in order or simultaneously).
> 
> Which of the following are you advocating?
>     1. IF-THEN-ELSE is allowed in a FORALL, but it is the user's
> 	responsibility to ensure that array elements assigned in the THEN
> 	branch are not referenced in the ELSE branch on another iteration.
>     2. IF-THEN-ELSE is allowed in a FORALL, and assignments made in
> 	the THEN branch are visible in the ELSE branch of another
> 	iteration (i.e. WHERE semantics).
>     3. IF-THEN-ELSE is allowed in a FORALL, and the effect of an
> 	assignment in one branch to an element used in the other
> 	branch on another iteration is undefined (i.e. asynchronous
> 	semantics).
>     4. IF-THEN-ELSE is allowed in a FORALL, and references made in
> 	either branch always refer to array values that were current before
> 	the IF or assigned in the same branch (almost Fortran D
> 	semantics, but not quite).
>     5. Something else.  (If you choose this one, please tell us what
> 	you have in mind! :-)

We can allow IT-THEN-ELSE in a FORALL within a pair of INDEPENDENT 
directives.  The user's responsibility is to ensure that:
1. array elements assigned in the THEN branch are not referenced in 
   the IF condition and the ELSE branch on another instance; and
2. array elements assigned in the ELSE branch are not referenced in 
   the IF condition and the THEN branch on another instance.

Take Alok's example:

   FORALL(I=1:N)
!HPF$INDEPENDENT  
    IF(A(I) .EQ. 0)
	THEN A(I)=1
	ELSE A(I)=0
    END IF
!HPF$ENDINDEPENDENT  
   END FORALL

The user can ensure the above two conditions are satisfied.

So far I believe we don't have a reasonable semantics for IF-THEN-ELSE
with *dependence* between instances.  Semantics 2 and 3 above is not 
reasonable.  Semantics 4 is interesting but may confuse users.  
It worth to put time on defining a reasonable semantics.  

> > > 	FORALL ( I = 1:N )
> > > 	    CALL FOO( A )	! How many times is FOO called?
> > > 				! Scalarization says 1, users will say N
> > > 	END FORALL
> > I agree that in this FORALL, FOO is called N times.  It can be solved
> > by using a different function:
> >        FORALL ( I = 1:N )
> >            CALL foo( a(I) )
> 
> Now I'm confused.  Why should changing the function's argument change
> the number of times it is called?

Sorry I didn't make the argument clear.  What I meant was a call in 
a FORALL should be called N times, so we should make the subroutine call 
with array element as argument instead of the whole array.  (And a 
subroutine with array element as argument is easier to write).

> Let me say that I'm in favor a semantics that would call FOO N times.
> It's not the semantics that Marc defined, however.  We need to
>     1. Allow the CALL to reference FORALL indices. (Otherwise the
> 	subroutine is called with the same arguments every time; not
> 	efficient!)
>     2. Define some restrictions on FOO to either disallow dependences
> 	between iterations, or define the behavior when dependences
> 	occur.
> Part 1 is easy, part 2 is hard.  It's things like this that led me to
> propose the very restricted block FORALL.  Anybody willing to put in
> the time to define these semantics is welcome to, and I'll support
> more general proposals if they look reasonable.

I agree.  For part 2, I believe before we can define the semantics for 
subroutine calls with dependence between instances, the call must be in 
the INDEPENDENT part.

Marc didn't make it clear how we can make a subroutine call.
From his proposal:
>Constraint: No statement in a {\it forall-block}, other than the
>{\it forall-assignment}'s, may reference any of the {\it
>forall-triplet-spec subscript-names}.
I assume he doesn't allow the call to reference FORALL indices.

> > My understanding is, in Marc's proposal, besides of GASes, all other 
> > statements follow the same flow. The good thing is that ARBITRARY sequence 
> > of statements is allowed, but these statements can only follow the same
> > control flow.  Moreover, it is not clear that those statements should be 
> > scalar or not.  For example, the statements
> >        FORALL(I=1:N, J=1:N, I.NE.J)
> >           IF(COND)
> >              THEN A(I,J) = I+J
> >              ELSE A(I,J) = I-J
> >           END IF
> >        END FORALL
> > and 
> >        FORALL(I=1:N)
> >           WHERE(MOD(I,2)=0)
> >               A(I) = 0
> >           ELSEWHERE
> >               A(I) = A(I-1)
> >           END WHERE
> >        END FORALL
> > are scalar, and this statement
> >        FORALL ( I = 1:N )
> >            CALL FOO( A )
> >        END FORALL
> > is not scalar.
> 
> Please define what you mean by "scalar" in this context.  In Fortran
> 90, "scalar" is a noun meaning roughly "a data object that is not an
> array."

Roughly, what I meant is to reference an array element or an array.

> As I argued before, Marc's proposal extends WHERE in a natural way.
> If you're saying that there is a case in Marc's semantics in which a
> vector WHERE statement has a different meaning than in standard
> Fortran 90, then please show us an example.  (That would be grounds
> for modifying the treatment of WHERE or throwing it out entirely,
> depending on how hard it was to fix.)  If you are against extending
> WHERE for some reason, then say that.
> 
> I'm against adding any new statement except for FORALL.  If Marc's
> WHERE is different from Fortran 90 WHERE (except for extending the
> domain), then we should fix or abandon it.
> 
> 	Chuck
> 

In Marc's proposal, the definition of WHERE in FORALL is not consistent 
with that outside of FORALL.  Just as you pointed out before:
>It's a subtle point, but the WHERE in Marc's example
>
>> FORALL(I=1:N)
>>    WHERE(MOD(I,2)=0)
>>        A(I) = 0
>>    ELSEWHERE
>>        A(I) = A(I-1)
>>     END WHERE
>> END FORALL
>
>is not legal Fortran 90.  Quoting section 7.5.3.1 of the standard,
>where WHERE is defined,
>	Constraint: In each assignment-stmt, the mask-expr and the
>	variable being defined must be arrays of the same shape.
>So, the mask-expr (in the example, MOD(I,2)=0) must be an array.
I don't think we need to extend WHERE since we have another way
to do it.  Actually, if we allow IF-THEN-ELSE reference FORALL index, 
we don't need WHERE:
      FORALL(I=1:N)
!HPF$INDEPENDENT  
         IF(MOD(I,2)=0) 
           THEN  A(I) = 0
           ELSE  A(I) = 1
!HPF$ENDINDEPENDENT  
      END FORALL
(I modified the ELSE part to make it no dependence).

However, I don't suggest abandon WHERE completely.  WHERE can be used 
for other purposes.  See the following example:
      INTEGER, ARRAY(N,N) :: A, B

      FORALL(I=1:N)
        WHERE(A(I,:)=B(I,:))
          A(I,:) = 0
        ELSEWHERE
          A(I,:) = B(I,:)
        END WHERE
      END FORALL

Min-You

---

From: Guy Steele <[email-masked]>
Date: Tue, 23 Jun 92 11:56:06 EDT

Date: Mon, 22 Jun 92 22:30:34 EDT
   From: [email-masked] (Min-You Wu)
   ...
   In Marc's proposal, the definition of WHERE in FORALL is not consistent 

... and so we come full circle.  This line of reasoning was exactly
what caused me to propose IF within FORALL several months ago; but
I retracted it after a discussion in the meeting showed that it puzzled
some people.  Not that I object to hauling it out again for another look.

--Guy

---

From: [email-masked]
Date: Wed, 24 Jun 92 11:39:52 -0500

> From: Guy Steele <[email-masked]>
> Date: Tue, 23 Jun 92 11:56:06 EDT
> Subject: Forall
> 

Almost full circle.  You defined a meaning for the original example:

	FORALL ( I = 1:N )
	  IF (MOD(I,2)=0) THEN
	    A(I) = 0
	  ELSE
	    A(I) = A(I-1)
	  END IF
	END FORALL

(the infamous WHERE semantics).  Min-You, on the other hand, makes
this case undefined because of the interaction between the branches.

I don't like the "branches may not affect each other" restriction
because it keeps me from handling inhomogeneous local computations in
the obvious way:

	FORALL ( I = 1:N )
	  IF ( ABS(A(I)) < EPS ) THEN
	    A(I) = 0.0
	  ELSE
	    A(I) = A(I-1) + A(I+1)
	  END IF
	END FORALL

In an ideal world (or in Fortran D FORALLs), this would be legal and
would perform independent computations on all points.  Those semantics
are difficult to explain (everywhere) and implement (on some machines).

The WHERE semantics are at least clear, if counterintuitive in some
cases.  I would rather use them, and call the construct in the FORALL
"WHERE", than do without.  Unfortunately, there is no WHERE-CASE
construct for more complex situations; sigh.  I can't in good
conscience propose adding one.

I am against allowing IF (or any other control-flow construct) if its
interpretation in the FORALL is markedly different from its outside
the FORALL.  Judging from the reaction to Guy's original proposal, I'm
not alone in this.

It would be a shame if we limited block FORALL to only assignment
statements.

	Chuck