Subject: hpff-doc: Comments on Mapping, Mapping in Subprogram Calls

From: Thomas Brandes <[email-masked]>
Date: Fri, 13 Sep 1996 11:14:09 +0200

---------------------------------------------------------------------------
[email-masked] is a mailing list for HPF 2.0 language specification
authors and editors.  Instructions for adding or deleting yourself from this
list appear at the bottom of this message.
---------------------------------------------------------------------------

Proposal for Mapping / Mapping in Subprogram Calls
==================================================

A) DESCRIPTIVE / PRESCRIPTIVE / TRANSCRIPTIVE

   Make no longer any difference between descriptive, prescriptive and
   transcriptive !! I doubt that any user can really understand it.
   I have spent a lot of time to understand it. Sometimes I think I have
   but some days later I am again confused.

   Many confusion is due to the fact that mappings can be underspecified.

   Furthermore, the confusion becomes more dramatical with the new 
   proposed RANGE directive that does not go conform with the descriptive
   directives.

   Please do not keep DESCRIPTIVE/PRESCRIPTIVE for history! It is a bad one!

B) FULL SPECIFIED / UNDERSPECIFIED MAPPINGS

   Instead of this make a difference between full specified and
   underspecified mappings. This can be defined as follows:

   - an explicit distribution with ONTO clause (where the processor array
     is specified) is a full specified mapping

   - an explicitly aligned array to a distributee that has a full specified
     mapping has as also a full specfied mapping

   Examples of underspecified mappings:

   !HPF$ DISTRIBUTE A(BLOCK,*) ONTO *
   !HPF$ DISTRIBUTE A(ANY,ANY) ONTO P
   !HPF$ DISTRIBUTE A ONTO P
   !HPF$ DISTRIBUTE A ONTO *

   A full specified mapping is given if there is no choice for the
   compiler about the actual mapping.

   Critical Point (open for discussion, but my view is clear):

   A missing ONTO clause implies a default arrangement. But this
   arrangement is (or not?) identical for distributees that have
   identical shapes and identical explicit mappings.

   !HPF$ DISTRIBUTE A(BLOCK,BLOCK)

   As there is obviously no choice for the compiler, this is also
   a full specified mapping. This is especially useful to have
   full specified mappings without defining processor arrays (that
   cannot be passed to subroutines).

   Attention: the following directives are different:

   !HPF$ DISTRIBUTE A(BLOCK,BLOCK)
   !HPF$ DISTRIBUTE A(BLOCK,BLOCK) ONTO *

C) FULL SPECIFIED MAPPINGS

   A full specified mapping is absolutely necessaray for global arrays
   (mapped arrays in common blocks and in modules). Otherwise the compiler
   might choose different distributions in different compilation units.

      SUBROUTINE SUB1 (...)
      COMMON /DATA/ A(1000,1000)
!HPF$ DISTRIBUTE A(BLOCK,BLOCK)

      SUBROUTINE SUB2 (...)
      COMMON /DATA/ A(1000,1000)
!HPF$ DISTRIBUTE A(BLOCK,BLOCK)

   The following code would be non-conformant:

      SUBROUTINE SUB1 (...)
      COMMON /DATA/ A(1000,1000)
!HPF$ DISTRIBUTE A(BLOCK,BLOCK) ONTO *

      SUBROUTINE SUB2 (...)
      COMMON /DATA/ A(1000,1000)
!HPF$ DISTRIBUTE A(BLOCK,BLOCK) ONTO *

D) SEMANTIC of UNDERSPECIFIED MAPPINGs

   For local arrays with underspecfied mappings the compiler might choose
   the final mapping that has to satisfy the underspecified mapping.
   The final mapping must be compatible with the underspecified mapping.

   For dummy arrays the compiler will generate code that can deal with
   all mappings of the actuals that satisfy the underspefied mapping.
   But the actual must be compatible with the dummy mapping (otherwise
   the data is redistributed).

   For pointers with underspecified mappings the compiler can choose
   the final mapping in an ALLOCATE statement. A pointer can be associated
   with a target if the mapping of the target is compatible.

   Example: !HPF$ DISTRIBUTE C (CYCLIC,BLOCK)

   This works also fine when providing INTERFACE blocks for remappings
   at subroutine boundaries where the compiler might the chose the less
   expensive redistribution.

