Subject: hpff-external: Re: Descriptors

From: [email-masked] (Scott B. Baden)
Date: Sun, 17 Sep 1995 19:33:15 -0700 (PDT)

---------------------------------------------------------------------------
[email-masked] is a mailing list for discussion of external
interfaces between HPF and other languages/systems.  Instructions for
adding or deleting yourself from this list appear at the bottom of this
message.
---------------------------------------------------------------------------

Here is a very rough  proposal for calling HPF from an extrinsic SPMD program.
I'll call this "HPF to SPMD" for short.

We going to need to work with the MPI and C++ folks as well as
some of the vendors who are writing the compilers.

Proposal for calling HPF from an extrinsic SPMD program.
	Scott Baden, Chuck Koelbel, Rob Schreiber

In some applications it is useful to handle coordination and data
motion in an SPMD "harness" written in an extrinsic language, and to
invoke HPF from this harness to handle computation.  This facility mirrors the
"HPF-to-SPMD"  facility described in Annex A of the HPF spec, and
"mirrors" many of the ideas described therein. We also get a limited
form of task parallelism if we admit MPMD (multiple data multiple
program) parallelism.

We can think of an SPMD program in terms of an MPI communicator:
loosely synchronous execution of the same program on multiple
processors. (Similarly with MPMD: different programs running on
different processors.)

Since MPI allows one to configure a processor topology for a
communicator (using the cache mechanism) it makes sense to identify an
MPI communicator topology with an HPF PROCESSORS spec.  The advantage
of this approach is that the values returned by NUMBER_OF_PROCESSORS
and PROCESSORS_SHAPE are well-defined.  Note that it is possible to
dynamically change the members of a communicator or the processor
topology.  The consequences of this will require some thought.

3 sets of entries are needed that enable the user to  interact with
HPF.  (This spec should be language independent in keeping with
tradition.) These entries should be called with "the same arguments at
roughly the same time," i.e. in loosely synchronous fashion, by all
members of a  communicator.

    The entries

I. hpf_init(), which establishes various state needed by the
HPF run time system.

