Subject: Re: Forall

From: [email-masked] (Min-You Wu)
Date: Wed, 24 Jun 92 15:17:06 EDT

> 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

I agree that IF with INDENPENDENT doesn't work for this example because
of interactions between branches.   Let's find out how can we solve
this problem.  It seems Fortran D semantics is a good solution, however,
Fortran D semantics can only be apply to using *old* values.  Of course 
the above example is a good one for Fortran D semantics.  How about the 
following example?

 	FORALL ( I = 1:N )
          DO J = 1,N
   	    IF ( ABS(A(I)) < EPS ) THEN
 	      A(I) = 0.0
 	    ELSE
 	      A(I) = A(I-1) + A(I+1)
 	    END IF
          END DO
 	END FORALL
 
The WHERE semantics, as you indicated, is *counterintuitive* in some
cases.  Lets consider the tightly synchronous semantics.  It is difficult 
to specify the corresponding synchronization point between branches.  
For the above example, we may say the RHS of THEN part can be synchronous
with the RHS of ELSE part, and so the LHS of THEN and ELSE.  However,
in general, it is not easy to do so.  I believe we need to have 
an explicit method to indicate the synchronization points.

Moreover, if we allow IF in Forall and assume we can define a reasonable
semantics for it, then CASE can be treated similarly.

Min-You

---

From: [email-masked]
Date: Wed, 24 Jun 92 15:27:41 -0500

> From: [email-masked] (Min-You Wu)
> Subject: Re: Forall
> 
> > ...
> ...

Leaving nested DO loops out of the discussion for a moment...

I agree that a reasonable semantics for IF is very likely to be
reasonable for CASE.  Let's find one.

Unfortunately, "synchronization points" look like a bad starting point
for defining IF semantics.  As soon as there are two statements in one
branch of the IF, the following conflict pops up:

	Users want synchronization between statements in the same branch
	Users do not want synchronization between the branches

Case study:

	FORALL ( I = 1 : N )
	  IF ( A(I) < EPS ) THEN		! S0
	    A(I) = 0.0				! S1
	    B(I) = 0.0				! S2
	  ELSE
	    A(I) = (A(I-1) + A(I+1)) / 2	! S3
	    B(I) = A(I) * 3			! S4
	  END IF
	END FORALL

As a programmer, I expect S4 to use the value of A(I) that S3
computes.  I do not expect S3 to see the values of A(I-1) and A(I+1)
assigned by S1.  (It's not clear to me what users expect to happen if
S4 is "B(I) = A(I-1)" instead.  But let's handle that after we get
agreement on this case.)

The only interpretation that I can see to get out of this conflict
involves creating copies of any objects referenced in both branches of
the IF, then executing each branch using its own copy.  Some language
has to be added to the effect that the same element cannot be assigned
by both branches of the IF (or a resolution rule for those conflicts)
as well.  I'll write something up formally if there's interest.
This is not Fortran D semantics, because each branch still has SIMD
semantics (it's close, though).

I'm not sure what this says in terms of synchronization points;
probably there's a global synchronization before (and after?)
evaluating the condition, a global synch after the END IF, and
synchronizations around S1, S2, S3, and S4 *of only the iterations
executing that branch*.  To the best of my recollection, we haven't
needed to talk about partial synchronizations before, although they
would certainly be used heavily in the underlying implementation on
MIMD machines.

Straw poll for the group:

1. Should HPF define a scalar WHERE statement (with semantics as in Guy
Steele's proposal) in a FORALL...
	A) If we cannot agree on a semantics for IF?
	B) If we do agree on a semantics for IF that is different
	   from WHERE semantics?
	C) If we agree to use WHERE semantics for IF?

(My votes are A - yes, B - yes, C - no.  I don't think we'll agree to
C, though...)

2. Which of the following statements should be allowed in a block FORALL?
	(Let's assume that assignment makes the cut :-)
	A) single-statement FORALL
	B) block FORALL
	C) array WHERE (i.e. current Fortran 90 WHERE)
	D) scalar WHERE (i.e. Marc's proposal)
	E) IF-THEN-ELSE with FORALL-invariant conditions
	F) IF-THEN-ELSE, conditions can depend on FORALL indices
	G) DO loop with FORALL-invariant bounds
	H) DO loop, bounds can depend on FORALL indices
	J) GOTO
	K) STOP and PAUSE
	L) I/O statements (OPEN, CLOSE, READ, WRITE, ...)
	M) ALLOCATE and DEALLOCATE
	N) CALL

