Subject: hpff-distribute: ASSUME directive proposal

From: Fabien COELHO <[email-masked]>
Date: Mon, 22 Jan 96 22:15:35 +0100

---------------------------------------------------------------------------
[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.
---------------------------------------------------------------------------

Dear Rob,

>  There seems to be no appetite anymore for any ambiguity as to mapping.

This is just the point I want to address in this proposal! great!

> That is why realign and redistribute and maybe inherit are on there way
> out.

I do think that realign and redistribute can be kept and be useful by
disallowing mapping ambiguity. But this is another story.

I would like the following proposal to be discussed by the Forum for
possible addition to HPF-later and/or the kernel. Any comment from the
list is welcome, for sure.

The idea is to allow the user to specify several descriptive mappings for
a given argument to a subroutine. I already sent the suggestion once.
This one version is more formal. Design and implementation issues are
discussed more precisely. It is a possible alternative to some use of the
inherit directive. 

This proposal may replace the inherit directive in the kernel...

I talked with Thomas Brandes (Adaptor) last friday about implementation
issues of such a feature, and he agreed that it is not big a problem.
I guess all implementors would agree on that point. Thus the question is
more about the usefulness of the feature. 

Fabien.
--
Fabien COELHO __ http://www.cri.ensmp.fr/~coelho __ [email-masked]
  CRI, ENSMP, 35, rue Saint Honoré, 77305 Fontainebleau Cedex, France
     phone: 33 1 64 69 {voice: 48 52, fax: 47 09, standard: 47 08}
       ________  All opinions expressed here are mine  ________

%%%%%%%%%%

PROPOSAL: ASSUME (or whatever name you might prefer) directive
--------------------------------------------------------------

The aim of this proposal is NOT to add a new feature or directive to HPF,
but rather to promote good software engineering in HPF and to provide more
knowledge to the compiler about the mapping of data, in order to improve
the performances. This is in the spirit of HPF. 

The proposal does not add any new "semantics" to the language. It is just
designed to help the compiler simply and efficiently.

Outline:
--------

The idea is to allow to specify several descriptive mappings for
arguments at subroutine interfaces. It is an alternative to the inherit
directive as a mean to switch beetween several subroutines, depending on
the mapping of their arguments, to do the same job. It does not prevent
separate compilation. The compiler can take advantage of maximum static
knowledge when compiling the subroutines. The user is not required to
clone its own procedure by hand to specify several mappings for a
subroutine, and or to use the inherit stuff.

Syntax:
-------

assume-directive is 
    ASSUME
    list-of-or-separated-static-mapping-directives
    END ASSUME

list-of-or-separated-static-mapping-directives is
    list-of-static-mapping-directives
    [ OR list-of-or-separated-static-mapping-directives ]

Constraints:
------------

C1: declaration:

The assume-directive may appear within the declarations of the subroutine.
If so, it MUST also appear in the subroutine interface.

Notes:
------

N1: the list of mapping directives might be empty, meaning that non
distributed arrays may be used as arguments.

N2: there may be other mapping directives outside of the ASSUME scope.

Discussion:
-----------

Here are discussed some issues that could be switched to constraints...

D1: same order... ?

If C1, it must be the SAME order in the subroutine interface and
declarations. 

Rationale: this allow a simple naming convention for direct implementation
of the feature to be managed at compile/link-time in a cloning-based
approach. If the order is not a constraint, then a compile/link-time
management should be based on the mapping directives by adding some
computed suffix to the name of the subroutines compiled with the different
assumptions, and all names must be different... Thus requiring D4(a).
This issue is extensivelly discussed hereafter.

D2: several/nested ASSUME directives?

Might be allowed. It would then specify the cross product of mappings as
possible assumptions to be managed by the compiler. On the one hand, this
could shorten the mapping description for some subroutines. On the other
hand, it would allow the user to specify many cases to the compiler
without making him/her feel the cost of these many different assumptions.
Should the user be trusted? I guess so:-)

D3: mapping of local variables?

The mapping of local variables may be linked to the mapping of the
arguments, thus local variables may be specified a mapping within the
ASSUME directive. An align outside the assume scope might not be
necessarily sufficient. There is no significant impact on the
clone-based implementation. If local variables are allowed within the
assume scope in a subroutine, they must not appear in the subroutine
interface... 

D4: distinct descriptive mappings, or not?

(a) The different lists of mapping directives should contain distinct
descriptive mappings about the arguments of the subroutine, so that there
can be no ambiguity about the right "version" of the subroutine to call.

(b) Or no such constraints, and the first convenient version is chosen?

This has some impact on the possible implementations:
It would be desirable to reject the next example because only the
first set of directives would be used (would be the rationale for (a))"

      subroutine sub(A)
      real B ! B is local to sub
