Subject: FORALL

From: [email-masked] (Alok Choudhary)
Date: Sat, 20 Jun 92 18:32:31 EDT

The following are my comments on Marc's proposal and on subsequent
comments by Chuck.

>Issue: This description makes it impossible to create a triangular
>FORALL.  For example, I can easily imagine someone wanting to say

>	FORALL ( I = 1:N, J = 1:I ) A(I,J) = 0.0

>(zero out the lower triangle of an array).  You can get the desired
>effect by using a mask expression, but that's inelegant (and I suspect
>inefficient on most implementations).  Or you can use the INDEPENDENT
>directive in a DO loop.

>Questions: Are triangular loops important enough to include them as
>FORALLs?  Will triangular FORALLs put an undue burden on the compiler
>writers?

The generalization may not stop at trianglular loop. For example, if
you allow one subscript expression to be a function of another, then
it can get very complicated.

 for example,

 What if you have

        FORALL (I = 1:N, J = f1(I):f2(I), K = f3(I,J) ...) A(I,J,K..) = 0.

 Not only can it become complicated, but it also imposes and order on the
evaluation of subscript values. Therefore, I would go along with what
Marc's proposal contains. Triangular loops can be easily done using
a DO INDEPENDENT LOOPS (DO LOOPS impose an ordering on the evaluation
of the loop indices whether or not the iterations are independent).

 Furthermore, in computations like these, the efficiency will depend
more on how data is distributed. Finally, for simple loops like
triangular loop it may not be (I hope) too difficult for a compiler
to recognize and optimize!

>Side issue:
>Is anyone else confused by "subscript" meaning both "FORALL index" and
>"subscript expression"?  Can anyone suggest a beter name?

 For FORALL Index we may use Iteration-set subscript (ISS) and for
"subscript expression" we may use Array Subscript (AS).

		RE: Marc's proposal on Block Forall

> \subsection{Block FORALL}
> 
> \begin{verbatim}
> forall-stmt          is FORALL (forall-triplet-spec-list [ ,scalar-mask-expr ])
>                           forall-block
>                         END FORALL
> 
> forall-triplet-spec  is subscript-name = subscript : subscript [ : stride]
> \end{verbatim}
> 
> \noindent
> Constraint:  {\it subscript-name} must be a {\it scalar-name} of type integer.\\
> 
> \noindent
> Constraint:  A {\it subscript} or a {\it stride} in a {\it
> forall-triplet-spec} must not contain a reference to any {\it
> subscript-name} in the {\it forall-triplet-spec-list}.
> 
> A {\it forall-block} can be an arbitrary sequence of executable constructs,
> treated as a unit (R801).  It can also contain {forall-assignment}'s.
> 
> \begin{verbatim}
> forall-assignment    is array-element = expr
>                      or array-section = expr
> \end{verbatim}
> 

> \noindent
> Constraint:  The {\it array-section} or {\it array-element} in a {\it
> forall-assignment} must reference all of the {\it forall-triplet-spec
> subscript-names}.

 I am not clear about the block statement. My understanding is, as
Chuck also points out, that if a statment is not an assignment,
then the usual definition applies.

 Consider tha following example.

 Let's say A is an array containing 0,1,0,1,0,1 ....(alternating between
0 and 1). What we want to do is to change 0 to 1 and 1 to 0.
(something like making background the foreground and viceversa).

 Is it accomplished by

   FORALL(I=1:N)

    IF(A(I) .EQ. 0)
	THEN A(I)=1
	ELSE A(I)=0
    END IF
   END FORALL

Since, all the iterations are independent, each statement (IF-THEN-ELSE being
one statement) is supposedly extecuted in parallel.

My understanding is that the above statement should do the job.

BUT IS THE FOLLOWING CONSTRAINT IS MARC's PROPOSAL VIOLATED? My interpretation
of the constraint is that one may not use conditionals on the
iteration subscripts themselves, but one may use it index an
array on which conditional is based. NOTE THE DIFFERENCE. "IF (A(I) .EQ.0)"
is a content based conditional and not index value based conditional.

> \noindent
> 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}.
> 

NOTE: A WHERE-ELSEWHERE statment will not do the job because assignment in
the WHERE part can affect the evaluation in ELSEWHERE PART,

 i.e., the following will change the array A to all 0s.

    WHERE (A .EQ. 0)
	A = 1
    ELSEWHERE
	A = 0
Since array contains only 0s and 1s, all 0s will be converted to 1s by
the WHERE Part, making evaluation of ELSEWHERE true for all elements,
making the entire Array 0.

 The above task cannot be accomplished by WHERE statment unless
temporaries are used. This strange meaning of WHERE in F90 is likely
to produce lot of buggy programs.

		CHUCK's COMMENTS

