Subject: Response to comments on Pr. VIII

From: [email-masked] (Mark P. Sears)
Date: Mon, 29 Mar 93 16:23:17 -0700

Tom (and other colleagues in MPI),

Thanks for your interest and let me try to answer some of your questions,
according to my point of view. I apologize for any lack of clarity in
the proposal (I had the flu when I wrote it). My proposal was certainly
not at the level of detail needed for insertion in the MPI document --
it was intended more as a position statement.

In the following, my comments begin with **** in response to Tom's
statements and questions. I end with some responses to Jim Cownie's
comments.

Mark P. Sears
Sandia National Laboratories
**********************************************************************

(from Tom Henderson's email:)

1)  Process ID's are globally unique integers.  I see this as a minor 
    advantage.  When PID is an opaque data type, we get the "identity" 
    problem:  how do I tell if PID A is the same as PID B?  I need to use 
    a special routine (like MPI_RANK() in Proposal I).

**** I agree with this.

**** In addition, our current model of a parallel task in MPI is rather
**** static: all the processes in the task are created and destroyed
**** simultaneously and all can communicate with one another. So why not
**** just number them? That is current common practice anyway. The numbering
**** encodes the system's idea of the best process ordering. Opaque id's
**** promote a sense that any ordering is just as good as any other, which
**** is not the case for high performance applications. 

2)  Contexts are globally unique integers.  Global uniqueness makes context 
    creation "slow".  Given the intended use of contexts, I do not see this as 
    a problem.  Your current proposal does not explain how contexts are 
    "created" in much detail.  Here's three (non-exclusive) possibilities:  

    A)  make_group_contexts(group, num_contexts, new_contexts)
          num_contexts new contexts are placed in array new_contexts.  This 
          routine must be called "loosely-synchronously" in every process in 
          the list of processes called "group".  This is a convenient way for 
          a user to create one or more contexts.  It does not imply any 
          relationship between groups and contexts.  

    B)  get_registered_contexts(context_name, num_contexts, new_contexts)
          This is a "name-server" version.  If one or more contexts are 
          registered under the name "context_name", then the first 
          num_contexts contexts are copied into array new_contexts.  If 
          "context_name" is not currently registered, allocate num_contexts 
          new contexts and register them under name "context_name".  

          Some folks will not need groups.  There must be a way to allow
          access to  contexts without using groups.  (However, see #3
          below...)  

    C)  make_list_contexts(list_of_PIDs, num_contexts, new_contexts)
          This could easily be (A).  The only reason for having this version 
          would be if "group" has other stuff "cached" with it.  This one 
          could be left out if "group" is just a "list of PIDs".  

**** Here I had in mind a hardware or low level model of context, just
**** implemented as a few bits in what is now the tag field of the
**** message envelope. From this point of view, contexts are a scarce
**** resource, but this matches well with the idea that contexts are
**** associated with different software components of a program - most
**** programs use only a handful of independent software components
**** (the main app, a few libraries). My model of how the underlying
**** implementation uses context is that a message (or part thereof)
**** arrives at a process and must then be queued or matched with an
**** outstanding receive. If there are not many possible context values then
**** the number of possible queues is not large either, and all of the
**** resources needed to support all context values can be preallocated
**** in process startup.  For 16 or 256 context values we can easily imagine
**** this not taking very long, order milliseconds. Then context values can
**** be used like tag values -- they preexist and can be utilized and allocated
**** according to any desired scheme. If we must specify an allocation scheme,
**** then I would recommend something like
****
****    context_value = MPI_get_context()
****
**** where the routine must be called synchronously on every processor.
**** This routine would typically be called a few times by the various
**** initialization code for the various software components.

**** The bottom line is that contexts preexist and a very simple (or no)
**** allocation/deallocation scheme is needed.

3)  I did not completely understand this:  
>   5) This proposal requires no server code and most of the
> group code is not even parallel. I did a test implementation of
> groups as defined here and was able to build code for identity
> groups, permutation groups, linear and bilinear groups, general
> set groups (Tony's favorite), composition groups, Cartesian products
> and cartesian subsets (my favorite), all in about 700 lines of code.
> The group definition really lends itself to object-oriented user
> extensibility, like X widgets but easier.
    Are you talking about groups only here?  If not, how are you proposing to 
    maintain globally synchronous allocation/deallocation of contexts?  

**** Yes, groups only. See above comments on context.

4)  Minor questions:  
>    6) Groups are easily constructed and destroyed, since no
> global communication is required. Dynamic groups are not excluded,
> although they must be used carefully. Since groups have no associated
> context, there are no resources limiting their construction other than
> memory and CPU time.
    You say "global" communication is not required.  I assume that 
    communication among the members of a created group is required?  (Seems 
    obvious...)

