Subject: Comments on FORALL Tentative Proposal, version of Aug 24

From: [email-masked]
Date: Tue, 25 Aug 1992 11:46:20 -0600

As promised, here are my comments on the current FORALL proposal.

Section 1.2 FORALL Statement

My comments are in the "Consequences" subsections.

Section 1.3 FORALL Construct

My comments are in the "Consequences" subsections.

Section 1.4 INDEPENDENT

My contribution to this section consisted of deleting all references to
INDEPENDENT applied to FORALL (to keep consistent with the HPFF meeting,
where only the DO version was covered).  It was probably a mistake not to
move those to their own section, and I'll do that in the next draft unless
the group working on extending INDEPENDENT makes a proposal in the
meantime.

I agree in principle with Geoffrey Fox that INDEPENDENT is very restrictive
as it is now phrased; there's no way to do reductions, and local variables
are only possible by calling subroutines.  If we define INDEPENDENT in
terms of data dependences, however, I see no way around this.  If anyone
can suggest another definition of INDEPENDENT, it might shed some light.

Section 1.5.1 FORALL with INDEPENDENT Directives

In general, this proposal should either stick to the syntax constraints of
sections 1.2 and 1.3, or explicitly propose changing FORALL to a new
construct.  I am firmly opposed to any statement that has one meaning (and
one set of syntactic constraints) when there is a comment before it, and
another meaning (and constraints) without the comment.  If Min-You wants to
fight for a new FORALL, he's welcome to; I've given up those crusades.

Guy Steele's proposal for FORALL INDEPENDENT is below:
>Let there be a directive
>
>!HPF$INDEPENDENT
>
>that can precede either a DO loop or a FORALL statement.
>It asserts to the compiler that the iterations of the loop
>may be executed independently--that is, in any order, or
>interleaved, or concurrently--without changing the semantics
>of the program.  (The compiler is justified in producing
>a warning if it can prove otherwise.)
>
>!HPF$INDEPENDENT
>      DO I=1,100
>        A(I)=B(P(I))   !I happen to know that P is a permutation
>      END DO
>
>!HPF$INDEPENDENT
>      FORALL (I=1:100) A(I)=A(F(I))
>!I happen to know that F(I) > 100, so synchronization is not
>!needed to delay assignments until every rhs has been computed.
>
>One may apply this directive to a nest of multiple loops
>by listing all the loop variables of the loops in question;
>the loops must be contiguous with the directive and in the
>same order that the variables are listed:
>
>!HPF$INDEPENDENT (I1,I2,I3)
>      DO I1 = ...
>        DO I2 = ...
>          DO I3 = ...
>            DO I4 = ...    !The inner two loops are *not* independent!
>              DO I5 = ...
>                ...
>              END DO
>            END DO
>          END DO
>        END DO
>      END DO
>
>In the case of a FORALL, any of the variables may be mentioned:
>
>!HPF$INDEPENDENT (I1,I3)
>      FORALL(I1=...,I2=...,I3=...) ...
>
>This means that for any given values for I1 and I3,
>all the right-hand sides for all values of I2 must
>be computed before any assignment are done for that
>specific pair of (I1,I3) values; but assignments for
>one pair of (I1,I3) values need not wait for rhs
>evaluation for a different pair of (I1,I3) values.

