Subject: comments on FORALL draft

From: John Merlin <[email-masked]>
Date: Thu, 15 Oct 92 20:04:39 BST

I have some comments and corrections on sections 2 & 3 of the latest 
draft of the HPF FORALL chapter.  (I don't have any on the 'Pure 
procedures' section, of course, which is already perfect! :-)).  
Here goes...

-----------------------
>                                                                        \BNF
> forall-assignment    \IS array-element = expr
>                      \OR array-element => target
>                      \OR array-section = expr
>                                                                        \FNB

Rather than introduce the new grammar symbol 'forall-assignment'
(which should be 'forall-assignment-stmt' anyway) I wonder if it 
wouldn't be better just to use the existing F90 grammar symbols 
'assignment-stmt' and 'pointer-assignment-stmt', along with constraints 
that the 'variable' or 'pointer-object' must be subscripted, etc. etc.  
That's the way that F90 handles the assignments in a 'where-stmt' and 
'where-construct'.

There are problems with these rules as presented.  Firstly, they
disallow a 'forall-assignment' like:

	A(I) % B = ...

which I presume you want to allow (note that the variable here belongs
to the syntactic class 'structure-component', not 'array-element'
--see pp 62-64 of the standard).
Also,	

>                      \OR array-element => target

is illegal F90 (the lhs must be a pointer, but p62 of the std says: 
"an array element...never has the POINTER attribute").  Probably what 
you want is:

		structure-component => target

with the constraints that 'structure-component' must be subscripted,
blah, blah, which will permit the example given later:

> ! Set up a butterfly pattern
> FORALL (J=1:N)  A(J)%P => B(1+IEOR(J-1,2**K))

(Actually, I'm not convinced that pointer assignment should be here at 
all, since it has such limited use and probably very limited scope for
concurrency).

BTW, if you drop 'forall-assignment' in favour of 'assignment-stmt'
and 'pointer-assignment-stmt', you can remove all these constraints:

> \noindent
> Constraint: In the cases of simple assignment, the {\it array-element} and 
> {\it expr} have the same constraints as the {\it variable} and {\it expr} 
> in an {\it assignment-stmt}.
> 
> \noindent
> Constraint: In the case of pointer assignment, the {\it array-element} 
> and {\it target} have the same constraints as the {\it pointer-object} 
> and {\it target}, respectively, in a {\it pointer-assignment-stmt}.
> 
> \noindent
> Constraint: In the cases of array section assignment, the {\it 
> array-section} and 
> {\it expr} have the same constraints as the {\it variable} and {\it expr} 
> in an {\it assignment-stmt}.

---------------------

> For each subscript name in the {\it forall-assignment}, the set of
> permitted values is determined on entry to the statement and is
> \[  m1 + (k-1) * m3, where~k = 1, 2, ..., \lfloor \frac{m2 - m1 +
> 1}{m3} \rfloor  \]
> and where {\it m1}, {\it m2}, and {\it m3} are the values of the first
> subscript, the second subscript, and the stride respectively in the
> {\it forall-triplet-spec}.  If {\it stride} is missing, it is as if it
> were present with a value of the integer 1.  The expression {\it
> stride} must not have the value 0.  If for some subscript name 
> \(\lfloor (m2 -m1 + 1) / m3 \rfloor \leq 0\), the {\it
> forall-assignment} is not executed.

I believe the expression should be:

	\lfloor (m2 -m1 + m3) / m3 \rfloor
not
	\lfloor (m2 -m1 + 1) / m3 \rfloor

---------------------

> A ``pure'' function is defined in Section~\ref{forall-pure}; the
> intuition is that a pure function cannot have side effects.

I would prefer something like:

"A ``pure'' function is defined in Section.. and is guarnateed not to
have side effects".

(sounds more confident).

---------------------

> Note that if a function called in a FORALL is declared PURE, then it 
> is impossible for that function's evaluation to affect other expressions' 
> evaluations, either for the same combination of 
> {\it subscript-name} values or for a different combination.
> In addition, it is possible that the compiler can perform 
> more extensive optimizations when all functions are declared PURE.

This seems to suggest that it's optional for functions to be PURE
in FORALL.  If the pure proposal is accepted, it's better to say 
something like:

"Since all functions called in FORALL must be pure, ..."

---------------------

> \subsection{Scalarization of the FORALL Statement}
> 
>...

In the scalarisation of the 'forall-stmt', it's claimed that:

> !               ... (it is safe to avoid saving the subscript 
> !expressions because of the conditions on FORALL expressions)

but I thought that the following was allowed:

	FORALL (I=...)  J(J(I)) = ...

If so, then the subscript expressions must be saved.

Also, if all functions in FORALL must be pure then a big simplification 
is possible, since the 'mask', 'rhs' and the subscript expressions can all 
be evaluated concurrently (except that for a given index, 'mask' must 
precede 'rhs' and 'e1,..,em').  This is because all expressions are 
guaranteed side-effect free; the only 'side-effect' of a forall is 
actually performing the assignment.

Therefore I suggest that the scalarisation could be simplified along the 
following lines:

>                                                                    \CODE
> ! In any order, evaluate subscript and stride expressions,
> ! the scalar mask expression, and, for all valid combinations of
> ! subscript names for which the scalar mask expression is true, 
> ! the 'rhs' expression and lhs subscript expressions.
> 
> templ1 = l1
> tempu1 = u1
> temps1 = s1
> templ2 = l2
> tempu2 = u2
> temps2 = s2
>   ...
> templn = ln
> tempun = un
> tempsn = sn
> DO v1=l1,u1,s1
>   DO v2=l2,u2,s2
>     ...
>       DO vn=ln,un,sn
>         tempmask(v1,v2,...,vn) = mask
>         IF (tempmask(v1,v2,...,vn)) THEN
>           temprhs(v1,v2,...,vn) = rhs
>           tempe1(v1,v2,...,vn) = e1
>           tempem(v1,v2,...,vn) = em
>         END IF
>       END DO
> 	  ...
>   END DO
> END DO
> 
> ! Then perform the assignment of these values to the corresponding 
> ! elements of the array being assigned to
> 
> DO v1=templ1,tempu1,temps1
>   DO v2=templ2,tempu2,temps2
>     ...
>       DO vn=templn,tempun,tempsn
>         IF (tempmask(v1,v2,...,vn)) THEN
>           a(tempe1(v1,..,vn), ..,tempem(v1,..,vn)) = temprhs(v1,v2,...,vn)
>         END IF
>       END DO
> 	  ...
>   END DO
> END DO
>                                                                       \EDOC

(In the first set of DO-loops I've used 'l1' rather than 'templ1', etc, 
for the bounds to avoid implying any order between the evaluation
of the subscript and stride expressions and the mask, rhs, etc,
although of course it's inefficient to evaluate 'l1', etc, twice.)

The same simplifications (and necessity of saving array element subscripts)
apply to subsequent sequentialisations.

-----------------------

> \subsection{General Form of the FORALL Construct}

contains the constraint:

> Constraint: If a {\it forall-stmt} or {\it forall-construct} is nested 
> within a {\it forall-construct}, then the inner FORALL may not redefine 
> any {\it subscript-name} used in the outer {\it forall-construct}.
> This rule applies recursively in the event of multiple nesting levels.

If functions in FORALL are pure and side-effect free, then I think
this constraint is redundant; the only 'side-effects' of the inner
FORALL are assignment to array elements, so the 'subscript-name's
cannot be redefined.
(Assuming the 'subscript-name' isn't equivalenced to an array element,
that is - on second thoughts, perhaps it's better to keep this constraint 
to cover this case!)

> For each subscript name in the {\it forall-assignment}s, the set of
> permitted values is determined on entry to the construct and is
> \[  m1 + (k-1) * m3, where~k = 1, 2, ..., \lfloor \frac{m2 - m1 +
> 1)}{m3} \rfloor  \]
> and where {\it m1}, {\it m2}, and {\it m3} are the values of the first
> subscript, the second subscript, and the stride respectively in the
> {\it forall-triplet-spec}.  If {\it stride} is missing, it is as if it
> were present with a value of the integer 1.  The expression {\it
> stride} must not have the value 0.  If for some subscript name 
> \(\lfloor (m2 -m1 + 1) / m3 \rfloor \leq 0\), the {\it
> forall-assignment}s are not  executed.

As before, I think the expression should be ((m2-m1+m3)/m3)

-----------------------

In
> \subsection{Interpretation of the FORALL Construct}

item 3(a):

> \item Assignment statements, pointer assignment statements, and array
> assignment statements (i.e.
> statements in the {\it forall-assignment} category) evaluate the 
> right-hand side {\it expr} and any left-and side subscripts for all 
                                          ^^^
> active {\it subscript-name} values,
> then assign those results to the corresponding left-hand side references.
              ^^^^^^^^^^^^^
              the results of {\it expr\/}

item 3(b):

> \item WHERE statements evaluate their {\it mask-expr} for all active 
                        ^
                        and constructs?

-----------------------

> A single assignment or array assignment statement in a {\it 
> forall-construct} must obey the same restrictions as a {\it 
> forall-assignment} in a simple {\it forall-stmt}.

Perhaps simpler to say:

A {\it forall-assignment} must obey the same restrictions in a 
{\it forall-construct} as in a simple {\it forall-stmt}.

-----------------------
In the example scalarisation:

> FORALL ( v1=l1:u1:s1, mask )
>   WHERE ( mask2(l2:u2) )
>     a(vi,l2:u2) = rhs1
        ^^
        'e1' would be more general (and I presume you meant 'v1').
>   ELSEWHERE
>     a(vi,l2:u2) = rhs2
        ^^
        likewise, 'e2' would be more general.
>   END WHERE
> END FORALL

-----------------------
Other tiny editorial matters:

> A {\it forall-construct} othe form:
                           ^

> where each si is an assignment is equivalent to the following scalar code:
             ^
             {\bf si}, or perhaps $s_{i}$ (and again later).

> \item In general, any expression in a FORALL is evaluated only for valid 
> combinations of all surrounding subscript names for which all the
> scalar mask eressions are true.
               ^