Subject: hpff-distribute: Thoughts on HPF2 and 2000

From: John Merlin <[email-masked]>
Date: Fri, 5 Jan 1996 16:47:34 +0000 (GMT)

---------------------------------------------------------------------------
[email-masked] is a mailing list for discussion of data
distribution in High Performance Fortran.  Instructions for adding or
deleting yourself from this list appear at the bottom of this message.
---------------------------------------------------------------------------

Hi,

I recently learnt of the HPF2.0 and HPF2000 proposals, and
thought I'd present some thoughts on them as input for the 
impending discussions.  

I'll start with the higher denomination standard first.

HPF2000
-------
My first impression was -- Wow!  To define HPF2000 in 1996,
four years early, is certainly a bold and far-sighted move!  
I can see the advantage.  It's nice to get things done ahead 
of schedule  (at least I imagine so -- I don't speak from personal 
experience you understand).

Despite this, I'd like to suggest an alternative idea.  (Sorry to 
be a spoilsport.)   That is, don't present this language as a standard
at all, but instead put everything that isn't in HPF2 in one
or more official HPF technical reports as proposals for the
standard to follow HPF2.  This would be in line with the procedure
that I believe has been adopted for Fortran evolution by the ANSI 
Fortran committee.  Roughly speaking (Jerry will have the full 
picture)  the idea is to use official TRs for features that if 
put into F96 would unduly delay its publication and implementation, 
but which are felt to be too important to forget altogether until 
F2000.  This way vendors have guidelines on useful extensions 
to F96, and they can be officially standardised in F2000 with 
the benefit of experience. 

Similarly for HPF.  Putting the new features in TRs means 
that users and the marketplace can test their usefulness,
efficiency, implementability, technical correctness, etc.  
The HPFF need be less concerned about getting every detail 
perfect, because implementation and use would iron out any
rough edges.  Then, come 2000, they can be incorporated in an
official HPF2000 standard with the benefit of experience, just
as Fortran and C generally standardise existing practice rather 
than defining totally new things.  If any of the proposed features 
aren't implemented by 2000, then clearly they aren't needed or are 
technically flawed, so they shouldn't go in the standard.
To paraphrase a paraphrase of a well-known saying:
"Premature optimisaton is the root of all evil".  As for the
name of this language, I suggest something like Extended
or Extra HPF, or HPF+, etc -- don't put a date on it.

The argument against this approach is that it's nice to put
everything in a standard so that users can rely on them being 
universally available.  However, the name HPF2000 is an open 
admission that this won't be the case for another four years.  
Given that, the TR approach seems sensible.

HPF2.0
------
I can understand the desire to make the next full HPF standard
some sort of subset of HPF1.1, so that users have something they
can rely on being implemented and universally available.  

However, I was alarmed by the suggestion that the offical 'Subset 
HPF' would somehow cease to exist.  I don't know how you can 
undefine a published standard, even an unofficial one, and it's 
unfair on users and implementors alike, and damages credibility, 
to shift the goalposts like this.  My chagrin was heightened by 
the fact that we've recently announced a public domain implementation 
of Subset HPF (see the advert at the end of this message!), and
were proud of the fact that we've implemented the data mapping
features in virtually their full generality.  I didn't expect 
all the interesting bits to be eliminated from the next HPF 
standard, given that this is the core and most important part of HPF.

Given that HPF2 will effectively be the real standard for 
some years to come, so realistically users will have to restrict
themselves to what's in it, I believe it shouldn't be too spartan 
and should include at least all of the alignment and distribution 
features in Subset HPF.  This also reasonable given that
Subset HPF is what most users and implementors have been
targetting so far.  I'll now try to give an even more cogent 
argument for this.

