Subject: Re: Forall

From: [email-masked] (Min-You Wu)
Date: Wed, 24 Jun 92 21:59:45 EDT

> 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).

Case study:
(1) Let me use barriers for synchronization, and barriers in THEN and ELSE
branches are 1-1 corresponding:
        THEN                             ELSE
          BARRIER  --------------------    BARRIER
          BARRIER  --------------------    BARRIER
          BARRIER  --------------------    BARRIER

Here is the example:

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

S1 will not start execution before S3.1 completes. 

We don't need to create copies for every object.  A copy is necessary
only for the cases that a statement reads and writes the same array 
at different grid points, like A(I) = A(I-1) + A(I+1).  
(when interpreting the single statement forall, we must create temporary
for this statement, it is the similar case, though not the same.)

(2) Let's take a look at the case B(I) = A(I-1).  Assume the user wants
to use the new value assigned by S1, then:

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

It the user want to use the old value, one more temporary is created:

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

Here I just show the general method.  Of course, the two temporaries
can be optimized by using one temporary.

> 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...)

My votes are A - maybe, B - maybe, C - no. 

> 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
> )

My votes are A, B, C, E, F, G, H, N - yes, D - maybe or no, 
J, K, M - don't know, L - don't know the meaning, parallel I/O?

> 	Chuck

---

From: [email-masked]
Date: Thu, 25 Jun 92 10:18:37 -0500

> Date: Wed, 24 Jun 92 21:59:45 EDT
> From: [email-masked] (Min-You Wu)
> Subject: Re: Forall
> 
> > ...

Let me get this straight.  Are you proposing yet another new
statement/directive?  I'm assuming so.

If BARRIER is supposed to be a directive, then it changes the
semantics of the program.  It's not asserting that no dependence
exists, it is forcing a particular resolution of the dependence.
We've been over this ground before: directives cannot affect the
correctness of a program.

If BARRIER is supposed to be a new statement, then we're adding even
more syntax, and adding really major complexity to the implementation.
We now have to deal with nested IFs (each level of which may need a
barrier structure), BARRIERs outside of FORALL (inside DO INDEPENDENT,
for example), ...  We seem to be complicating our lives a lot, and
it's not clear to me that the gain is worth it.

I'll mention in passing that if we add BARRIER, then users will want
EVENTs and all the other PCF synchronization statements.  Plus, I'm
not convinced that BARRIER here is the same as the "usual" BARRIER
statement - I thought that generally all *processors* had to reach the
*same* barrier, not all *iterations* reaching *different* BARRIERs.

Finally, what is your interpretation of the case study without
BARRIERs?  Non-standard-conforming?  Nondeterminate?  Some specific
combination of BARRIERs?  Even assuming that we accept BARRIER, we
have to know what happens when the programmer forgets to put them in.

> ...

I probably didn't make myself clear.  My semantics would read
something like "The effect of an IF statement nested within a FORALL
would be as if two copies of all data referenced in the IF were copied
before evaluation of the condition, and each branch of the IF would
execute using its own copy."  This is similar to the scalarization of
FORALL itself, which generates half a dozen temporary arrays; a real
implementation will minimize this memory use.

> ...

I agree that BARRIERs allow both of the reasonable deterministic
interpretations of this case.  If we assume that programmers want this
power, Min-You's proposal seems to provide it.  My question is, how
much control do we want to give programers, and how complex are we
willing to make the language to handle that?

>... 

Sentiment seems to be running strongly in favor of A, B, and C; would
someone besides Min-You and myself comment on D?

For case H:
Min-You, where do you envision the synchronization points in this
example:
	FORALL ( K = 2:N )
	  DO J = 1, K
	    A(K) = A(K) + A(J)
	  END DO
	END FORALL
Fortran D semantics would produce A(I) = SUM(A(1:I))
SIMD semantics, masking K iterations that had finished their DO loops,
would give tmp=SUM_PREFIX(A(1:N)); A(I)=SUM(tmp(1:I)), I think
PCF semantics would produce seriously nondeterminate behavior

Note that SIMD and PCF semantics produce different results for
	FORALL ( K = 2:N )
	  DO J = K, 1, -1
	    A(K) = A(K) + A(J)
	  END DO
	END FORALL
(and I'm not talking about roundoff behavior!)

	Chuck