Subject: Re: hpff-distribute: distribution ranges

From: <[email-masked]> (Henry Zongaro)
Date: Fri, 8 Mar 1996 15:55:32 -0500 (EST)

---------------------------------------------------------------------------
[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 Fabien,

> I just had a look at the "distribution range" proposal briefly outlined
> in the HPFF meeting minutes. The aim seems to be the same than some
> suggestion I posted, i.e. to tell the compiler about several reaching
> mappings for a subroutine, in place of (?) inherit. I would like to point=
>
> out some defficiencies of this proposal (if I understood it correctly): =
>
>
>  1/ the syntax does not seem to be consistent with any other part of HPF.=
> =2E. =
>
>     RANGE seems to be another word for DISTRIBUTE somehow? =
>
>     Why one more keyword? =
>
>     what if I want to specify some alignments? =
>
>     processor arrangement?
>     why going away from ALIGN and DISTRIBUTE?
>     It does not allow to express the varity of reaching mappings of HPF.

     You are correct that RANGE does not give the compiler hints about all of
the possible mappings that an object can have.  However, the amount of
information it provides for distributions is probably sufficient.  That it does
not give information about possible alignments is a bigger problem.

     I've taken a quick look at your ASSUME proposal, and I believe that RANGE
is more concise when it comes to possible distributions.  For example, if I
want to redistribute an array CYCLIC(n) with some blocking factor that is to be
computed, I could specify this as follows

        program prog
          integer a(100000)
  !hpf$   processors p
  !hpf$   distribute (cyclic) onto p, dynamic :: a
  !hpf$   range a(cyclic())

          ! Compute n
  !hpf$   redistribute a(cyclic(n)) onto p
        end program prog

With ASSUME I have to enumerate the possibilities in order to provide the
compiler with the same information.

        program prog
          integer a(100000)
  !hpf$   processors p
  !hpf$   distribute (cyclic) onto p, dynamic :: a
  !hpf$   assume
  !hpf$     distribute (cyclic(1)) onto p :: a
  !hpf$     OR
  !hpf$     distribute (cyclic(2)) onto p :: a
  !hpf$     OR
            .
            .
            .
  !hpf$     distribute (cyclic(100000)) onto p :: a
  !hpf$   end assume

          ! Compute n
  !hpf$   redistribute a(cyclic(n)) onto p
        end program prog

>  2/ It seems that you cannot specify the relative mapping of data one wit=
> h
>     respect to the other. For instance
>
>     subroutine sub(A,B)
>     real A(:), B(:)
>     real TMP
>     INHERIT A, B
>     RANGE A (BLOCK), (CYCLIC) =
>
>     RANGE B (BLOCK), (CYCLIC)
>     DISTRIBUTE TMP (BLOCK) ??? OR CYCLIC...
>     A=3DB+TMP
>
>     If it happens that A and B are always distributed the same, BLOCK or
>     CYCLIC, you cannot provide this information to the compiler.
>     It seems that you can just specify the mapping on a array per array
>     basis, but the compiler must deal with 4 potential mappings when
>     compiling A=3DB. =

     Good point.

>   3/ It seems that you cannot specify a mapping for local data which woul=
> d
>      depend on the reaching mappings. (TMP example above)

     In many (most?) cases TMP's relationship with A could be expressed with
the ALIGN directive.  This doesn't seem like a big problem to me.

>   4/ you cannot play with several descriptive or prescriptive mappings as=
>
>      a default.

     I'm not sure how the ASSUME proposal handles defaults.  Could you please
elaborate?

>   5/ I cannot see the simple and efficient implemementation. I suspect
>      that the intent is to have some boolean everywhere to guard =
>
>      array references (???) but that does not help much when
>      communication implying two such arrays must be managed; for a
>      cloning based approach the cross product of distributions must
>      be handled what may be both costly and useless (see 2)
>
>
> To summarize my points: in my opinion the suggested approach is
>
>   - ugly (syntax, interaction with DISTRIBUTE...)
>   - not very expressive (ALIGN?, related arrays? default case?)
>   - not straighforward/expensive to implement.
>
>
> Ad: =
>
>
> I outlined an "ASSUME" directive in report A-284 that can be found from m=
> y
> web page, to describe several reaching mappings, which is far from being
> perfect, but which is
>
>   - consistent with ALIGN and DISTRIBUTE that are just reused...
>   - expressive (full HPF mappings, related arrays, default...)
>   - efficiently compilable (compile/link time) with the *current* compile=
> r
>     technology!
>
> End Ad:-)

     I'm not sure how ASSUME is more efficiently compilable than RANGE.  I see