Firstly, I don't think the proposed criterion for including
features in HPF2 (that they "give high performance on all
platforms") is a good one.  It seems like a cop out by vendors.
A better criterion is to include the minimal set of features 
necessary to allow programs to execute with the highest 
(reasonably achievable) performance.  E.g., although CYCLIC (N) 
distributions may be slower than BLOCK in a direct comparison, 
there will be applications for which the use of CYCLIC (N) will 
give better performance than being forced to use a simple BLOCK 
distribution.  The HPF philosophy is that the user has to 
experiment to get optimum efficiency;  I doubt if the user will
use relatively inefficient features like strided alignment 
unecessarily, so I don't see why we should protect him/her from it.

On the basis of this argument, and the fact that these features 
have already been widely implemented so obviously aren't too hard 
to provide, I'd like to argue for the re-introduction of
general alignments and distributions.  Some justifications:

-- Alignment offsets and strides are needed to describe the
distribution of an array section when it is passed as an actual 
argument into a procedure.  In this way no data movement is
required, and the mapping is still explicitly specified inside
the procedure.  Without this facility the argument would
either have to be remapped on entry and exit, so that it has a simple
mapping that can be described without alignment, or the mapping
would have to be inherited (which is probably also disallowed,
and is certainly less efficient than explicitly specifying the
mapping).  I gave an example of this for Gauss elimination in a 
Sci. Prog.  paper about HPF a while back.

-- Alignment axis permutation is needed to efficiently implement
references like:
   FORALL (i=...,j=...) a (i,j) = b (j,i)

Anyway, I don't understand what complication or inefficieny this
facility could introduce.  Can someone explain?

-- Embedded alignment, e.g.:
     ALIGN s WITH a(m,n)
is needed to allow fine-scale control of where data is stored
and thus where computations are performed, and can avoid
unecessary communications.  For example, in Gaussian elimination 
with pivotting, intermediate values of the pivot element and value 
can be stored and computed just on the processor owning 
the column in question, and the final values can then be
broadcast by assigning them to globally replicated scalars. 
If one could not embed the variables holdinh the intermediate 
values on a particular processor, they would be globally broadcast 
at each step of the pivot search, with massive overhead.  Using
an 'ON HOME' directive doesn't solve this problem;  though the 
computation can be localised, the intermediate results are still 
broadcast if assigned to a globally replicated variable, as they 
must be to preserve HPF semantics.  (I got this example from a 
paper I reviewed, which found that the embedding solution gave 
immensely better performance.)

-- '*'s in the alignment are needed to specify partial replication, 
e.g. replicating a vector over dimension 1 of a 2d processor array 
and distributing it over dim 2.  Surely there is no debate over
the usefulness of this.
 
Thus, I argue for keeping Subset HPF's general alignment and
distribution features in HPF2. 
 
I have just two other comments on features for inclusion in
HPF2:

-- Why is it necessary for HPF2's base language to be full F90
(or F96), rather than the F90 subset selected for Subset HPF?  
True, I expect most large vendors will wish to provide full F96 
along with HPF, but they could do this anyway
even if HPF2 only required Subset F90.  (Perhaps they could
distinguish that their HPF implementation supports full F96 by
calling it HPF96 rather than just HPF2, for instance).

The problem I percieve with requiring full F96 as a basis
is that it tends to exclude small-scale research and academic 
efforts, which may well provide public domain implementations 
(e.g. shpf and ADAPTOR), from being legitamately calling
themselves HPF.  I think public domain implementations can 
greatly help to prime the market for HPF, by providing free
development and testing systems to get people interested, and
for education purposes, etc.  Thus I think the HPFF should
support and facilitate such efforts rather than putting big
hurdles in the way.

Also, some vendors may wish to expend more effort on the HPF
features important for performance (like general data mapping
support!) rather than nice but relatively unimportant F90
features.  Finally, F96 does introduce some extra complications
for HPF, like pointers, arrays-of-arrays, etc.  I'm not
convinced these have been well sorted-out, nor do I think they
are trivial.

-- I agree with the removal of sequence and storage association, 
and the SEQUENCE directive.  This is one area where Subset HPF 
provided features that were guaranteed to give low performance, 
and were extremely hard to implement in full generality.

Also, of course, I support the introduction of PURE procedures
to HPF2!

-- Finally, since we seem to be in the business of tweaking and
correcting the last HPF standard, I'd like to plead again
for common blocks to be disallowed inside pure procedures.
(Please, don't sigh so loud Chuck! :-)).  In fact they only
cause problems if they contain distributed data (much like
sequence and storage association), so could be allowed
otherwise, but for regularity it's probably prefereble to
disallow them altogether, in HPF2 at least.

Without common blocks, pure procedures are trivial to implement,
and very useful for getting high efficiency in many
circumstances as they permit functiional parallelism in FORALLs
(or indeed in array syntax, using F96 ELEMENTAL procedures).
However, by allowing them to access external data that may be
stored on a different processor to that executing the pure
procedure, they violate one of the rules of Kernel HPF, namely,
that features should "allow high performance across all platforms",
because they become extremely hard (or perhaps virtually
impossible) to implement on distributed memory architectures,
which is still an important architecural class for HPF
(e.g. workstation networks).  Has anybody actually implemented
pure procedures in their full generality, with global data
accesses allowed, on any DM platforms yet?

Furthermore, I notice that the desire for 'purer than pure' 
procedures has been voiced in several contexts at recent HPF 
meetings.  Perhaps this is the time to bite the bullet and add 
this constraint.

That's all for now, you'll be pleased to know.

Wishing you all a Happy and High Performance New Year,
                               John.

P.S.  And now for that advert I promised.  'shpf', a Subset
High Performance Fortran compilation system, is now freely
available by anonymous ftp from:

   ftp.hpcc.soton.ac.uk  in directory  /pub/packages/shpf.

It supports arbitrary alignments and distributions, in any
number of dimensions, in virtually any context (for what
it's worth!).  Full information is (or shortly will be)
available on the WWW at URL:
   http://www.hpcc.ecs.soton.ac.uk/shpf/shpf.html.

Please spread the good news to your friends and colleagues, 
and enjoy it!
-----------------------------------------------------------
John Merlin,                                 [email-masked]
Dept of Electronics and Computer Science,    tel:  +44 1703 593943
University of Southampton,                   fax:  +44 1703 593045
Southampton, SO17 1BJ, U.K.
---------------------------------------------------------------------------
To (un)subscribe to this list, send mail to
[email-masked].
Leave the subject line blank, and in the body put the line
(un)subscribe <email-address>
---------------------------------------------------------------------------

---

From: John Merlin <[email-masked]>
Date: Mon, 8 Jan 1996 12:41:20 +0000 (GMT)

I just noticed a terrible mistake in my my last message...

> "Premature optimisaton is the root of all evil".  As for the
             ^^^^^^^^^^^
I meant 'standardisation' of course.  Sorry for any confusion.

                John.