Subject: Proposed additions to pure proposal!

From: John Merlin <[email-masked]>
Date: Sun, 18 Oct 92 20:49:36 BST

The purpose of the updated 'Pure Procedures' draft distributed by 
Chuck last week was to fix technical bugs in the earlier draft, as
requested by the HPF FORALL group at the last meeting.  Hopefully
it is now technically correct and complete, in that the definition 
given should guarantee side-effect freedom, and takes full account 
of Fortran 90 issues such as pointers, procedure arguments, and 
defined operations and assignments.

However, there are a couple of small additions that I'd like to propose 
for the 'Pure procedures' proposal.  I didn't put them in the latest 
draft as they haven't been discussed yet by the HPF and I didn't want 
to confuse the issue.  Therefore I'll propose and justify them here.  
I'd be grateful if they could be given a 'first reading' at this 
week's meeting and, if passed (provisionally at least) I'll put
them into the 'Pure procedures' document before the next meeting, 
in time for a 'second reading'.

(Note -- the description here is just to convey the general ideas and
isn't carefully worded - it will be carefully considered and
'polished' before insertion into the draft.  I first describe the
two new features, then explain and justify them.)

Proposed additions to 'Pure Procedures' proposal
------------------------------------------------
Addition #1:
------------
Introduce a couple of new directives, for use in the specification-part
of a pure procedure interface and definition:

	!HPF$ READS_GLOBAL
	!HPF$ READS_DISTRIB_GLOBAL

(or something similar!).

Constraint: If a pure procedure references any global data object
(i.e. variable in a common block or module) with explicit, non trivial
distribution, or references a procedure that may do so, then its 
'specification-part' must contain the 'READS_DISTRIB_GLOBAL' directive.

[ N.B. By 'explicit, non trivial distribution' I mean a declared
alignment or distribution which may result in the variable being
distributed over multiple processors.  I'll define this more carefully 
in the final proposal - it obviously depends on the exact form finally 
chosen for the mapping directives!). ]

Constraint: If a pure procedure references global data objects,
none of which has explicit, non trivial distribution, or references
a procedure that may do so, then its 'specification-part' must contain 
a 'READS_GLOBAL' directive.

[ This means it reads global data which is not distributed -- e.g. it
may be replicated, stored in global memory, etc, depending on implementation.
     The clauses about procedure refs mean that, if a pure procedure
calls any procedure whose interface contains a 'READS_DISTRIB_GLOBAL' 
directive, then it must contain one;  otherwise, if it calls any 
procedure whose interface contains a 'READS_GLOBAL' directive, then it 
must contain one.
     Incidentally, as an alternative to having separate directives like
this, I'd be equally happy to have 3 forms of the pure-directive, e.g.:

	pure-directive   \IS  !HPF$ PURE  [procedure-name]
	                 \OR  !HPF$ PURE_GLOBAL  [procedure-name]
	                 \OR  !HPF$ PURE_DISTRIB_GLOBAL  [procedure-name]

to achieve the same effect.  I'm open to suggestions!
     Note that these declarations make no difference to where a
pure procedure may be used - it may still be used in FORALL, elementally,
etc, regardless of whether it accesses global data.  The latter only
concerns implementation and optimisation issues - i.e. they guide the
compiler in the same way as 'SEQUENCE' does.  The implication is
that all side-effect free procedures are pure, but some are purer than
others!]

Addition #2:
------------
Allow some limited forms of data mapping directives for dummy arguments
and local variables within pure procedures (the current draft totally
excludes them).  The exact rules have yet to be decided (based partly on
the outcome of the next meeting) but would be something like:

	A dummy argument may be subject to an  "ALIGN WITH *"  directive;

	A local variable may be subject to an  "ALIGN WITH data-object"
directive, where the 'data-object' is a dummy argument or another local
variable (*not* a template).

Guidance in the use of ALIGN directives for dummy arguments: 
it is recommended that, if a dummy argument may be associated with a
array-valued actual argument that has explicit, non trivial distribution,
then the dummy argument is specified by an  "ALIGN WITH *"  directive.

[This is only a recommendation - correct code will be generated anyway.
However, the generated code may be more efficient if this guideline is
followed.]

Addition 1 - explanation
------------------------
The whole motivation of pure procedures is that they may be invoked
concurrently (e.g. in a FORALL or an elemental reference), each 
invocation operating on a segment of data, with the procedure only 
necessarily being invoked on the processors that own the segment of 
data.  Pure procedures are constrained so that concurrent invocation is 
(i) secure for the programmer and (ii) can be implemented efficiently 
and securely.

The current constraints ensure side-effect freedom, satisfying 
requirement (i).

However, pure procedures can access arbitrarily distributed global
(i.e. common block or module) data.  For such procedures to be
executed concurrently requires global memory (at least for reading), 
either provided by hardware or simulated by software.  
A 'naive' message-passing implementation (i.e. one that has neither 
hardware nor software global memory accesses) would be unable
to support concurrent execution in these circumstances.  Concurrent 
references could still be implemented, but by sequentialisation.