that it is better able to describe alignments and relationships between arrays.
Is that what you're referring to?

     Perhaps some synthesis is possible - something that would describe cover
the best parts of both features.

Thanks,

Henry
---------------------------------------------------------------------------
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: Fabien COELHO <[email-masked]>
Date: Sat, 9 Mar 96 11:48:30 +0100

Dear  Henry,

First the following introduction remark to outline the different approaches
of RANGE and ASSUME: 

 - With RANGE the intent is to help in the compilation of transcriptive
mapping by providing some information (but not as much as could be
described with prescriptive and descriptive mappings), thus it is an
attempt to simplify the troubles in dealing with INHERIT.

 - With ASSUME the approach is just the opposite, extending the use
of prescriptive and descriptive mappings so as to avoid, replace, rule out
INHERIT, thus going upward to more expressiveness with no semantical
extension on the mapping directives and the information provided by them.

> information it provides for distributions is probably sufficient.  That
> it does not give information about possible alignments is a bigger problem.
> 
> want to redistribute an array CYCLIC(n) with some blocking factor that
> is to be computed, I could specify this as follows
> 
>         program prog
>           integer a(100000)
>   !hpf$   processors p

[...]

This exemple does reflect for me neither the intent of the assume proposal I
made, nor my understanding of the range proposal.

The intent of the ASSUME is to provide information about the mapping of
ARGUMENTS passed to a subroutine, that is something which is not available
to the callee in a non interprocedural compiler, while in the example
above it is used to describe some information already available in the
routine, an intra procedural information that a quick data flow analysis
thru the subroutine content should compute easily.

The possible presence of mappings directives dealing with data local to
the subroutine is only significant with respect to different arguments
mappings that may reach the subroutine, that is if you want to relate
the mapping of local data to the mapping of incoming arguments.

The intent of ASSUME as describe is not to tell something about what may
happen IN the subroutine, what I see as obvious for the compiler that can
have a look a the code, but to give information about what is coming from
OUTSIDE. 

When compiling the routine as outlined in your mail with the ASSUME, the
compiler should issue an error because it would result in each case in 2
specification of STATIC mapping directives for the array, after expansion
of the routine for each specification.

// version ..x..
chpf$ distribute A(BLOCK)
chpf$ distribute A(CYCLIC(..x..))
// well, is it BLOCK or CYCLIC? error.

> >   3/ It seems that you cannot specify a mapping for local data which
> >      would depend on the reaching mappings. (TMP example above)
> 

Sure. Just providing orthoganality at not cost in my opinion. Also if you
want to specify NO mapping at all, the align does not make sense.

subroutine sub(A(100))
real TMP(100)
ASSUME
align TMP with A
distribute A(block)
OR
! here A is just *local*, not distributed at all.
! aligning TMP with A which is intended as local does not make sense...
END ASSUME

> >   4/ you cannot play with several descriptive or prescriptive mappings
> >      as a default.
> 

The assume proposal does not put any constraints on the static mapping
directives that may appear in the ASSUME when describing the mapping of
ARGUMENTS passed to the subroutine. Thus it is allowed to mix descriptive
and prescriptive (and why not transcriptive) mappings:

subroutine sub(A(100))
ASSUME
distribute A * (BLOCK)
OR
distribute A * (CYCLIC)
OR
distribute A (BLOCK) // other cases => prescriptive => remapping !
END ASSUME

the compiler is expected to (may) compile 3 versions of the routine, one
for each possible set of mappings... When compiling the callers, and since
the subroutine explicit interface would specify the same information, the
compiler selects the right version (clone) to call, that is the first one
if A is block, the second if cyclic, and the third if otherwise mapped,
what will require a remapping... The last case, if prescriptive (or maybe
transcriptive, but it should be avoided of possible) acts as a default
case.

> I'm not sure how ASSUME is more efficiently compilable than RANGE.

The underlying assumption is that the compiler are ok when compiling
direct descriptive and prescriptibe mappings. Thus the compilation scheme
as suggest is to compile the different versions by using this available
state of the art. I see ASSUME as a way to specify a CLONING of the
procedure to be compiled with different mapping assumptions about
arguments, although it may be possible to do something more intelligent
later on as compiler technology evolves. 