>I think this is opening a very nasty can of worms.

>Worm 1:
>The BNF and text need to be fixed to state that only forall-assignment
>is allowed in a forall-body.  (I assume this is what Marc means - if
>not, then
>	A(I) = B(i+1)
>can be interpreted as either a regular assignment or a
>forall-assignment, which apparently have different meanings (in the
>scalarization, only forall-assignments are transformed).  Or, going
>the other way,
>	X = X + A(I)
>is allowed in a forall-body, since it is syntactically not a
>forall-assignment but otherwise a legal Fortran statement.)  

I agree with Chuck here. Any assignment inside a FORALL should be a FORALL
assignment, meaning that any statment having more than one
reference to the same array location  on the LHS is illegal.

>Worm 3:
>The principle of least astonishment may need invocation here.  One
>interesting consequence of Marc's proposal is that this is legal:
>	FORALL ( I = 1:N )
>	  IF ( N > 1 ) THEN
>	    A(I) = 1.0
>	  END IF
>	END FORALL
>but this is not legal:
>	FORALL ( I = 1:N )
>	  IF ( N > I ) THEN
>	    A(I) = 1.0
>	  END IF
>	END FORALL
>(Look carefully at the IF condition...  Marc does not allow the FORALL
>index to be referenced in any statement except forall-assignments.)
>The intent (I assume) is to force all iterations, and thus all
>processors, down the same path at all branch points, and that sure
>makes FORALL easier to define.  But it will make some useful
>computations difficult to code:
>	Iterating to convergence on each point of a grid
>	Conditional assignment to points on a grid
>	Having different formulas for different grid points
>	Guy Steele's ragged array example (ALLOCATE different-sized blocks)
>	Nested triangular loops or triangular FORALLs
>	Boundary conditions

>(Some of these limitations are solved by the WHERE construct.)

I agree with Chuck, although I do not know how a WHERE construct can
solve the problem, because WHERE does not allow explicit reference to
index values.

>>Worm 4:
>If the statements in the forall-block can be arbitrary, we have to
>define semantics for
>	FORALL ( I = 1:N )
>	    CALL FOO( A )	! How many times is FOO called?
>				! Scalarization says 1, users will say N
>	    OPEN(5,FILE='BAR')	! Parallel I/O, here we come
>	    READ (5) B(1:100)
>	    			! READ (5) B(I) is illegal, though
>	    WRITE (5) C(1:5)
>	    			! WRITE (5) C(I) is illegal
>	    CLOSE (5)
>	END FORALL
>(Interestingly, I don't see any trouble from GOTO or STOP, since all
>iterations must follow the same control flow.)  There may be other
>problematic Fortran statements.

FOO is called N times. 

I do not know why would one put OPEN inside a FORALL, if opening the same
file (but is it an error to try to OPEN a file already opened?? same for CLOSE)

I am not clear why READ above is illegal?

Since inside the FORALL each element of C may be assigned only once
(per statement), The WRITE will not produce an erroneous result, although
it may produce several unnecessary writes.

>Worm 6:
>No other nested construct puts any restrictions on the statements
>within its body, except for DO loops not allowing their index
>variables to be redefined.  I argue that FORALLs (or other new
>constructs) should not restrict their bodies either without good
>reason.

I agree

>Overall, I think the proposal went too far in generalizing the FORALL.
>I'll make the following modest (and informal) counterproposal:
>	Only "generalized assignment statements" (GASes) are allowed
>	in a FORALL body.
>	The following statements are GASes - assignment, WHERE,
>	FORALL.

  I do not see a need for a WHERE inside a Forall if "IF" statement
is allowed

 Anyway, I am not sure if WHERE Construct allows MASKS to be specified
the way they have been used in Marc's proposal. I looked up
the F90 documents, but did not find anything explicitly prohibiting it,
nor did I ever find an example using it also.

 For example, the following illustration used in Marc's proposal
uses MOD(I,2) inside the WHERE Mask Expression. I am not sure
if it is allowed.

PLEASE CHECK.

FORALL(I=1:N)
   WHERE(MOD(I,2)=0)
       A(I) = 0
   ELSEWHERE
       A(I) = A(I-1)
    END WHERE
END FORALL

Alok Choudhary

 Alok Choudhary
 Assistant Professor
 ECE Dept., 121 Link Hall
 Syracuse University
 Syracuse, NY 13244
 (315)-443-4280
 Fax: (315)-443-2583
 [email-masked]

---

From: [email-masked]
Date: Mon, 22 Jun 92 11:05:12 -0500

> Date: Sat, 20 Jun 92 18:32:31 EDT
> From: [email-masked] (Alok Choudhary)
> Subject: FORALL
> 

Liberally edited by me.

> >FORALL.  ...
>  for example,  What if you have