F) Redistributions at Subroutine Boundaries

   A redistribution is required if the actual argument is not compatible
   with the dummy argument. In this case, an explicit INTERFACE must
   exist.

E) Extensions for underspecified mappings

   For dummy arrays there should be obviously some more general possibilities
   to underspecify the distribution.

   I propose to extend the distributions in such a way that it goes 
   conform with the new proposed RANGE DIRECTIVE.

   dummy_dist_format :: BLOCK [ (int-expr) ]
                        CYCLIC [ (int-expr) ]
                        GEN_BLOCK (int-array)
                        INDIRECT (int-array)
                        *
                        BLOCK ()
                        CYCLIC ()
                        GEN_BLOCK
                        INDIRECT 
                        ALL

   The new forms are used to underspecify the actual distribution.

   For alignments that have strides and offsets another syntax is
   introduced:

   extended_dummy_dist_format : dummy_dist_format
                                ':' dummy_dist_format
                                
F) Compatibily of Mappings

   a) compatibility with processor arrays

   !HPF$ DISTRIBUTE A(BLOCK,BLOCK) ONTO P

   If the processor array is full specified, it implies that the first
   dimension of A is distributed along the first dimension of processor
   array P and the second one along the second dimension of P.

   !HPF$ DISTRIBUTE A(BLOCK,BLOCK) ONTO *P

   This implies that array A is mapped to processor array P (only
   these processors own values of A). But in fact, it can also have
   embedded, replicated or permuted dimensions.

   !HPF$ DISTRIBUTE A(BLOCK,BLOCK) ONTO *

   A is mapped to some processor array. Embedding, replication
   or permutation of dimensions can be possible.

   !HPF$ TEMPLATE T(N,N)
   !HPF$ DISTRIBUTE T(BLOCK,BLOCK) ONTO P
         REAL A(N,N), B(N,N)
   !HPF$ ALIGN A(I,J) WITH T(J,I)
   !HPF$ ALIGN B(I,J) WITH T(I,J)

   The mapping of A and B are both compatible with

   !HPF$ DISTRIBUTE (BLOCK,BLOCK) ONTO *
   !HPF$ DISTRIBUTE (BLOCK,BLOCK) ONTO *P

   But only the mapping of B is compatible with

   !HPF$ DISTRIBUTE (BLOCK,BLOCK) ONTO P

   b) compatibility of distributions

   BLOCK is compatible with BLOCK, BLOCK(), CYCLIC(), ALL
   BLOCK(m) is compatible with BLOCK(m), BLOCK(), GEN_BLOCK, ALL
   CYCLIC is compatible with CYCLIC, CYCLIC(), ALL
   CYLCIC(m) is compatible with CYCLIC(m), CYCLIC(), ALL
   GEN_BLOCK(int_array) is compatible with GEN_BLOCK, ALL
   INDIRIECT(int_array) is compatible with INDIRECT, ALL

   * is compatible with everything under the restriction that
     the processor array is not full specified.

         REAL A(N,N), B(N,N)
   !HPF$ DISTRIBUTE A(*,BLOCK) ONTO P
   !HPF$ DISTRIBUTE B(BLOCK,*) ONTO P

   A and B are both compatible with

   !HPF$ DISTRIBUTE (BLOCK,BLOCK) ONTO *P

   Note: BLOCK and BLOCK(m) are also compatible with GEN_BLOCK which
         is currently not the case for the RANGE directive (but it is
         trivial for the compiler).

   c) Aligned dimensions

   !HPF$ TEMPLATE T(N)
   !HPF$ DISTRIBUTE T(BLOCK)
         REAL A(M)
   !HPF$ ALIGN A(I) with T(a*I+b)

   The mapping of A is not compatible with

   !HPF$ DISTRIBUTE (BLOCK) ONTO *

   as the dimension of A is not really BLOCK distributed.

   Therefore we need a possibility to specfiy this as the compiler has
   to generate more general code.

   !HPF$ DISTRIBUTE A(:BLOCK)

   In general, :<dummy_dist_format> tells the compiler that the actual
   dimension is aligned in some way to a template dimension that has 
   this distribution.

   Note: compiler might take advantage of the fact that the stride will 
         be 1 (special notation ?)

   This notation can also be used if array sections are passed to
   subroutines.

         LOGICAL FRUG(128)
   !HPF$ PROCESSORS DANCE_FLOOR(16)
   !HPF$ DISTRIBUTE (BLOCK) ONTO DANCE_FLOOR :: FRUG
         CALL TERPSICHORE (FRUG(1:40:3))

         SUBROUTINE TERPSICHORE (FOXTROT)
         LOGICAL FOXTROT(:)
   !HPF$ DISTRIBUTE (:BLOCK) ONTO *

   The distribution of the actual array section is compatible with
   the underspecified distribution of the dummy.

   d) Permutations, Embeddings, Replications

   The following code is will not require any redistribution:

   !HPF$ TEMPLATE T(N,N)
   !HPF$ DISTRIBUTE T(BLOCK,CYCLIC)
         REAL A(N,N)
   !HPF$ ALIGN A(I,J) WITH T(J,I)
         call SUB (A,N)

         subroutine SUB (A, N)
         REAL A(N,N)
   !HPF$ DISTRIBUTE A(CYCLIC,BLOCK) ONTO *

   Similiar it is the case for replicated dimensions:

   !HPF$ TEMPLATE T(N,N)
   !HPF$ DISTRIBUTE T(BLOCK,CYCLIC)
         REAL A(N)
   !HPF$ ALIGN A(I) WITH T(I,*)
         call SUB (A,N)

         subroutine SUB (A, N)
         REAL A(N)
   !HPF$ DISTRIBUTE A(CYCLIC) ONTO *

   Embedded arrays can also be compatible with underspecified distributions:

   !HPF$ TEMPLATE T(N,N)
   !HPF$ DISTRIBUTE T(BLOCK,CYCLIC)
         REAL A(N)
   !HPF$ ALIGN A(I) WITH T(I,2)
         call SUB (A,N)

         subroutine SUB (A, N)
         REAL A(N)
   !HPF$ DISTRIBUTE A(CYCLIC)

   e) Compatibility of aligned arrays

         REAL B(N,N)
         REAL A(N,N)
   !HPF$ DISTRIBUTE A(BLOCK,BLOCK)
   !HPF$ ALIGN B(I,J) WITH A(I,J)
         CALL SUB (A,B)

         SUBROUTINE SUB (X,Y)
         REAL X(:,:), Y(:,:)
   !HPF$ DISTRIBUTE Y(BLOCK,BLOCK)
   !HPF$ ALIGN Y(I,J) WITH X(I,J)

   The aligned array B is compatible with the distribution of the dummy
   argument Y. The distribution of A is also compatible with the
   alignment of Y (as in this case the alignment can be inversed).

   Advice to users: It might be the case that a compiler cannot verify
   compatibility and might generate code for redistribution. But at
   runtime the compatibility guarantees that only local copy is
   required.