**** There is no magic, of course. Sometimes, group creation requires
**** communication and sometimes not. Many interesting groups can be
**** computed rather than communicated, for example the row and column
**** subgroups of a group representing a rectangle. Other groups require
**** communication in order for each process to know whether it belongs
**** to a group or not, the random list group being a good example, but I
**** see that communication as independent of the construction of the group.
**** That is, you communicate the list of processes wherever needed, then
**** each process that needs the group builds it from the list.

5)  Clarification:  
>   There is no reason to disallow user-defined groups (e.g. dynamic
> groups).
    The term "dynamic group" has been used to mean different things in the 
    mpi-context discussion.  Are you talking about a user-created group whose 
    membership does not change?  Are you talking about a user-created group 
    whose membership can change after creation?  Are you talking about 
    something else?  

**** A group is just a mapping or function. This function could be
**** one predefined by MPI or one defined by a (knowlegeable) user. MPI could
**** restrict itself to a few simple kinds of groups and allow the user to
**** implement code for groups whose membership changes (what I meant by
**** dynamic groups) or groups with properties we haven't thought of yet.

6)  My understanding of this proposal is that "group" is an array of integers, 
    probably including range(group).  You mention that other information could 
    be cached with "group".  Are you proposing a "handle" or "opaque object"?  

**** A group is not explictly an array. Most groups in my view (this is
**** biased by the kind of work I do, of course) will be computed rather
**** than given as explicit lists. So a group is a union of possible
**** structures. Each kind of structure knows how to compute the
**** needed functions (element(group, rank), rank(group, element, etc) -- all
**** very straightforward with modern C programming techniques. Maybe
**** that computation uses a list, maybe it doesn't.
**** What the user gets from a group creation operation
**** is a pointer to the object defining the group. The pointer is of
**** course an opaque type valid only on the process that created that
**** group.

**** The kind of information likely to be cached with a group is probably
**** a spanning tree or set of exchanges which are optimized for the
**** particular group. Alternatively it is possible to cache optimized methods
**** for operations such as broadcast or synchronization. 

7)  How are you proposing groups be created?  It would be nice to see a few 
    proposed routines.  (Or, "it's done just like proposal XXX.)  

**** I hope you don't want code! (I will mail it to anyone that asks).

**** Let me begin with defining a classification of groups. Each class
**** here is defined in terms of the function element(group, rank). Each
**** type of group will have its own constructor with the parameters
**** needed for that type. The output of the constructor is a pointer
**** to the actual group object.
****
****  Class:        element(rank)                    parameters:
****  ------        -------------                    -----------
****  Identity      rank.                            order
****  Permutation   p(rank) for some permutation p.  order, p
****  List          list(rank)                       order, list
****  Linear        start + rank*delta               order, start, delta
****  Bilinear      start + r1 * d1 + r2 * d2        order, n1, d1, d2
****                 where rank = r1 + n1 * r2
****  Composition   g1(g2(rank))                     (group) g1, g2
****  Product       g1(r1) + range(g1)*g2(r2)        (group) g1, g2

****  So the constructor for a linear group would be defined like
****
****    Group MPI_make_linear_group(order, start, delta), 
****
****  which returns a pointer to the actual group structure. Each
****  class of groups would have a specific constructor.
****
****  The functions common to all groups would be defined like
****
****    int MPI_group_order(Group g)
****    int MPI_group_range(Group g)
****    int MPI_group_iselement(Group g, int element)
****    int MPI_group_rank(Group g, int element)
****    int MPI_group_element(Group g, int rank)
****
**** In addition in my test implementation I defined some other
**** stuff like a destructor, copy constructor, etc. 

**** Although I have made heavy use of C pointers here, a Fortran
**** binding is not too hard to construct.

8)  Is this what you had in mind?  (My understanding of some of the things 
    you've said...):

    * All point-to-point communication uses (PID, context, tag).  
**** Yes.

    * All collective communication uses (group, context, tag) (with the caveat 
      that tag may be eliminated by the collcomm committee).  
**** Here the committee could eliminate tag and context together but not
**** independently, I think. How could I call such a routine not knowing
**** which tags it was going to use for the operation? If neither is
**** available then the MPI routines must use an internal context and
**** set of tags.

    * Third-party library routines that use collective communication must have 
      (group, context) passed in as arguments.  
    * Third-party library routines that use point-to-point communication 
      within a group must have (group, context) passed in as arguments.  
      (PID's are then extracted inside the routine using element(), etc.)  
    * Third-party library routines that use point-to-point communication 
      without reference to groups must have (PID's, context) passed in as 
      arguments.  

**** Not quite.

**** In my view there are two categories of third party routines: one
**** category which establishes and uses its own context and tag spaces
**** and a second category which uses the context and tag spaces given
**** to it. Both kinds are useful -- MPI must be careful not to preclude
**** one or the other. 

    * Group-based point-to-point calls will look like:  
        send(element(group,rank), context, tag, ...)
        recv(element(group,rank), context, tag, ...)

**** Yes.

    * Default group and default context are provided.  When used, these look 
      like:  
        send(element(group,rank), MPI_DEF_CONTEXT, tag, ...)
        barrier(MPI_DEF_GROUP, MPI_DEF_CONTEXT)

**** Yes. Default context (free-for-all) especially is intended for
**** the poor hapless end-user slob (I wear this hat occasionally)
**** who hasn't got the time to understand all our machinations. :-)

**** Default group is a trivial group (what I would call an identity
**** group) which maps rank into itself, assuming PID == rank.
 
9)  The examples above imply that context appears in all communication 
    routines.  There could be special versions of all communication 
    routines that use the default application context.  I'd prefer to avoid 
    this.  No one has proposed special versions of the collective 
    communication routines that use the default group!  

**** Hear, hear. How many routines do we need anyway? Delete my
**** suggestion.

10) If I've got the points above right, inter-group communication seems to be 
    no problem with this proposal.  Everything is converted into a globally 
    unique PID.  

**** Right.

11)  Clarification:  
>    2) Processes are addressed by their rank within the parallel task.
> This global rank is fixed and assigned in an implementation-defined way.
    What do you mean by "parallel task"?  Is there only one?  Is this 
    extensible to "more than one"?  (Seems like it could be as long as 
    "global rank" == PID is globally unique for any process.)  A bit more 
    detail on how this would extend would be nice.  

