Subject: collcomm changes, rationale

From: [email-masked]
Date: Sun, 14 Mar 93 12:46:57 PST

RATIONALE FOR SUGGESTED CHANGES TO COLLECTIVE COMMUNICATION PROPOSAL

In a related summary, I outlined a set of suggested changes to
the concepts and routines in the collective communication proposal.

The purpose of this note is to present the rationale for those
suggestions and to discuss possible alternatives.

The discussion is organized into 5 areas, flagged with "----- Topic #".

Entries flagged with > are from my summary of suggested changes.
Entries flagged with >>> are from the draft proposal sent out by Al Geist.

----- Topic #1: Group Identification -----

> . The concept of group identification has been firmed up.  Most
>   operations use a "group handle" that is local to the process.
>   (Think of the group handle as being just the address of a
>   potentially large and complex "group descriptor".)
>        ...
> . A semantic restriction is introduced, that a process can access
>   information about a group only if the process holds a group
>   handle for it.  Group handles can be obtained in two ways: 1)
>   they are produced by group formation routines, and 2) a process
>   can explicitly distribute copies of its group handles to other
>   processes, using new routines introduced specifically for that
>   purpose.

There are two issues here: one of being able to layer collective
communications on top of point-to-point at all, and a secondary
one of efficiency.

The more fundamental issue is layering.  Given only MPI point-
to-point functionality, how can a group identifier (whatever it
is) be transmitted between processes so as to be useful to the
receiver?

Presumably we want to allow group identifiers to be passed around so
that any process holding the group identifier can use it for purposes
like translating between (group,rank) and pid.  We also want to allow
this translation to be done asynchronously, i.e., without requiring
the explicit cooperation of any other MPI process at the time of
translation.  Since MPI pt-pt does not support asynchronous servers or
an interrupt receive capability, this implies that the group
identifier must come complete with enough information to resolve all
translations without communication.

This prompts the concept that the group identifier must be associated
with a "group descriptor" that is large and complex enough to
fully describe the group.

How is the association done?  This is a question of efficiency.  If
the identifier is allowed to be process-local, the group descriptor
can be located very quickly -- just make the identifier be a pointer
to the group descriptor.  Requiring the identifier to have global
scope would not be so good.  In that case, either the identifier has
to be carefully constructed or the association has to be done with
some sort of table search.  These issues also arise with global pid's.
However, groups can be formed much more often and in greater numbers
than processes.  I doubt that careful construction tricks could be
assured to be adequate, and if not, then a table search would be
required on each collective communication call.

The conclusion is that, for most purposes, a process-local
identifier generated by the system is preferred.  Such things are
typically called "handles", hence the term "group handle".

> 4. Distribution of group handles and disposition of distributed handles:
> 
>     MPI_SendGroupHandle (pid,context,tag,old_group_handle)
> 
>     new_group_handle = MPI_RecvGroupHandle (pid,context,tag)
> 
>     MPI_FreeGroupHandle  (group_handle)

The next question is how group handles should be distributed.

Implicit distribution is out because MPI pt-pt doesn't support
a server capability, and presumably we aren't willing to synchronize
all of the processes whenever somebody creates a group handle.

So, explicit distribution is required.  How do we handle it?

Two ideas that I do not like are the following.  MPI might provide
routines to translate to and from some machine- and process-
independent format, so that the translated information could be sent
using normal point-point primitives.  This strategy requires that the
user program manage the storage of indefinite-length objects, which
makes for an ugly Fortran interface.  Or, group descriptors (and their
translation routines) might be built into point-point MPI as another
data type.  This violates the spirit of layering collective
communication on point-to-point, and has the same storage management
problem.

The three routines proposed above were the cleanest interface
I could think of.

----- Topic #2: Global Group ID -----

>   There is
>   still a "group ID" that is globally unique, but it has only a
>   secondary role and can be ignored by most applications.  
>         ...
>     global_id = MPI_GetGlobalGroupID (grouphandle)

Given that we are now able (and required) to pass around copies of
group handles, it is not clear to me that MPI really needs special
support for the concept of a global group ID.  On the other hand,
it's easy to provide, since we have to construct one or more
globally unique context values for each group anyway.  So just
use the first such context value as the global ID.  This gives
something unique that all processes can agree on.  

But note that knowing just the global group ID does not let you
get other information about the group -- you have to hold a group
handle for that.

(We could add a routine that would accept the global group ID and
return a handle for that group, presuming that the process held
one.  This would be cheap to do, since group handles are managed
by MPI anyway, and I can vaguely imagine that it might help some
applications.  On the other hand, there are no similar "handle
lookup" facilities provided elsewhere in MPI, and I'm reluctant
to set that kind of precedent without clear need.)