(
My reading of the current proposals is:
	Snir - all of above except F and H
	Page - A for sure; maybe B, C, and D
	Me - A, B, C, D for sure; E and F if we can agree on some meaning
)

	Chuck

---

From: [email-masked] (Joel Williamson)
Date: Wed, 24 Jun 92 15:59:16 CDT

>    	    IF ( ABS(A(I)) < EPS ) THEN

Please explain to me the purpose of the "DO J = 1,N" loop.

Joel

---

From: "Rex Page" <[email-masked]>
Date: Thu, 25 Jun 92 08:26:09 -0500

>	Users do not want synchronization between the branches

Right.  Are we also agreed that the above FORALL containing IF-THEN-ELSE
should have the same meaning the following?
   TEMP = A(1:N)
   FORALL (I=1:N, ABS(TEMP(I))< EPS) A(I)=0.0
   FORALL (I=1:N, ABS(TEMP(I))>=EPS) A(I)=TEMP(I-1)+TEMP(I+1)

I think this would be the most appealing analog to the meaning of
array assignments without IF-THEN-ELSE, such as the following:
   FORALL (I=1:N) A(I) = A(I-1) + A(I+1) ! both forms use current values,
   A(1:N) = A(0:N-1) + A(2:N+1)          ! build an array, then assign

rlp votes:

1. Should HPF define a scalar WHERE statement (with semantics as in Guy
Steele's proposal) in a FORALL...
 no              A) If we cannot agree on a semantics for IF?
 probably no     B) If we do agree on a semantics for IF that is different
	            from WHERE semantics?
 no              C) If we agree to use WHERE semantics for IF?

2. Which of the following statements should be allowed in a block FORALL?
	(Let's assume that assignment makes the cut :-)
 yes    A) single-statement FORALL
 yes	B) block FORALL
 no	C) array WHERE (i.e. current Fortran 90 WHERE)
 no	D) scalar WHERE (i.e. Marc's proposal)
 maybe	E) IF-THEN-ELSE with FORALL-invariant conditions
 maybe	F) IF-THEN-ELSE, conditions can depend on FORALL indices
 maybe	G) DO loop with FORALL-invariant bounds
 maybe	H) DO loop, bounds can depend on FORALL indices
 no	J) GOTO
 no	K) STOP and PAUSE
 maybe	L) I/O statements (OPEN, CLOSE, READ, WRITE, ...)
 maybe	M) ALLOCATE and DEALLOCATE
 maybe	N) CALL

     ("Maybe" goes to yes if adding these facilities makes it possible
      to avoid local subroutines.)

 - Rex Page

---

From: [email-masked] (Joel Williamson)
Date: Thu, 25 Jun 92 10:18:38 CDT

> 	Me - A, B, C, D for sure; E and F if we can agree on some meaning

I believe that FORALL should be constrained to act as just a flexible
extension of triplet notation and nothing more.  Most of the proposed
extensions to this notion seem to be trying to forcefit MIMD semantics
into a SIMD construct.  I strongly believe that a "high performance
Fortran" needs these semantics, but not in FORALL.  Within our current
set of proposals I think that all else should be relegated to
INDEPENDENT DO loops.  Beyond that I personally believe that an
amalgamation of HPF and X3H5 is what the user community will ultimately
demand.  (Just to thoroughly muddy the waters.)

Best regards,

Joel Williamson

---

From: Richard Shapiro <[email-masked]>
Date: Thu, 25 Jun 92 11:53:59 EDT

Best regards,

   Joel Williamson

I agree with the above statement as well.  Given our ambitious schedule, I
don't see us resolving the MIMD issues very well. We should make sure we
have a well-defined escape mechanism, and come back to MIMD in HPF 2.

		Richard Shapiro,
		Thinking Machines Corporation
		([email-masked])

---

From: "Rex Page" <[email-masked]>
Date: Thu, 25 Jun 92 14:52:28 -0500

rlp votes:

 - Rex Page