> [ This is an area where MPI 2.0 could really break some new ground:
> define interaction between different parallel tasks, define creation
> and deletion of parallel tasks, ...]
    I think "one" parallel task in MPI 1.0 is definitely a good idea.  :-)

**** There are several options:
****     1) There exists one parallel task (collection of processes).
****        In this case processes can be addressed by rank within the task.
****     2) There exists more than one parallel task. Now we open up
****        a Pandora's box of options: can a process belong to more than
****        one parallel task (yech), can groups cross task boundaries
****        (yech**2). If the answer to both these questions is no, then
****        I would support modifying everything so that processes are
****        addressed by (parallel-task-id, rank). But this significantly
****        extends our work.

**** I had a hard time with this one -- am pulled both ways.

12)  Suggestion:  
>    4) Groups have an implicit topology, defined by the ordering of the
> elements. Any other ordering can be defined by constructing a new
> group with the same elements in the new order. There is no need for
> any other topology function.
    It seems to me that having standard routines that produce "good" orderings 
    for a few common logical topologies is a good idea.  
> There must exist environment functions which obtain the topology of
> the global process assignment (hypercube, mesh, random network, ...)
    I think that this is more difficult than specifying a few "logical 
    topology" ordering routines.  Arguments?  :-)

**** What you mean by a logical topology ordering routine is (correct
**** me if I misinterpret) something that selects, for example a Gray
**** ordering or natural ordering for a group. The choice depends on
**** the underlying topology and the application and cannot be done
**** automatically. Suppose you have constructed a group and want to
**** impose Gray ordering on it. In this proposal you would compose
**** your group with a permutation group (where the permutation was
**** the Gray ordering), creating thus a new group with the required
**** order. 

**** The implementation knows what the global topology is. A routine
**** like the following could be easily implemented (I think) to return
**** this information:
****
****   char * MPI_global_topology()
****
**** which in various implementations could return a string containing
**** something like
****
****    "N 564"      -- a random network with 564 processes.
****    "H 5"        -- a 5 dimensional hypercube.
****    "R 16 13"    -- a 16 by 13 mesh.
****
**** or generally
****    "topology-class parameter ..."
****
**** I don't anticipate very many topology classes.

(from James Cownie's email:)

It woudl be really nice if the could be kept separate. Unfortunately
they interact because 

1) the context needs to be agreed by a set of processors, so context
creation is naturally a group operation

**** In this proposal contexts are global quantities agreed to by
**** all processes. Also, contexts are a scarce and therefore limited
**** resource. I see no problem in simply creating them all at process
**** startup.

**** If we insist that contexts do need to be "created" before being
**** used, and if we accept the model (in this proposal) that a context
**** is just an integer, then there is no problem with implementing
**** a routine
****    context = MPI_get_context()
**** which tells MPI internally that this process is now willing to
**** send and receive messages with the specified context value. Such
**** a routine could be implemented with other point-to-point routines
**** which used one preexisting context (MPI_INTERNAL_CONTEXT).

2) if collective operations are built on point to point they need a
context to remove the ambiguity, and to work safely.

**** I agree, and my proposal states this. I would feel badly about
**** any proposal where collective communications could not be built
**** on top of point to point.

(the end)