Subject: Re: User-defined elemental procedures

From: John Merlin <[email-masked]>
Date: Tue, 14 Jul 92 18:14:02 BST

Firstly, thanks to everyone who read my lengthy proposal for 
'user-defined elemental procedures', and particularly to Joel 
Williamson, Rex Page and Jim Cownie for their comments.  Here 
I'll dip in with some responses to the discussion I've seen so far.

Joel Williamson <[email-masked] Mon Jun 29 13:53:00 1992> writes:

* > For a function to be valid for use as an elemental function, it must 
* > obey the following constraints:
* > 
* > 	1. Its arguments must have intent '(IN)'.
* > 	2. Local arrays cannot be SAVEd.
* > 	3. It cannot define any global variable.
* > 	4. Its arguments, result and local variables must not be distributed.
* > 	5. It can only reference a global variable if it is *not distributed*.
* > 
* > ('local' and 'global' are used here in the normal programming sense, 
* > rather than referring to distribution!).
* 
* It seems that the above constraints preclude the possibility of
* elemental subroutines unless constraint 1 is relaxed.

Agreed.  Perhaps I should modify this to:

     1. For an elemental function, every argument must have intent '(IN)'.

* > I would propose that only elemental functions (both user-defined and
* > intrinsic) are allowed in FORALL, just as in array expressions.  
* > 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.  
* > (Incidentally, arguments returning a result can have intent '(IN)' or 
* > '(INOUT)' as in F90).                                         ^^
*                                                                OUT? 

Well spotted!  (although requiring the subroutine results to have intent 
'(IN)' would eliminate the undesirable side effects you mention next:-))

* This seems to be the needed relaxation, but allowing modification of
* subroutine arguments probably opens yet another proverbial can of worms,
* since a pathological and insidious programmer can find ways to introduce
* innumerable side effects via this mechanism.  I think we'll be far
* better off restricting ourselves to elemental functions only.

Perhaps you're right.  However, Fortran 90 has a rule that any dummy
argument that is modified may not be accessed via an alias 
(e.g. via another dummy argument, or a common block or module, or
by host association).  Explicit interfaces, which I think should be 
mandatory in this context, actually allow this rule to be partially 
checked (i.e. with respect to dummy argument aliases).  