I'm not going to take a strong stand for or against triangular
FORALLs.  I just want to make a couple points:
    1. As far as I can tell, the only way to express them now is with
	nested DO loops and INDEPENDENT directives.
    2. DO INDEPENDENT has a different semantics from FORALL (although
	not from FORALL INDEPENDENT); therefore, we really are losing
	some sort of expressiveness by dropping the triangular FORALL.
    3. My comments were not directed toward efficiency, but rather
	toward expressing certain computations.  If you can't express
	a computation, it doesn't matter how efficient the compiler
	is...

I'm a little confused about Alok's comment re: compilers recognizing
triangular loops.  Sure, that's an easy pattern match.  The hard part,
though, is recognizing a parallel loop of any shape.  That is,
dependence analysis is just as hard whether the loop is triangular or
square (more or less; arguments over how precise triangular Banerjee's
inequalities are can go elsewhere).  Alok, why do you think triangular
loops are easy to optimize, but we still need FORALL for other loops?

> "subscript expression" we may use Array Subscript (AS).

Minor problem - the Fortran 90 standard uses "subscript" all over the
place (and uses it consistently).  I don't like switching terminology
for one chapter of the Fortran 2001 standard.

"FORALL index" sounds like just what we want, though.  I'll check how
this fits with DO loop terminology.

> ...

Marc, please comment on how you intended the constraint to be
interpreted.  Also, a word on why you picked those constraints would
be helpful; I fear Alok and I are thinking about different problems.

Alok -
Consider Marc's scalarization applied to the following content-based
conditional:
	FORALL ( I = 1:N )
	  IF ( A(I) < 0.0 ) THEN
	    A(I) = 0.0
	  ELSE
	    STOP
	  END IF
	END FORALL
Why do you think that content-based conditionals create fewer problems
than index value based conditionals?  I can simulate index-based
conditionals by defining an array TEMP that TEMP(I) = I, then using
TEMP in all conditions.

> >is allowed in a forall-body.
> >...
> 

Also having a scalar on the LHS should be illegal.  In Marc's
proposal, this is a syntax error.

> >...

I thought that WHERE could reference index values - this is stated
right under the BNF for forall-where-construct (section 3.2 of Marc's
proposal).  This seems in conflict with a constraint in section 3.1
("No statement in a forall-block, other than the forall-assignments,
may reference any of the forall-triplet-spec subscript-names"),
though.  Marc, can you debug this definition?

A WHERE that can't reference the index values seems pretty useless to
me - how can you mask an array element if you can't refer to its
subscripts?

> >	    			! WRITE (5) C(I) is illegal

That's my expectation, too, *but not what the scalarization gives*.
Remember, we're commenting on the proposal, not what we wish the
proposal was.  Anybody want to tackle modifying the proposal to give
the "right" semantics to CALL?

> file (but is it an error to try to OPEN a file already opened?? same for CLOSE)

I suspect it would be a bug, too, *but if we allow arbitrary nested
statements we have to define what they mean*.  According to the
scalarization, the OPEN would only be performed once.

> I am not clear why READ above is illegal?

"No statement in a forall-block, other than the forall-assignments,
may reference any of the forall-triplet-spec subscript-names."

> it may produce several unnecessary writes.

The current scalarization produces only one write.  Is this what we want?

>   I do not see a need for a WHERE inside a Forall if "IF" statement

Read my proposal again.  I'm saying IF is not allowed (nor are DO,
WHILE, OPEN, CLOSE, READ, WRITE, ALLOCATE, ...).  Only three types of
statements: assignment, WHERE, FORALL.

> nor did I ever find an example using it also.

My interpretation is that Marc is defining a new form of WHERE, for
use only in FORALLs.  (Marc, please comment.)

It's a subtle point, but the WHERE in Marc's example

> 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.
Scalars are not arrays in Fortran 90 (language purists can compare
this to APL).

We also saw an example of this in the last meeting, when Pres
suggested his X = SUM(A(I)) syntax in FORALL loops; again, the
difference between scalar arguments and array arguments to SUM was
important in defining the semantics.

Questions for the group: Do we wish to extend WHERE (or any other
statement or intrinsic) with a special form for use in the FORALL
statement?  Do we want to extend WHERE (or any other array statement
or intrinsic) to apply to scalars, regardless of whether it's in a
FORALL or not?

Marc's proposal seems like something we want to be able to
do, but I think the principle of minimal changes applies here.

> Alok Choudhary

	Chuck

---

From: Guy Steele <[email-masked]>
Date: Mon, 22 Jun 92 12:12:56 EDT

WHERE (A .EQ. 0)
	   A = 1
       ELSEWHERE
	   A = 0