II.  create_mapped_array_descriptor(), which returns an opaque pointer
to a descriptor of a mapped array with specified shape,
alignment, distribution, processors spec, and so on.
(Rob also mentions an inverse of create_mapped_array_descriptor.
I'll get to this later on.)

III. various query routines that enable the user to access a mapped
array using an interface defined by HPF.  In effect these
are "mirror images" of routines defined in  Annex A of the HPF spec.

Details.

I.  HPF_INIT().  I'll punt on this for now.

II.  create_mapped_array_descriptor()

This routine is the workhorse of the interface.  We borrow the idea
from local HPF that a local grid is viewed in terms of a set of blocks,
and that there is a standard interface comprising routines that enable
the SPMD programmer to efficiently access and iterate over the data.
This is nicely defined in Annex A, which I adapt for the task at hand:

"All HPF arrays accessible from an SPMD procedure are logically carved
up into pieces; the SPMD process executing on a particular physical
processor sees an array containing just those elements of the global
array that are mapped to that physical processor.

"The model assumes that array axes are mapped independently to axes of a
rectangular processors grid, each array axis to at most one processors
axis (no "skew" distributions) and no two array axes to the same
processors axis.  This restriction suffices to ensure that each
physical processor contains a subset of array elements that can be
locally arranged in a rectangular configuration (of course to compute
the global indices of an element given its local indices or vice verse,
may be quite a tangled computation-- but it will be possible)

    Rob suggested::
>  
>  I think what we need is the inverse of create_mapped_array_descriptor.  Something
>  that is an ordinary struct or something in C++ that can be used to describe
>  to the HPF runtime (not the application) the shape and mapping of an array
>  that has been created by the C++ calling routine:
>  
>  
>     subroutine hpf_called_from_extrinsic(x_desc, x)
>  !
>  !  this routine is called collectively by an extrinsic that has passed in
>  !  both the mapped array X, and a descriptor of this mapped array
>  !
>  	type (mapped_array_descriptor) x_desc
>  	real x(:,:,:)   !   Use assumed shape array
>  	call describe_mapped_array_argument(x_desc, x)  ! Tell HPF about X

I'm not sure why we need this.

    ** SPMD execution model**

A communicator collectively allocates a mapped array by making a call
to create_mapped_array_descriptor(), which returns an opaque pointer.
HPF routines are called by all members of the communicator.  Opaque
pointers returned by create_mapped_array_descriptor() are passed as
arguments to an HPF routine.  All members of the communicator group
must pass the same opaque pointer in each corresponding position of the
argument list.  As far as the HPF routine is concerned, it won't know
the origin of the argument, which could have in fact originated from
another HPF program.

We must place certain restrictions on our SPMD/HPF model.

0. Calls to an allocation routine or to an HPF routine
    must be loosely synchronized.   Clearly all members of the communicator
    must EVENTUALLY call the HPF routine.

1. The SPMD program is responsible for passing global arrays to an HPF
   routine in conformance  with the routine's expectations, i.e. the distribution
   must match and so on.  (The only exception is when the HPF routine
   employs a transcriptive declaration.) This implies that we will
   need utilities to redistribute and remap existing array since
   the compiler can't be expected to handle this for us.

2. Actual scalar arguments must be consistent across the communicator.

(This statement mirrors that of Annex A, which pertains to the HPF
calling SPMD model:

    "Actual arguments corresponding to scalar dummy arguments are
	replicated (by broadcasting, for example) in all processors.")

3. Data motion between communicators must be handled at the SPMD level.
  This implies that global arrays allocated in different communicators
  cannot be passed to the same HPF routine.  (There there is language
  in Annex A that applies to the HPF to SPMD case.) 
   Note that different subgroups can call different HPF routines,
  and this admits task parallelism.

4. We may not want to permit an HPF routine that had been called FROM SPMD
   to in turn call SPMD at a lower level (i.e. HPF local) routine.
   (There's a similar but mirrored restriction in Annex A for calling
   an HPF local routine from HPF)

III. Query functions and other entries.
Required entries.
We need the following query routines, as described in Annex A:
 GLOBAL_DISTRIBUTION()
 GLOBAL_LBOUND()
 GLOBAL_UBOUND()
 GLOBAL_SHAPE()
 GLOBAL_SIZE()
 ABSTRACT_TO_PHYSICAL()
 PHYSICAL_TO_ABSTRACT()
 LOCAL_TO_GLOBAL()
 GLOBAL_TO_LOCAL()
 LOCAL_BLKCNT()
 LOCAL_LINDEX()
 LOCAL_UINDEX()

Note that employ opaque mapped array descriptors in place of the
(HPF) ARRAY arguments that the Annex specifies for these functions

We also need routines that handle HPF style REDISTRIBUTE,
and that perform I/O, should this be included in HPF 2.0.

 **** Matters to be resolved. ***

1. There can be several processor arrangements, with different ranks
and upper and lower bounds.  If a processor changed communicators (more
likely, if it made two calls, one as a member of each communicator),
then HPF_INIT would have to be called again.  The key constraint is
that the HPF subroutine can declare exactly one processors arrangement,
and the SPMD call would have to match this declaration.  The problem
is we can't pass a PROCESSORS arrangment as an argument
because these are static directives in HPF(Chuck Koelbel)

2.  Should HPF common blocks be accessible from SPMD?
    What are the consequences of this?  There may be a problem since it
isn't possible to specify data movement between communicators in HPF
code.  Presumably this implies that we can't access an array in COMMON unless
the element we want happens to be stored on a processor in the
appropriate group. (Chuck Koelbel)

3.  I/O should probably not be done from HPF directly.  In this case we
would need to provide all the HPF I/O facilities via specially defined
entries.
Comments?

Scott

---------------------------------------------------------------------------
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: Doug MacDonald <[email-masked]>
Date: Mon, 18 Sep 95 12:14:15 EDT

...

Hi,

I've been working on a "local/global" programming model for Thinking
Machines and have some responses to this proposal.  In general I agree with
what it says.  I have some comments and suggestions throughout the text and
at the end.  There are probably other issues but these are the ones that
occur to me right now...

Regards,
Doug MacDonald

Descriptor queries called locally in an HPF-to-SPMD local routine should be
via a standard function interface to which an opaque descriptor ID is
passed.

Is it necessary to link HPF with MPI?  They both seem to be dominant
standards, but if it can be avoided, it should be.  Linking puts users at
the mercy of the correctness and performance of the MPI implementation to
which they have access.

       The entries

I like the idea of a function interface with a subroutine
create_mapped_array_descriptor() defined as part of an HPF implementation.
In this way, descriptors compatible with the HPF descriptor set are
generated, giving what I call _language interoperability_.

Another issue is _memory interoperability_ HPF 1.0 at least doesn't mandate
a particular axis nesting order or even contiguity of local subgrids of a
global array.

Fortran subgrids are likely to be column-major.  In an HPF that allocates
local subgrids contiguously and in column-major order, This may be OK for a
Fortran 90 or f77 SPMD program.  But what about a C program?  You need to
specify a convention for what happpens to local row-major arrays.  I
suggest reversing the array's axis ordering on the global level.

Sometimes local subgrids are enlarged to receive boundary exchange values
to support stencils and similar codes.  In the best of worlds, the HPF
implementation will also use such expanded subgrids in its stencil
optimizations.  Such an HPF implementation must be able to support
non-contiguous memory layouts (successive columns owned by a given
processor are separated by the top and bottom boundary pointes).

Also, there should be a story about (a) how such expanded subgrids are
mapped to the global array's coordinate space, (b) when users must
guarantee subgrid boundary points to be consistent, e.g., just before a
call to global HPF.

Support for creating replicated arrays is important.

   Details.

If there is to be full language interoperability, there shouldn't be any
restriction on SPMD -> global HPF -> SPMF or HPF_LOCAL calling.  This
restricts how HPF-compatible global library routines could be implemented
by third parties.  One very useful way to implement such library routines
is in SPMD.  If this call pattern is not permitted, HPF routines that call
SPMD routines could not themselves be called in an SPMD application.  Or
have I misunderstand this?

   Scott

Another issue is _memory interoperability_ This is a bit more tricky, since
Fortran subgrids are likely to be column-major.  OK for a Fortran 90 or f77
SPMD program, but what about a C SPMD program?  You need to specify a
convention for what happpens to local row-major arrays.  If an HPF
implementation is to insist on column-major local memory storage, I suggest
a convention of reversing the array's axis numbering on the global level
when called from C.

Support for creating replicated arrays is important.

Sometimes local subgrids are enlarged to receive boundary exchange values
to support stencils and similar codes.  In the best of worlds, the HPF
implementation will also use such expanded subgrids in its stencil
optimizations.  There should be a story about (a) how such subgrids are
mapped to the global array's coordinate space, and (b) when subgrid
boundaries must be consistent, e.g., just before a call to global HPF.

Some global Fortran implementations that execute on a SIMD-like mode with a
control thread on a scalar processor which broadcasts RPC-like function
calls to the processing nodes, as in the CM-5.  In such implementations,
local subgrid addresses and any other local addresses that are broadcast
from the control thread to the nodes are (and must be) identical node to
node.  This is guaranteed by a memory management subsystem in the RTS that
is managed from the scalar processor.  But SPMD routines running on nodes
don't have access to this mm scheme, and malloc() will probably yield
inconsistent values across the nodes.  This is a real problem for these
implementations.  One solution is to provide also an alternate routine,
create_mapped_array_and_descriptor(), which allocates temp storage using
the HPF memory management subsystem and guarantees equality of subgrid
addresses.

Given an HPF data mapping, you need to be able to convert local coordinates
to global coordinates and back again, to determine what position along a
processors axis a given local coordinate falls on, and whether a given
global tuplet is local to the querying processor.  Some of this is done by
GLOBAL_TO_LOCAL() and LOCAL_TO_GLOBAL().  They need to work for all
supported data mappings.
---------------------------------------------------------------------------
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>
---------------------------------------------------------------------------