Subject: A new proposal for context and groups.

From: [email-masked] (Mark P. Sears)
Date: Mon, 22 Mar 93 10:30:02 -0700

Proposal VI
Mark P. Sears
Sandia National Laboratories

The following proposal for context and group definitions is
intended to fill a gap in Tony Skjellum's list. It is most
closely related to Rik Littlefield's proposal V. The main
difference is that in my proposal, context and groups are
completely orthogonal, both in purpose and function. There are
a number of advantages to this proposal:

  1) The meanings of context and group are simple and it is
easy to see how they can be implemented quickly and efficiently.
The proposal is also free of chicken vs. egg problems.

  2) MPI 1.0 can be closed at the point-to-point level without any
reference to groups or group operations. We might actually
finish on time.

  3) Other proposals which combine aspects of context and group
as defined here could be layered on top of this proposal, but
not vice versa. Indeed, some of these proposals are very different
from each other and it is not clear which is the best.

  4) Elsewhere in MPI we have agreed to define low level
layers on which higher level stuff can be built. This proposal
follows that line of reasoning.

  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.

   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.

To summarize, in this proposal:

   1) The purpose of context is to allow different software modules
to maintain independence by allowing independence of tag
spaces. A context is an integer-valued extension to the tag field
which must match exactly for both sender and receiver. Allocation
and deallocation of contexts must occur globally and synchronously.
Two predefined contexts exist, one for internal use by MPI and one
a free-for-all context for application programs. 

   2) Processes are addressed by their rank within the parallel task.
This global rank is fixed and assigned in an implementation-defined way.
There must exist environment functions which obtain the topology of
the global process assignment (hypercube, mesh, random network, ...)

[ 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, ...]

   3) The purpose of groups is to allow the management of
subsets of processes in a parallel task. A group is defined
simply as an ordered set of unique integers (the elements). Two
groups are functionally the same if they define the same ordered set.
Groups have no associated context, default or otherwise. They are also free
of state. Groups are defined locally by construction, and have no
global meaning. A group can be passed from one process to another
by passing the information needed to construct it. A process is
a member of a group if its global rank is an element of the group.

   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.

   5) Any group implementation must define at least the following functions:

      order(group)               -- Number of elements in the group.
      range(group)               -- Upper limit on elements. Lower limit is
                                    always zero.
      iselement(group, element)  -- Predicate to determine if element
                                     is in a group.
      rank(group, element)       -- Compute rank of element.
      element(group, rank)       -- Compute element given rank.

  Some other proposals have scamped on the need for being able to
compute the rank of an element or the predicate defining whether
something is even an element of the group.

   Using these functions, it is easy to construct a minimum spanning
tree or set of binary exchanges for all of the interesting collective
communication functions, for any group. This information could be cached
with the local group definition.

  There is no reason to disallow user-defined groups (e.g. dynamic
groups).

  Note that since groups are ordered, the previous and next elements
are easily computed using the rank and element functions.

   6) MPI collective communication functions which operate on subsets
of processors use groups to define the subset of interest, and must
be called with the same context, tags(s) and group, by at least all
processes which are members of the group. Note that with this definition
of group it is the responsibilty of the caller to provide context and
tags. Two (or more) such communication functions are guaranteed to complete
if they are called in the same order on all processes which are members of
both groups (this condition is less stringent for multithreaded
environments). Otherwise the program is erroneous.

---

From: [email-masked] (Tom Henderson)
Date: Fri, 26 Mar 93 11:09:35 MST

Hi all,

A while back, Mark Sears wrote the beginnings of a "Proposal VI":  

> completely orthogonal, both in purpose and function...  
> [remainder deleted...]

Any particular reason why this proposal hasn't been pushed any farther?  
(Maybe no one has time to do it??  I'm not volunteering!  :-)  

I think "Proposal VI" would fit into Lyndon's summary like this:  

> In Proposal I CONTEXT and GROUP are identical concepts and are not
> distinguished.
> 
> In Proposal III CONTEXT is a lower degree concept that GROUP. The
> GROUP concept inherits aspects of the CONTEXT concept.
> 
> In Proposal VII CONTEXT is a higher concept than GROUP. The CONTEXT
> concept inherits aspects of the GROUP concept.

In Proposal VI CONTEXT and GROUP are othogonal and unrelated.  

Is this worth pursuing?  

Tom (I'm STILL reading the proposals...  :-) Henderson 
NOAA Forecast Systems Laboratory
[email-masked]