G) INHERIT + RANGE DIRECTIVE

   !HPF$ INHERIT X
 
   is equivalent to !HPF$ DISTRIBUTE X (:ALL, ..., :ALL) ONTO *

   !HPF$ RANGE <dummy_distribution_list>
 
   goes conform with the current solution but allows different possibilites
   instead of one single distribution directive.

H) What should be in the approved extensions ?

   Probably the new possibilities for underspecified distributions
   should be put into the approved extensions.

I) Conformance to the current standard

   !HPF$ INHERIT is equivalent to

   !HPF$ DISTRIBUTE (:ALL,...,:ALL) ONTO *

   The syntax of prescriptive directives could still be used but there
   is no semantic difference.

   !HPF$ DISTRIBUTE *(BLOCK,BLOCK) ONTO P
   !HPF$ DISTRIBUTE (BLOCK,BLOCK) ONTO P

Summary of Advantages:
======================

a) the concept is more clean and will hopefully cause less confusion
   for the user.

b) much more flexibility in writing 'efficient' code that can deal
   with different distributions, e.g.:

         SUBROUTINE SUB (A)
         REAL A(:,:)
   !HPF$ DISTRIBUTE A (:BLOCK,:BLOCK) ONTO *
         ...
         END SUBROUTINE

c) compatibility with the RANGE directive of the approved extensions

d) implementation in a compiler is not too complicated (I hope!)

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