----- Topic #3: Group Formation -----

> . A new group formation routine is introduced, that is less
>   synchronous and more general than MPI_PARTGROUP.
>        ...
> 1. Arbitrary group formation:
> 
>     newgrp_handle = MPI_FORMGROUP (grouptag,groupsize,knownmembers)
> 
>     where
>      grouptag     is a user-provided integer tag, sufficiently unique
>                   to disambiguate overlapping groups that might be
>                   formed simultaneously, say by multiple threads.
> 
>      groupsize    is the number of members that will compose the group.
> 
>      knownmembers is a set of pid's of some or all members of the group.
>                   Each member of the group must provide the same
>                   set of knownmembers.
> 
>      newgrp_handle     is a group handle for the newly formed group
> 
>     This new routine must be called synchronously, but only by those
>     processes forming the group.  

The draft proposal distributed by Al Geist says that

>>> A group is identified by a group name that is supplied by the user.

A group name by itself is not enough to allow implementing groups
as a layer on top of point-to-point, unless we impose
restrictions that I think would be not acceptable.

The problem is: how does a group-forming routine know whom it
should send messages to, in order to form the group?

MPI_PARTGROUP does not have a problem with this, because it has
to be called synchronously by all members of the group.  Since
each current member of the group holds a handle (descriptor) for
that group, it is easy for each member to figure out who talks to
whom.

Unfortunately, there are some important application designs that
I do not see how to implement with just MPI_PARTGROUP.

For example, I am now doing an application that uses a
master-slaves strategy to asynchronously parcel out chunks of
work, with each chunk being done by several processes working
collaboratively.  Collective communication between those
processes is required, so it seems natural to organize them into
MPI groups.  Using a synchronous group partitioning routine
would introduce a risk of load imbalance, because the varying
chunk size implies that groups can finish their work at
different times, and synchronous partitioning would delay their
reassignment.

Applications like this could benefit from a group formation
routine that is called synchronously, but only by those
processes forming the group -- hence MPI_FORMGROUP.

This type of routine does have the problem of identifying its
collaborators, and the only solution I can think of is to
tell it.  That's what the knownmembers argument is for.

I have specified knownmembers in terms of pid's because I assume
that point-to-point communication based on pid's is always fast
and unrestricted.  If knownmembers were based on (group,rank)
pairs, then per the discussion above, all processes making this
call would have to hold handles (descriptors) for the referenced
groups.  This seems to me to be more trouble than it's worth, but
others may disagree.

Another comment about efficiency...  The size of the knownmembers
set affects the efficiency of group formation.  At one extreme,
only one member is required to be known.  This is scalable in a
memory sense, but not in a time sense, because it implies O(P)
group formation time for a group of P processes.  At the other
extreme, all members can be specified.  This is not scalable in a
memory sense, but allows guaranteed O(log P) formation time.
Other tradeoffs are possible, such as O(sqrt P) knownmembers and
O(sqrt P) formation time.  The interface as specified allows
each application to choose the type of scalability it wants.

----- Topic #4: Group Names -----

>   ...  The
>   "group name" is entirely removed from MPI-1.  (Group names are
>   still anticipated in MPI-2, but upward-compatibility is
>   maintained in a different way from the draft proposal.)

The draft distributed by Al Geist states:

>>> To allow for future extensibility of the group concept
>>> the present draft specifies that groups be named. 

Requiring names has the drawback that 1) it burdens the user with
at least the appearance of having to create unique names, in
order to be upward-compatible with dynamic groups, even though 2)
in a layered MPI-1, there is no way in general to check global
uniqueness, and thus programs can work fine with non-unique names.

This combination strikes me as actually impeding upward-
compatibility.  The tendency will be for programmers to use
non-unique names because it works and it's easy.  But such programs
would break when MPI-2 came along and started actually using
the names for something.  I don't like encouraging people to
write programs that are going to break.

I do support upward compatibility.  However, rather than requiring
names in MPI-1, I propose that they be deferred entirely to
MPI-2, at which point they can be supported either just through
MPI_JOINGROUP (as an alternative to MPI_FORMGROUP) or via
additional routines to attach globally unique names to groups
that have already been formed via MPI_JOINGROUP.

----- Topic #5: Cacheing -----