Thus, Guy's proposal was a pure (presumably unchecked) assertion that no
inter-instantiation (not inter-iteration, this isn't a sequential loop)
race conditions occured.  This is slightly at odds with Min-You's
definition that "There is a synchronization at each of these directives." 
I would favor an assertion in Guy's style, and I think that Min-You's later
descriptions of data independence do this without relying on the
synchronization.

Section 1.5.2 Pointer Assignments

Sounds reasonable to me.  I'll include the appropriate changes in the next
draft unless controversy erupts.

Section 1.5.3 ALLOCATE in FORALL

Semantically, this is probably OK.

Occam's Razor warns us against putting too many new features in.

Are other implementors as happy about implementing parallel allocation as
Guy is?  And would anybody like to comment on how this meshes with
allocating distributed arrays / distributing allocatable arrays?

If no controversy erupts, I'll put this into the next draft too.  I'm
uneasy doing so, however.

Section 1.5.4 Generalized Data References

I'm not sure I understand the example; are + and * applied to TYPE(MONARCH)
supposed to be defined somewhere else?

I'd like to see some more examples of using these before I make a real
comment, if just to get a feel for how useful they are.

This is a direct extension to F90, not a FORALL/INDEPENDENT matter.  My
priorities are to handle the FORALL first (actually, it seems to be going
well), INDEPENDENT and other assertions next, and array syntax (or other
F90) changes last.  Yes, I went ahead and added elemental functions applied
to arrays to the section below.  Those parts are independent of the main
FORALL part, and if push comes to shove I'll drop the array syntax to get
the FORALL part passed.

Section 1.5.5 Elemental Functions

This is a little more general than Fortran 90 elementals were supposed to
be.  In particular these elementals can expand some of their arguments and
not others, for example
        INTERFACE 
          !HPF$ ELEMENTAL 
          REAL FUNCTION FOO( X, Y, Z )
            REAL, INTENT(IN) :: X, Y, Z
          END FUNCTION
        END INTERFACE

        REAL A(100), B(100), C(100)
        REAL P, Q, R

        A(1:N) = FOO( A(1:N), B(1:N), C(1:N) )  ! OK
        P = FOO( P, Q, R )      ! OK
        A(1:N) = FOO( A(1:N), Q, R )    ! OK
        A(1:5) = FOO( A(1:10), B(1:10), C(1:10)      ! ERROR
The intent was to allow the kind of array - scalar matching possible in
array operations like
        A(1:N) = B(1:N) * P
I can't claim that this improved the proposal's readability quotient.  I
stand ready to go back to Fortran 8X elementals if that's the consensus.

Similarly, I think that allowing nonscalar arguments and returns is
valuable for elemental functions called from FORALL, but difficult to
define for array expressions.  I've made the corresponding restrictions,
and am ready to back off to everything scalar if that's what the group
wants.

Note that ELEMENTAL in INTERFACE blocks is an assertion about behavior, not
constraints about what can be in the function.  For example, by my reading 
        ! LOTS OF DECLARATIONS
        FORALL ( I = 1:N ) A(I) = COUNT_ON_ME(I, A(I))
        ...
        REAL FUNCTION COUNT_ON_ME( K, Y )
        INTEGER K
        REAL Y
        COMMON /ME/ ICOUNT
        IF ( Y > 0 ) IOCUNT = ICOUNT+1
        ...
        END
would be OK iff A(I) <= 0 for all I.  Yet another correctness condition
that Fortran can't necessarily check.

Section 1.5.6 A Proposal for MIMD Support in HPF

Generally, I view MIMD support as a problem for HPF round 2.  However, to
prime the pumps for that debate (and maybe bring some of this into HPF 1),
here goes...

When this proposal says "specify parallelism", which of the following does
it mean?
        1. Assert these operations are independent
        2. Command the compiler to run these sections in parallel.
        3. Both of the above.
        4. Something else. (If so, please explain...)
Claim: If the answer is 1., then PARALLEL DO is equivalent to DO with
INDEPENDENT.  I would support assertions of this type.
Claim: If the answer is 2., then lots of work has to be done to make this
work; for example, what does the command mean when all processors are busy?
 I believe this answer will produce the stalemate that PCF did.
I don't know how I would react to answers of 3. or 4.  Probably I would
reject 3 as overspecifying the program (specifying which section of code
should be parallel is surely machine-dependent).

Seeing the full definitions of elemental functions, FORALLs, INDEPENDENT,
BEGIN/END INDEPENDENT, and these PARALLEL constructs, I'm beginning to
think we should make "data independent" a basic term.  At least then we
wouldn't have to keep repeating the definition.  (Whether it is a good idea
to define semantics based on data dependence is a different question.)

The NEW construct: Presuming that we have the rule that directives are
assertions, what does NEW assert?  Does it change the semantics of the
program (i.e. are there programs that will produce incorrect output if NEW
is inserted)?  What is the scope of NEW (one loop?  one procedure?)?

I assume that the intent is that INDEPENDENT (or PARALLEL) assertions would
take NEW into account; that is, dependences related to NEW variables do not
make a loop serial, for example.  I'd be grateful if someone would write up
a precise definiton of "data independent" that took this (and procedure
local variables, and allocated pointers, etc.) into account.

I favor some form of NEW variables, but we have to realize that these will
require some backpatching to definitions we've already made.

                                                Chuck

---

From: [email-masked] (Min-You Wu)
Date: Tue, 25 Aug 92 23:52:27 EDT

> fight for a new FORALL, he's welcome to; I've given up those crusades.

My revised proposal (July 25) is consistent with the syntax of David Loveman 
and Chuck Koelbel's proposal.  Although I believe FORALL should be a new 
parallel construct instead of an extended array assignment, I don't want 
to propose the new FORALL now.  My current proposal for HPF is simply 
extended Guy's INDEPENDENT to a pair of BEGIN INDEPENDENT and END INDEPENDENT.

> descriptions of data independence do this without relying on the

Since the statement before BEGIN INDEPENDENT and the one after END INDEPENDENT
already have synchronization, there is no problem to eliminate the sentence: 
"There is a synchronization at each of these directives." 

Min-You

---

From: [email-masked]
Date: Wed, 26 Aug 1992 11:07:03 -0600

>extended Guy's INDEPENDENT to a pair of BEGIN INDEPENDENT and END INDEPENDENT.

I apparently was working from a stale copy.  I've asked Min-You to send me
a new one.

>"There is a synchronization at each of these directives." 

OK, I think I agree with everything in that proposal now.  Does anybody
else have comments?  (I know somebody was working on an extended
INDEPENDENT proposal...)

                                                Chuck