chpf$ assume
chpf$ distribute A(block)
chpf$ distribute B(block)
chpf$ or
chpf$ distribute A(block)
chpf$ distribute B(cyclic) ! inconsistent with the previous one...
chpf$ end assume

However (a) would prevent the example in D5 and a default prescriptive
case when non distributed data are also to be considered (see D6).
Thus I would prefer (b), but it requires D1 as a constraint, for simple
naming convention management and compile/link time handling.

D5: prescriptive mappings?

prescriptive mappings for some arguments of the subroutine may be allowed:
For instance: 

      subroutine sub(A(n),B(n))
chpf$ assume
chpf$ distribute A(block)
chpf$ distribute * B(cyclic) ! requires a remapping
chpf$ or
chpf$ distribute * A(cyclic) ! idem
chpf$ distribute B(block)
chpf$ end assume

However you would not like this case to be rejected because the compiler
cannot decide the right version to call if both A and B are block
distributed. The "take the first one" option would make sense here. 
The nature of the ambiguity here is quite similar to the one in D4, but
here it is not as useless...

D6: default?

The last option in the assume, under D4(b), can be used as a default case
with prescriptive arguments:

chpf$ assume
chpf$ or
chpf$ distribute A(cyclic)
chpf$ or 
chpf$ distribute * A(block)
chpf$ end assume

Ths would mean that A may be local or cyclic distributed, otherwise please
block-distribute it for the routine. Note that maybe it would not make
much sense to add a descriptive assumption about A as block-distributed,
because the default case should perform equally well (the remapping should
not be performed at runtime... maybe a simple copy... and the body of the
subroutine would be compiled with equal assumptions? I guess it depends on
the way prescriptive mappings are handled by the compiler).

Advices to users:
-----------------

The directive may be expensive at compile time because it may require 
to compile several times the routine with the different assumptions. 

Advices to implementers:
------------------------

To summarize the main issue in the discussion above: 

(1) the declaration order (in the assume or-list) is important:
    => very simple naming convention for compile/link-time handling,
       based on the occurence number.

(2) the declaration is not important AND distinct descriptive mappings
    => possible naming convention for compile/link-time handling
       a` la C++, but disallow interesting use of the feature (D5/D6)...

(3) the declaration order is not important
    => no simple compile/link-time handling. dynamic switching required:-(

My opinion: best is (1) [D1/D5/D6 and D4(b)]. 

It does not prevent some stupid set of directives to be supplied by the
user. Well, this is the problem of the user, it is not the main issue of a
language to prevent stupid use of features. It allows a direct and simple
compile/link-time implementation, what is highly desirable.

Thus the directive *can* (this is not mandatory) be implemented as follow: 

(1) Rewrite 

      subroutine sub(...)
chpf$ assume
CASE 1
chpf$ or
CASE 2
chpf$ end assume
      ...
      end sub

As (this is a cloning)

      subroutine sub_1(...)
      CASE 1 ...
      subroutine sub_2(...)
      CASE 2 ...

Compile the subroutines. When such a subroutine is called, insert the call
to the right version (which is simply derived under constraint D1: it is
sub_"minimum occurrence number compatible with the arguments").

(2) Other possible implementation, without constraint D1, but requiring
constraint D4(a): the routine is rewritten as

       subroutine sub_"name_from_case(CASE X)"(...)
       CASE X...

name_from_case should depend only on the descriptive mapping of
arguments. This is how (C++) templates can be compiled in C++, as far as I
remmeber. 

(3) Other possible implementation, without D1 and D4(a), the switching must be
performed at runtime, between the cloned versions, thus:

       subroutine sub
       if CASE X call sub_x ...
       else if CASE Y call sub_y ...

Example:
--------

The computation and distributions in this example do not make much sense.
Note the align directive outside the assume/end assume. 

      sub callee(a, c)
      parameter(n=100)
      real a(n,n), c ! arguments
      real b(n,n) ! local array
chpf$ align b with a
chpf$ assume 
chpf$ distribute a(block,*)      
chpf$ or
chpf$ distribute a(block,block)
chpf$ end assume 
chpf$ independent(i,j)
      forall(i=1:n,j=1:n) b(i,j) = c*sqrt(i*i+j*j)
chpf$ independent(i,j)
      forall(i=1:n,j=1:n) a(i,j)=a(i,j)/b(i,j)
      end callee

      sub caller()
      parameter(n=100)
      real x(n,n),y(n,n)
chpf$ distribute x(block,*)
chpf$ distribute y(block,block)
      ...
      call callee(x, 0.1)
      call callee(y, 0.25)
      ...
      end caller
---------------------------------------------------------------------------
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>
---------------------------------------------------------------------------