Subject: Re: User-defined elemental procedures

From: John Merlin <[email-masked]>
Date: Thu, 16 Jul 92 20:36:46 BST

Rex Page <[email-masked] Wed Jul 15 18:12:49 1992> writes:
> 
> In my comments on John's proposal for elemental procedures, I claimed
> that programmers could get the effect of elemental procedures through
> overloading.  I should have said "one of the effects." 
> .....
>
> John pointed out that the version of such a function that operates
> on array arguments (and delivers an array value) will probably be
> viewed by the compiler in the same way as other array-valued functions.
> That is, the compiler probably won't view the invocation as a
> collection of parallel invocations unless it does a tremendous amount
> of inter-procedural analysis.  Yet that view that would be obvious if
> the invocation were elemental.  The point here is that the elemental
> facility allows programmers to add precision to their specifications,
> that is to raise their level of communication.
> 
> I agree that this is a powerful argument, and I was opposed to
> removing elementals from Fortran 90.  Nevertheless they were removed.
> Putting them back in raises the ante for compiler developers, which
> is a trade-off HPFF must consider if it is important for people to be
> able to run their code on both sequential workstations and high
> performance systems.

But FORALL was also removed from F8x and is being considered for HPF.  
On a more general point, I personally don't think that HPF should be 
hamstrung by a requirement not to introduce *any* new facilities to F90 
(this comment is also directed to Jim Cownie about FORALL), provided 
the new syntax is kept to a minimum and the new facilities are clear, 
expressive, clearly useful for our purpose, and implementable across 
the whole range of architectures.  (I have reservations about complex 
MIMD extensions, for these reasons).  

> The last version of Fortran 8x to contain a facility for user-defined
> elemental functions did so by defining elemental invocations.  The
> language included no syntax for designating a function as elemental.
> It required the interface to be visible, making it possible for the
> compiler to recognize an elemental invocation by matching arrays in
> the actual argument list with scalars in corresponding positions of
> the dummy argument list.

Question:  How did F8x propose to check that such procedures are free of 
side-effects  (i.e. local arrays are not SAVEd, no I/O, and no definition 
of global data), which is necessary to make elemental invocations 
deterministic?  

(I assume it didn't check these things.  If not, that's arguably
acceptable in F90, where the consequence of breaking these rules is
simply non-determinism, which can arise anyway from breaking other 
rules that traditionally aren't checked in Fortran.  I believe it's
unacceptable not to check the constraints in the context of HPF,
as there are additional constraints, namely on data distribution, 
which if broken would result in deadlock).

> If we add elementals to HPF using the F8x approach, then we will be
> adding semantics to Fortran 90, but not syntax.  This simplifies the
> plight of someone trying to run an HPF program on a Fortran 90 system.
> People lacking an HPF compiler can link in a collection of overloads
> to simulate HPF elemental functions; they won't need to change any of
> the invoking code.

I'd be glad to avoid new syntax.  I just want some way of annotating
a procedure to assert that it obeys my constraints, so that the 
constraints can be checked.  I'd be happy with an HPF directive like:

	!HPF$ ELEMENTAL proc-name

at the end of the procedure statement or on the next line.  Is that 
an acceptable solution?

> Page:
> *    REAL v(3,10,10)
> *    INTERFACE
> *      ELEMENTAL FUNCTION f(x)
> *        REAL, DIMENSION(3) :: f,x
> *      END FUNCTION f
> *    END INTERFACE
> * ...
> * The question of the shape of the object f(v) needs careful attention.
> * John Merlin's proposal matches the first subscript of the actual and
> * dummy arguments and makes f elemental on the last two subscripts in
> * this invocation, so the shape of the result would be [10,10].
> * 
> * However, other matchings are possible...
>
> ...
>
> Merlin's reply, continued:
>
> > ... if HPF were to adopt this generalisation, there's definitley no 
> > arbitrariness about which indices of an actual argument match those of the 
> > corresponding dummy argument, and which are elemental.  Viewing the actual 
> > argument as an array of compound data objects, its leading indices must be 
> > matched with the dummy argument, as dictated by Fortran's column-major 
> > ordering.
> 
> Fortran 90 defines an array element ordering only so that a whole array
> in an i/o list will imply a particular sequence of i/o elements.  F90
> uses this notion in a storage association sense only where it needs this
> concept for compatibility with Fortran 77.  When one assumes that the
> leading indices are the ones that must match, one elevates the concept
> of array element ordering and drifts back towards the storage association
> regime.  HPF could define a particular matching, such as first indices,
> but should not try to justify the idea through appeals to array element
> ordering.
> 
> I tried to sell the idea of arrays of arrays (without going through
> structures) several times to the Fortran 8x committee, but came up short.
> One of the arguments against it was the arbitrary choice of indices to form
> elements of a lower-rank array from one of higher rank.  The array-of-arrays
> concept would be a major addition to the language.  The issue is whether
> it adds enough expressiveness to make it worthwhile.