> 5. Cacheing group-specific process-local information:
> 
>     The following routines get and free keys for use with group
>     cacheing.
> 
>       key = MPI_GetAttributeKey ()
>       MPI_FreeAttributeKey ()
> 
>     The following routines cache and retrieve information.
> 
>       MPI_SetGroupAttribute  (grouphandle,key,value,destructor_routine)
>       MPI_TestGroupAttribute (grouphandle,key,&value)
> 
>     where
>       key         must be unique within the group
>       value       is anything the size of a pointer
>       destructor_routine   is an application-provided routine that
>                            is called by MPI_LVGROUP, with arguments
>                            being the group handle, cached key and value.
> 
>     Cached information is stripped from the new group handle
>     returned by MPI_SendGroupHandle.
> 
>     In a conforming implementation, MPI_TestGroupAttribute must
>     be no slower than a point-to-point communication call.

This feature is purely for efficiency, but I think it's so valuable,
cheap, and clean that something like it has to go in.

One feature of collective communication is that the fastest
algorithm for any particular job usually depends on the machine
topology, which processes belong to the group, and the amount of
data being manipulated.  For example, global combine of L data
elements across P = RC processes on a 2-D RxC mesh can be done in
O(L log(P)) time using a fanin/fanout algorithm, or in O(L + sqrt(P))
time using a nested rings algorithm.  The former is better for
small L, the latter for big L, and using the wrong one can easily
cost a factor of 3 in execution time.

So, there is strong motivation to write collective communication
routines that are adaptive in the sense of figuring out which
algorithm is best.  The problem is that it can take quite a lot
of time to make the decision, starting from a scratch position
of not even knowing which processes belong to the group.  It's
going to take lots of calls to the inquiry routines to get that
information, and then some more cycles to make the proper decisions.

Obviously it would be profitable to cache the information and/or
decisions.  The question is, where?  

It is tempting to say that the collective communication routine
could or should keep its own cache, indexed by group handle
and/or global group ID.  The problem is, groups are dynamic in
the sense of being formed and disbanded, so that unless group IDs
can get very large, eventually they will have to be reused.  Now,
it wouldn't do to have a collective communication routine use
stale cached information, so if the collective communication
routine is keeping its own cache, then it needs to be notified of
the reuse so that it can release the cached stuff.
Alternatively, perhaps the cached information could be
automatically released.  (Either strategy guarantees immediate
release of cached info when the group handle/descriptor is
released.  I presume we want to do that, to avoid getting into
the morass of garbage collection.)

The method proposed here can be thought of as implementing both
strategies.  The idea is that the routines that free group
handles (and the associated descriptors) loop through the cached
information, calling an application-provided destructor routine
for each piece of cached information.  Typically, the cached
information will be a pointer to a hunk of memory managed by the
collective communication, which the destructor will free in
whatever way it has to.  Upon return from the destructor, the
group-freeing routine will release the little piece of memory
holding the pointer, and everything will be cleaned up.

If that group handle/descriptor is ever reused, it will be
reinitialized to indicate no cached information, and
MPI_TestGroupAttribute will return "not found".

An efficient-after-first-call group-global operation using 
cacheing might look like this:

   static int gop_key_assigned = 0;    /* 0 only on first entry */
   static MPI_key_type gop_key;        /* key for this module's stuff */

   efficient_global_op (grphandle, ...)
   struct group_descriptor_type *grphandle;
   {
     struct gop_stuff_type *gop_stuff;   /* whatever we need */

     if (!gop_key_assigned)     /* get a key on first call ever */
     { gop_key_assigned = 1;
       if ( ! (gop_key = MPI_GetAttributeKey()) ) {
         MPI_abort ("Insufficient keys available");
       }
     }

     if (MPI_TestGroupAttribute (grphandle,gop_key,&gop_stuff))
     { /* This module has executed in this group before.
          We will use the cached information */
     }
     else
     { /* This is a group that we have not yet cached anything in.
          We will now do so.
        */

       gop_stuff = /* malloc a gop_stuff_type */
  
       /* ... fill in *gop_stuff with whatever we want ... */

       MPI_SetGroupAttribute (grphandle, gop_key, gop_stuff, 
                              gop_stuff_destructor);
     }

     /* ... use contents of *gop_stuff to do the global op ... */
     
    }

    gop_stuff_destructor (gop_stuff)   /* called by MPI on group close */
    struct gop_stuff_type *gop_stuff;
    {
      /* ... free storage pointed to by gop_stuff ... */
    }

----------------------------------------------------------------------
[email-masked]               Rik Littlefield
Tel: 509-375-3927                    Pacific Northwest Lab, MS K1-87
                                     P.O.Box 999, Richland, WA  99352