I believe that this rule prevents any undesirable side effects  (or are 
there other problems that I've missed?).  If so, then one could allow 
elemental subroutines but emphasise that they must adhere to the 
standard rules---taking the view that non standard-conforming programs 
can't be expected to give well-defined results, and that their authors 
deserve what they get.  Perhaps elemental subroutines would be sufficiently 
useful to make this course of action preferable.

Rex Page <[email-masked] Mon Jun 29 16:08:53 1992> writes:

* > I'd like to propose extending the Fortran 90 concept of 'elemental 
* > procedures' for the purpose of HP Fortran -- the extension being to 
* > allow programmers to define such procedures, which in F90 are restricted 
* > to a subset of the intrinsic procedures.  
* 
* True, programmers cannot define elemental procedures in a technical sense,
* but they can get the effect of such procedures by overloading a procedure
* name.  Overloading is resolved by matching the type/kind/rank pattern of
* the actual arguments in an invocation against that of the dummy arguments
* in a procedure definition.  For elemental procedures, rank is the relevant
* issue.  Since rank must be between zero and seven, the programmer can
* overload a procedure name with eight definitions, one for each rank, to
* get the effect of elemental functions.
* 
* HPFF seems reluctant to add syntax to Fortran 90 (fortunately, in my view).
* Adding syntax to make an existing capability less clumsy will, I hope,
* have a low priority in our list of tasks.

I don't think that the equivalence you suggest is correct:  an elemental 
procedure call with array-valued arguments isn't equivalent to an 
array-valued procedure.  Elemental procedures have (or rather can be 
defined to have) restrictions that permit independent and concurrent 
execution over the elements of the arguments, which ordinary procedures 
don't have.  Evidence of this is that you can use the former in a WHERE 
construct, but not the latter.

The additional syntax I'm suggesting is very minor---just the additional
keyword 'ELEMENTAL'.

* Fortran 8x contained, at one time, a facility for user-defined, elemental
* procedures.  If HPF is to have this feature, we should review old drafts
* of Fortran 8x to get the benefit of earlier thinking on the matter.

I agree, and confess that I haven't done so yet!

* > Incidentally, I've chosen not to insist that the dummy arguments and 
* > result are scalar---that's another extension to the F90 definition!  
* 
* The overloading device covers this extension.

See above.

* > For a function to be valid for use as an elemental function, it must 
* > obey the following constraints:
* >	1. Its arguments must have intent '(IN)'.
* >	2. Local arrays cannot be SAVEd.
* >	3. It cannot define any global variable.
* >	4. Its arguments, result and local variables must not be distributed.
* >	5. It can only reference a global variable if it is *not distributed*.
* 
* I like constraints 1-3 (plus the prohibition of i/o, which John mentions
* later is his proposal).  I don't see the need for contraint 4.  (Does "local
* variable" mean dummy argument?)  Elemental functions operate locally on
* arrays.  The result has the same shape as the arguments.  As long as the
* argument and result arrays all have the same distribution, this seems a
* perfect opportunity for parallel computation on distributed arrays.

Firstly, I agree that I should add the prohibition of I/O to this list of
constraints.  (I had it in my first draft but deleted it, for reasons
of cowardice really---I didn't want to turn the reader off by giving
too many constraints!  My thinking was that allowing I/O would permit
the old-fashioned technique for debugging, but supporting it would really 
complicate the implementation, and I don't think it's worth it!)

My apologies about rule 4 -- I should have written it more clearly
as follows:

	4. Within the procedure body, its dummy arguments, result and 
local variables must not be distributed.

That is, I mean that nothing that is referenced *within the procedure body*
may be distributed---all accessed data must be available locally without 
communication.  This is to avoid race conditions and the need to implement 
virtual shared memory for distributed memory platforms (but see later for 
a partial withdrawal from this stance).

Of course, on the *caller's* side these procedures may be invoked with 
distributed actual arguments---indeed this is a perfect opportunity for 
parallel computation as you say, and even for MIMD computation.  
In fact, I see no need for the actual arguments and result to have the 
*same* distribution---the implementation should be such that the caller 
automatically redistributes the actual arguments into temporary arrays 
if necessary, and passes in these temporaries, so that at the point of 
call corresponding elements of each argument reside on the same processor.  
Likewise, the dummy result can be re-distributed if necessary into the 
actual result array or section.  This implementation would require no 
extra mechanisms beyond those already required in HPF for other purposes.

* Constraint 5 applies no more strongly to elemental functions than to ordinary
* ones.  A computation will be more efficient when a function executes on the
* processor whose fastest-access memory contains the data the function refers
* to.  When the data resides elsewhere, the computation takes a performance hit.
* Programmers wishing to avoid this will express themselves in some other way.

I would argue that condition 5 is *required* for elemental procedures
in HPF, otherwise the language can only be implemented on platforms with 
(virtual) shared memory, which I believe is contrary to its main objective.
I'll say more about this later, in reply to Jim Cownie's message on the 
same subject.

It isn't required for 'ordinary' procedures, whose data communications are
handled by the normal mechanisms that must be used to implement HPF.

To summarise, the essential difference between an 'ordinary' array-valued 
function and an 'elemental' one is as follows.  In the HPF program, 
a single textual occurrence of an 'ordinary' array function corresponds 
to a single identical call in all processors, which executes the same 
code in SPMD mode.  Therefore, if a data communication is required, 
both sending and receiving processes are aware of this and can cooperate.  
By contrast, an elemental function is invoked independentally for each 
element of its arguments.  Thus, a single textual occurrence of 
an elemental function in an array expression may be equivalent to several 
calls on each processor (because it stores several elements of the array 
arguments);  the number of calls may depend on the processor 
(because of non-uniform distribution of the selected elements, which 
may come from an array section and may be masked in a WHERE or FORALL); 
and different calls may execute different code  (at least for user-defined 
elemental functions, because of data-dependent branches and loop bounds).

At the considerable risk (or certaintly!) of labouring the point, 
I can show the transformation to sequential Fortran 77 of:

	Y = X + F (X)

in the two cases.  Here, 'X', 'Y' and function 'F()' are array-valued
with dimension 'N'.  If 'F()' is an 'ordinary' array-valued function, 
the transformation is:

	CALL F_SUB (TEMP, X)      ! F_SUB() is a subroutine equivalent to F().
	                          ! TEMP is a temp array of dimension N.
	DO I = LOCAL_LB, LOCAL_UB ! restrict index range to the local segment.
	  Y(I) = X(I) + TEMP(I)
	ENDDO

If 'F()' is elemental, the transformation is:

	DO I = LOCAL_LB, LOCAL_UB
	  Y(I) = X(I) + F (X(I))
	ENDDO

* > These functions can also be used in a FORALL.  Because a 'forall-assignment'
* > may be an 'array-assignment' (in most definitions anyway) the elemental
* > function can have an array result.
* >  ...
* >
* >	REAL  v (3,10,10)
* >	INTERFACE
* >	  ELEMENTAL FUNCTION f (x)
* >	    REAL, DIMENSION(3) :: f, x
* >	  END FUNCTION f
* >	END INTERFACE
* >	...
* >	FORALL (i=1:10, j=1:10)  v(:,i,j) = f (v(:,i,j)) 
* ...
*
* 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.  Why not match the last subscripts?
* The result shape would then be [3,10]?  The decision seems arbitrary; it
* will be easy for programmers to forget which decision the language takes
* -- a likely source of errors.

Here you're making a case against the generalisation of allowing the 
'elements' of elemental procedures to be compound data objects as well as
scalars.  That's certainly a debatable point.  I proposed this 
generalisation because I found it to be very useful for some applications 
that I'm familiar with, one of which I outlined in the proposal.
In full F90 implementations of HPF, the 'elements' of elemental
procedures could be data structures as well as arrays, so these procedures 
could be applied to arrays of structures as well as arrays of arrays.  
I think this flexibility makes these procedures much more powerful and 
widely applicable.  The disadvantage, as you point out, is that it may 
be confusing for programmers.

However, 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.

* > I would propose that only elemental functions (both user-defined and
* > intrinsic) are allowed in FORALL, just as in array expressions.  
* 
* I don't understand what this means.  Array expressions, even in FORALL
* assignment, may refer to non-elemental functions.  John, will you clarify
* this for me?

I don't know what I meant by the clause  '...just as in array expressions'!
I guess it was a mistake and should be deleted!

As for your statement that array expressions in FORALL may refer to
non-elemental functions, I would dispute that---you need the constraints 
I listed to ensure that the function may be evaluated concurrently over 
all elements of the FORALL assignment.

* > 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.  
* 
* Structure-valued functions provide a way to return multiple results, so
* this doesn't seem to be a strong reason for including subroutine calls
* in FORALL.

But it's a nuisance to have to clump together logically distinct
data objects into a single structure simply to achieve this effect.
Also, only one grouping of data objects can be achieved this way statically
---other groupings must be created by assignment to a structure,
which will be expensive in time and storage.  (Also, early HPF 
implementations may not support structures, though that's not a 
strong argument!).

* > In addition, the implementation of an elemental function array in an
* > array expression is likely to be more efficient than that of an 
* > equivalent array function.  One reason is that it requires less temporary
* > storage for the result ... .  Another is that it saves on looping ... .
* > ... the elemental function can be invoked elementally in situ within
* > the expression.
* 
* True, the ELEMENTAL designation provides more specific information to the
* processor.  It raises the level of communication possible in the language.
* This is a good argument for adding syntax.  It sways me, for one, but not
* quite enough to support the idea.
* 
*   -  Rex Page

I'm glad you're partly swayed :-))