If such a 'naive' HPF implementation does not know whether a procedure 
that is referenced elementally or in FORALL uses arbitrarily distributed 
data, it must make a worst case assumption, and sequentialise the FORALL 
or elemental reference.  Thus, one is lead to the conclusion that all 
elemental references and FORALLs containing function calls must be 
sequentialised.  To avoid this, I would like the procedure interface 
to contain a "!HPF$ READS_DISTRIB_GLOBAL" directive to flag this case 
-- if the directive isn't present, the procedure can be executed 
concurrently.  (This is analogous to the  "SEQUENCE" directive, whose 
presence restricts data distribution).

(Some might argue that the implementation must perform inter-procedural 
analysis to establish whether a procedure reads distributed data.  
However, in my opinion it would be a very bad language design to rely 
on inter-procedural analysis in Fortran.  It may not always be possible, 
and even if it is, it may slow down the compilation severely
- the whole source file must be analysed before any procedure can be
compiled.  Indeed, the whole point of interface blocks in F90 is to 
avoid the necessity for inter-procedural analysis!)

The directive:
	!HPF$ READS_GLOBAL
asserts that a pure procedure accesses common block or module data,
but it isn't explicitly distributed.  (For a 'naive' message-passing
implementation, this would typically mean that it's replicated
and thus available everywhere; systems with hardware or software
global memory support could of course just keep one global copy;
either way, it means that the accessed data is available to all processes
and hence does not inhibit concurrent execution.)  In this case,
concurrent execution is possible, but the global data accesses might
result in dependences which may inhibit certain optimisations.
For example, consider:

	FORALL (I=1:N) A(I) = FUNC ( B(I) )  ! A and B distributed

where FUNC() accesses A though a common block:

	FUNCTION FUNC (X)
	  !HPF$ PURE FUNC
          REAL, INTENT(IN) :: X
	  COMMON /N/ A(N)

	  ... reads elements of A
	END FUNCTION FUNC

The references to A in FUNC() causes a dependence which means that
the rhs of the FORALL must be fully evaluated before any assignment
takes place, i.e. the FORALL must effectively be implemented as:

	FORALL (I=1:N) TEMP(I) = FUNC ( B(I) )
	FORALL (I=1:N) A(I) = TEMP(I)

- the optimisation of assigning the rhs directly to A(I) cannot be
performed.  If FUNC's interface contains neither a "READS_DISTRIB_GLOBAL"
nor a "READS_GLOBAL" directive, this means it doesn't mask any
data dependences, so this optimisation can be performed (subject to
dependence analysis of the FORALL stmt itself).

By the way, I've toyed with ideas for giving more precise information
than these proposed directives provide, e.g. by requiring that pure
procedure interface blocks also specify the global variables or common 
blocks accessed, or by providing information in the directives about 
which global variables are accessed.  I dismissed these as too complicated,
particularly considering the possibility of pure procedure call trees.

Addition 2 - explanation
------------------------
The motivation for this proposal is that a pure function in FORALL 
can have distributed actual arguments, e.g.

	REAL A (N,N)
	!HPF$ DISTRIBUTE A (BLOCK, BLOCK)

	FORALL (I=1:N) ... FUNC (A(I,:), I) ...

Here FUNC operates on rows of A concurrently, perhaps doing a different 
thing to each row, depending on its index I (MIMD parallelism!).  
For each call to FUNC, its first argument is a distributed vector, 
which is ok, since FUNC is invoked in all processes holding segments 
of the vector.

The current proposal disallows any data mapping directives for
dummy arguments and local data.  This is because the dummy arguments
may have a different distribution for each invocation, so their
distribution must be 'assumed' from the actual arguments.
The distribution of the local data must be tied to the processors 
on which the procedure is invoked -- it no good specifying that a 
local variable is owned by processor (1) if the function is only invoked 
on processor (5)!  Thus it is left to the implementation to determine 
a suitable mapping of the local variables, which must be aligned 
somehow with the dummy arguments (rather than just dumped anywhere!).

The problem with this is that when a pure procedure is compiled,
the compiler has no way of knowing whether an array dummy argument is
associated with a distributed or non-distributed actual.  In the former 
case it must generate the most general message-passing code, in the
latter the code can be much more compact and efficient.  An implementation
could choose to do either -- it could always generate the most general 
code, or it could always assume that the actual argument is undistributed, 
in which case it must arrange for the whole of each actual argument to
be present on each process that calls the procedure -- which may 
be inefficient on the caller's side.  If it assumes that the dummies 
can be distributed, then it must choose how to align the local variables
with the dummies, which can require complex analysis (which the HPF
mapping directives are meant to avoid).

Therefore, I'd like a way for the programmer to be able to hint to the
compiler which dummies may be distributed, and how locals are to
be aligned.  The latter is obvious -- locals can be explicitly
aligned to dummies (but not to anything else, e.g. templates, which 
might cause locals to be allocated to processors that aren't involved
in the procedure call).  The former is more difficult -- I suggest that

	ALIGN dummy WITH *

could be used to give this hint (but I'd like to think about it some
more!).  An implementation could assume that dummies with this
declaration may be arbitrarily distributed, and others are 
undistributed.  Of course, no error is caused if the user gives 'wrong'
information, since when a call to the procedure is compiled, the 
implementation knows what assumptions were made (via the interface block)
and so can arrange the distribution or non-distribution of the actuals 
accordingly.

-- John Merlin.