> I see that it is better able to describe alignments and relationships
> between arrays. Is that what you're referring to?

No. I agree that the ASSUME approach is more powerfull (that is as
powerfull as HPF mapping directives to describe array mappings) than the
RANGE approach, but what I really meant here is that the addition of
assume is possible at low cost in the current compilers, without
significant development but:  

1/ some preprocessing to clone the routines by expanding the assume
   (CLONING), each version is then compiled as it is today;

2/ some management of the interface declarations to chose the right
   version at call sites, most often statically, or in very few cases
   at runtime.

And that's all, really!

The way I see the RANGE from the compiler point of view is that it is one
more object that does provide some information, different from what is
already available with standard mapping directives, and that this different
information will have to be managed somehow, differently, to take
advantage of it. Thus I feel it as less powerfull, and requiring more work
to do something out of it.

> the best parts of both features.

Concision is one of the quality of the RANGE proposal, in my opinion. 

For simple cases it can be sufficient to express the mapping of incoming
arguments. We could think of a "simpler" syntax for the assume at the
DISTRIBUTE level, something like

subroutine sub(A(100))
distribute A * {(BLOCK),(CYCLIC)}

that is to reuse the idea of a simple list of distribution, and
as a pratical and concise shorthand for

subroutine sub(A(100))
ASSUME
distribute A * (block)
OR
distribute A * (cyclic)
END ASSUME

but the expressivity is quite limited (for instance, you cannot express
that the array is not mapped at all and is thus local, alignments), so
such a convinient and concise syntax (in the RANGE style) should not
prevent the general and fully expressive and... verbose ASSUME.

I don't feel this verbosity as a big issue: using ASSUME implies more work
from the compiler (that may have to compile each clone), thus it is
important maybe that the user notice with the syntax chosen.

I'm available to add more explanations and examples to help clarify these
issues, and to discuss and analyse new points you may raise.

Regards,

Fabien.

-- 
Fabien COELHO __ http://www.cri.ensmp.fr/~coelho __ [email-masked]
 CRI-ENSMP, 35, rue Saint Honoré, F-77305 Fontainebleau cedex, France
     phone: 33 1 64 69 {voice: 48 52, fax: 47 09, standard: 47 08}
       ________  All opinions expressed here are mine  _________
---------------------------------------------------------------------------
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: Fabien COELHO <[email-masked]>
Date: Tue, 12 Mar 96 15:06:40 +0100

Dear Henry,

I finally understood you point about just specifiying general cyclic
distributions without the actual stride used. I don't think that this issue
should be fixed at the ASSUME or RANGE level, but rather at the DISTRIBUTE
level. Example:

program
  DYNAMIC A
  DISTRIBUTE A(block)
  ...
  N = ...
  REDISTRIBUTE A(CYCLIC(N))
  call sub(A)
  M = ...
  REDISTRIBUTE A(CYCLIC(M))
  call sub(A)
end
subroutine sub(A(100))
  DISTRIBUTE * A(CYCLIC(*)) ! or whatever syntax
  ...
end

That is a when passing arguments it does make sense to warn the compiler
about an incoming general cyclic distribution without specifying the block
size, because it is not available. I agree that such an information can
help the compiler. On the other hand, if the size is known, then more
benefits may be expected from specifying the value that may reach sub...

My opinion:

 - this particuliar issue should be managed at the DISTRIBUTE level which
   could be extended without any new keyword, as pointed out in the
   example above (derived from yours). 

 - this brings an information not available to HPF as currently defined.
   thus implementation issues are not solved a priori.

 - it is definitely not incompatible with ASSUME (or RANGE):
   I intent ASSUME as a simple and powerful way to express several
   possible reaching mappings for subroutine arguments, as they can be
   described with HPF. Thus putting this particular issue (providing a NEW
   kind of information, not a SET of standard informations) in DISTRIBUTE
   just allow the simple implementation and full expressiveness allowed by
   ASSUME just to work without any problem.

Conclusion, I would suggest to:

 - push for extending the DISTRIBUTE directive semantics to allow
   this NEW kind of mapping information to be available to compilers.

 - push for the ASSUME expressiveness that deals with any available
   mapping information, just telling that several ones may occur.
   (the cyclic(*) included, once managed by compilers).

both extensions are orthogonal, and can be included and managed within a
compiler independently. Thus the best of both words! Great!?

What do you think about it?

Regards,

Fabien.