Ok, I take your point.  My personal opinion is that, in this context, 
the 'arrays-of-arrays' concept would add considerably to the 
expressiveness of the language, and I don't think that one should be 
forced to use structures for the compound elements just for this purpose 
(i.e. if there's no other reason for using them).  
Also, I note that some other languages have the 'array-of-arrays' concept, 
at least to some extent (e.g. C, Pascal and occam---these being the only 
other langauges I know well!), but I admit that this concept sits
very naturally on these languages because of their row-wise element
ordering, and not-at-all naturally on Fortran with its columnwise ordering.

However, I'm not adamant on this point.  As always, it's a matter to be 
decided by concensus.

> Part of Merlin's clarification:
> > I would dispute [your statement that array expressions in FORALL may
> > refer to non-elemental functions]---you need the constraints 
> > I listed to ensure that the function may be evaluated concurrently over 
> > all elements of the FORALL assignment.
> 
> Fortran 90 (and 77 and 66) includes constraints against side-effects that
> make the value of an expression depend on the order of evaluation of
> subexpressions.  I would like HPF to expand these contraints to permit
> concurrent evaluation of subexpressions.  (I think that John's constraints
> are adequate and that they add to Fortran's existing constraints only the
> requirement that functions within the same statement must avoid sharing
> temporary resources.)  Then forall statements could call non-elemental
> functions with impunity, expanding their usefulness for SPMD programming.
> 
> If we add these constraints under all circumstances, we improve the
> language, but invalidate certain standard-conforming programs.  (I think
> the improvement would be worth the cost in this case, but I don't expect
> to convince many others.)  We will need to add the constraint in the case
> of FORALL regardless of the decision on elemental functions.  Otherwise,
> forall won't be a parallel construct.

Are you proposing that all functions be side-effect free and perform
no communications?  If so it seems a bit harsh.  Sorry if I've misunderstood 
you.

> (Actually, if we define forall to permit parallelism, then we inherit the
> constraints we need from Fortran's prohibition of side-effects in functions
> when they may change the meaning of an assignment statement.)

True, but that leaves the whole responsibility for correctness up
to the programmer, with no guidelines and no possibility of checking
---my preference is to give some rules and be able to check them.
Also, I want to impose more constraints than strictly necessary to satisfy
this criterion, e.g. to prohibit access to distributed data (see earlier).

> Merlin:
> * > Elemental subroutine calls could also be allowed in FORALL, with a very 
> * > similar interpretation to elemental functions.  The main reason for
> * > using them would be to allow the return of multiple results.  
> 
> ... stuff omitted
>
> If a subroutine is returning multiple data objects that are logically
> distinct, then the subroutine is ill-conceived.  If it is worth defining
> a subroutine, it is worth defining a datatype corresponding to the
> result it delivers.
> 
> The Fortran 8x version of elementals permitted elemental subroutines
> only for subroutines used to overload the assignment operation.  I'd
> like to restrict the elemental notion to functions only.  Subroutines
> (unlike functions) are an outmoded concept in Fortran 90.
> Accomplished programmers will not use them -- except to package i/o
> or other side-effects, or possibly for efficiency reasons to cope with
> poor compilers.

Again, I'm not adamant about introducing elemental subroutines to HPF.
Actually, in suggesting them I took my lead from Fortran 90, which
has an intrinsic elemental subroutine 'MVBITS ()' (unless I'm out of
date and it's been dropped!).  Admittedly though, its reason for being 
a subroutine is not that it has multiple outputs, but that it has an 
INOUT argument.  Perhaps that's another justification for elemental 
subroutines in HPF? :-)

Incidentally, if subroutines are an outmoded concept in Fortran 90, 
why does it introduce new intrinsic subroutines (for date, time, 
clock, random numbers, etc)?  Please feel free to ignore this bait,
however, as I don't want to start a debate about subroutines vs.functions! :-)

Jim Cownie <[email-masked] Thu Jul 16 11:29:02 1992> writes:
>
> John Merlin writes:
> > ... I was thinking that the global data accessed by elemental 
> > procedures must be replicated (at least on the architectures I'm 
> > considering).  Why isn't that permissible under my restrictions?
>
> Because I need to use mapping directives on the global data objects to
> ensure that they are replicated. But your restriction number 5 :
>
> > 	5. It can only reference a global variable if it is not 
> > subject to data mapping directives.
> > ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
>
> explicitly forbids me from doing this...

Ok.  We must clarify the significance of omitting data mapping
directives.  I'd like to interpret it (at least on distributed 
memory platforms without demand-driven communications) to mean 
'replication' (or 'private' storage for the dummy arguments and locals
of elemental procedures, which is in some senses equivalent to replication).
That seems logical, by analogy with the way one would typically 
store scalars, which also don't have mapping directives.  
I think I'm allowed to interpret it that way---is that correct?

However, that does conflict to some extent with it's interpretation for 
dummy arguments, where it seems to mean 'inherited' or 'assumed' mapping.
I would support the introduction of a specific notation in the ALIGN 
directive for this case. That would correspond nicely with F90, 
which has a specific notation for assumed *shape* dummy arguments 
(e.g. 'DIMENSION (:,:)').  If and when HPF directives become actual 
Fortran syntax, it would be nice to have some form of 'ALIGN' and 
'DISTRIBUTE' attributes for all data objects that have non-trivial 
mapping, just as F90 requires some form of 'DIMENSION' attribute for 
all non-scalars.

                Cheers,
                     John Merlin.