James Cownie <[email-masked] Mon Jun 29 17:29:08 1992> writes
(In-Reply-To: "Rex Page"'s message of Mon, 29 Jun 92 09:33:40 -0500):

* > Constraint 5 applies no more strongly to elemental functions than to ordinary
* > ones.  A computation will be more efficient when a function executes on the
* > processor whose fastest-access memory contains the data the function refers
* > to.  When the data resides elsewhere, the computation takes a performance hit.
* > Programmers wishing to avoid this will express themselves in some other way.
* 
* Quite right !
* 
* I think John is trying to achieve two separate effects here (since
* he's away I think I can say this without fear of immediate
* contradiction !)
* 
* 1) To insist that the functions are "mathematical" in that they always
* produce the same results when called with the same arguments, and have
* no side effects. Rules 1,2,3 and "no I/O" are intended to achieve this.
* ...
* 2) To ensure that all data references made by the function can be
* achieved locally. (Rules four and five are trying to achieve this)
* 
* Point 1) is important if we're not throwing away a semantic
* specification of what happens inside the FORALL.
* 
* Point 2) is "solely an implementation issue" :-). John wants it
* because he wants a run-time which doesn't require demand driven
* communication. It is easy to construct elemental functions which
* access non-local data.  (Ignoring John's rules 4 and 5 for now)
* e.g.
* 	REAL ELEMENTAL FUNCTION REMOTE (X)
* 	REAL X
* 	REAL Y(1000)
* 	COMMON /FOO/Y   ! Assuming Y can be distributed, add
* 			! appropriate MODULE if required 
* CHPF$   TEMPLATE T(1000)
* CHPF$   ALIGN Y WITH T
* CHPF$   PROCESSORS P(10)
* CHPF$   DISTRIBUTE T BLOCK ONTO P
* 
*  	REMOTE = Y(INT(ABS(X))
* 
* 	END
* 
* C Some call of this
* 	REAL Z(1000),BAH(1000)	
* 	FORALL(I = 1:1000)
* 	   BAH(I) = REMOTE(Z(I))
* 	ENDFORALL
* 
* This function is definitely elemental, but will also require an
* arbitrary communication pattern (which depends on the values in the
* actuals), when the 1000 instances are called on the 10 processors. In
* particular there is no knowledge local to any particular processor
* that its values of Y will be required by any instance of the
* subroutine. To implement this (in parallel) one needs demand
* driven communication, so either a send receive model with a remote
* store access daemon, or a direct (unsynchronised) remote read, remote
* write model.

Of course you're perfectly right---constraints 4 and 5 are designed to 
avoid data communication within the body of elemental procedures, to
allow them to be implemented on distributed memory message-passing 
architectures without the need for virtual shared memory (which you 
call 'demand driven communication').

I believe it's crucial that HPF *doesn't* require virtual shared memory
for its implementation---indeed, I thought that was a principal objective
of the exercise.  Providing VSM would be very expensive on some
platforms, and if you have it it's not clear that HPF is the appropriate 
programming or execution model: why not use PCF or some BSP-type model?

Therefore, I would say it's more than just an implementation issue; 
rather, it's a question of adhering to (what I believe to be) the 
underlying execution model and purpose of HPF, which is that it's 
implementable on DM message-passing machines, where both sender 
and receiver co-operate in communications, without shared memory
emulation.

* It is actually unclear that there is any easy way of making the
* restrictions John wants visible in hpf, since "every array is create
* with an alignment to some template, and every template is created
* with some distribution onto some arrangement of processors."
* Therefore my example would stand EVEN without any explicit mapping
* statements for the global data.

That's a good point!  According to the current HPF proposal, the 
lack of ALIGN and DISTRIBUTE directives for a data object doesn't 
necessarily mean it's undistributed---it's implementation dependent.  
Perhaps that doesn't matter, provided that the absence of mapping 
directives can be interpreted, on architecutures without shared memory
support, to mean that the data is undistributed (i.e. replicated or 
private).

I must confess that when I wrote this proposal I was only thinking
of distributed memory platforms.  Now you've raised the point, 
it seems unnecessarily restrictive to forbid non-local data accesses
on all platforms---they probably cause no problems on SM machines.  
These considerations suggest that perhaps constraints 4 and 5 should 
be changed to the following:

	4. Within the procedure body, its dummy arguments, result and 
local variables must not be subject to data mapping directives.
                            ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^

	5. It can only reference a global variable if it is not 
subject to data mapping directives.
^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^

(i.e. replacing the word 'distributed' by the underscored words).
That way we avoid restrictions that are inappropriate on some 
architectures, while allowing the implementation to impose them 
when necessary.  Any comments?

(Incidentally, I'm not really happy with the number of different
meanings attached to the absence of mappings directives.  For 
dummy arguments they seem to mean 'inherited mapping' -- except, 
if this proposal is adopted, in the case of elemental procedures;
in other contexts they mean implementation-dependent mapping.)

James Cownie <[email-masked] Tue Jun 30 11:38:27 1992>) writes:

* Content
* =======
* The local arrays for elemental functions should certainly be allocated
* resident, however the problem also arises with the global data (see
* example in previous mail).
* 
* A solution which would meet John's objective (but is not permissible
* under his restrictions) would be to insist that the global data
* accessed by the elemental function was replicated, thus ensuring that
* it is resident on all processors.
* 
* (maybe resident isn't so poor !)
* 
* --Jim
* James Cownie 

Exactly --- 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?

Rex Page <[email-masked] Tue Jun 30 14:06:43 1992> writes
(in reply to Jim Cownie):
* > Content
* > =======
* > ...
* > A solution which would meet John's objective (but is not permissible
* > under his restrictions) would be to insist that the global data
* > accessed by the elemental function was replicated, thus ensuring that
* > it is resident on all processors.
* 
* If the demand-driven-data-access-problem is bad,
* the replicated-data-coherence-problem is worse.
* I hope we don't try to tackle that one this go-round.
* 
* How about requiring that global data accessed by elemental functions
* be constant data (identifiers defined in PARAMETER statements,
* made accessible through MODULE USE)?  That would circumvent the
* coherence problem.
* 
*    - Rex Page

As Jim Cownie subsequently replied, there's no coherence problem for 
read-only accesses; and for updates data coherence has to be ensured anyway.

I think it's probably too restrictive to forbid access to global data.
Certainly accessing constants causes no problems, but that's quite 
different from the global data issue.

                   Best regards,
                        John Merlin.

---

From: [email-masked] (James Cownie)
Date: Thu, 16 Jul 92 11:14:47 BST

> considering).  Why isn't that permissible under my restrictions?

Because I need to use mapping directives on the global data objects to

> subject to data mapping directives.

explicitly forbids me from doing this...

-- Jim
James Cownie 
Meiko Limited
650 Aztec West
Bristol BS12 4SD
England

Phone : +44 454 616171
FAX   : +44 454 618188
E-Mail: [email-masked] or [email-masked]