No, that is not what happens.  While assignments in the WHERE part
indeed can affect the behavior of the ELSEWHERE part, the WHERE mask
is *not* re-evaluated before execution of the ELSEWHERE part; that is,
the condition must be "remembered" in a manner not affected by
execution of the ELSEWHERE part.  Thus, if TEMP is a LOGICAL array
of appropriate size used nowhere else in the program, then

      WHERE (A .EQ. 0)
	A = 1
      ELSEWHERE
	A = 0
      END WHERE

means exactly the same thing as

      TEMP = (A .EQ. 0) 
      WHERE (TEMP)
	A = 1
      END WHERE
      WHERE (.NOT. TEMP)
	A = 0
      END WHERE

This is entirely analogous to the fact that

      IF (A .EQ. 0) THEN
	A = 1
      ELSE
	A = 0
      END 	

means exactly the same thing as

      TEMP = (A .EQ. 0)
      IF (TEMP) THEN
	A = 1
      END IF
      IF (.NOT. TEMP) THEN
	A = 0
      END IF

assuming TEMP is a LOGICAL scalar variable used nowhere else in the program.

--Guy Steele

---

From: [email-masked] (Alok Choudhary)
Date: Mon, 22 Jun 92 13:03:23 EDT

>	a computation, it doesn't matter how efficient the compiler

You can still specify the computation using 

    FORALL(I=1:N, J=1:N, J<=I) A(I,J) = 0.

The difference is that indices are independently specified and condition
is moved to the mask expression of forall. This allows one to
evaluate the mask for each FORALL index independent of the others
without imposing an order on the evaluation.

>loops are easy to optimize, but we still need FORALL for other loops?

 What I meant was is also shoem in the above example. That is,
using the mask expression, one may still be able to recognize
that it is triangular (or any other) loop, if sequentialized. How
hard it is for a general case, I do not know.

>be helpful; I fear Alok and I are thinking about different problems.

My interpretation on the constraint is that one may not use the
FORALL INDEX subscripts inside a FORALL except for using them
as a part of an array being assigned. Since, A(I) is part of
an assignment, I can use A(I) to evaluate the conditional. I guess,
Marc may be able to say if the above example is legal or illegal
according to his proposal.

>than index value based conditionals? That is my interpretation of
what is allowed and what is not allowed.

Chuck,
I am not saying that content-based conditionals create fewer (or
greater for that matter) problems.

> I can simulate index-based

True. your example of simulating index-based using content-based
will do the job of evaluating the conditional.

>me - how can you mask an array element if you can't refer to its

According to F90, a mask's shape in WHERE should conform to the array
assigment inside the WHERE. DOES  a WHERE inside FORALL have a
different definition (meaning)??

>important in defining the semantics.

If it is interpreted as a SCAN OPERATION then of course it is 
incorrect. That is, if SUM(A(I)) is considered as a sum of
all numbers from the lower limit of the FORALL UP to I for all 1<=I<=N.

But we may define the meaning of reduction functions inside
a FORALL if a unique answer is obtained. Need more discussion.

>or intrinsic) to apply to scalars, regardless of whether it's in a

I would go for allowing WHERE inside as long as its meaning remains
the same as that defined in F90. Otherwise, it may create a lot
of confusion.

Alok Choudhary

---

From: [email-masked]
Date: Mon, 22 Jun 92 13:08:10 -0500

> >triangular loops. ...

OK, now I see what you mean.  It appears that any
triangular/trapezoidal/etc loop can be converted into a mask
expression; efficient translation seems possible for at least some
cases.  I withdraw my claim of non-expressibility.  Unless some other
users want to take up the triangular loop fight, Marc's proposal
stands as is on this point.

> according to his proposal.

I'll hold off on discussing this until Marc tells us what he meant.
Whatever the interpretation, some rewording or extra English
explanation is probably needed to remove this sort of confusion.

> greater for that matter) problems.

I guess I'm confused over why you draw the distinction in the first
place, then.  What is the difference used for?

> >though.  Marc, can you debug this definition? ...
> 

Again, I'll wait for Marc's response.

> a FORALL if a unique answer is obtained. Need more discussion.

Avoiding sidetrack discussion: I meant this as an example of what was
being done, not as a proposal for extending/changing FORALL.  I
believe that the straw polls taken at the last meeting strongly advise
us to not consider reductions in FORALL and DO INDEPENDENT.

> the same as that defined in F90. Otherwise, it may create a lot

Well said.  I think that Marc's semantics extend the meaning of WHERE
in an obvious way (to scalar masks and assignments).  The meaning for
cases that were legal in F90 remains the same, and the meaning of the
new cases is closely related to the old and is useful in the FORALL
context (at least --- I haven't thought about WHERE in scalar code).
I propose that we extend WHERE to this new case.

	Chuck