From: "Marc Snir" <[email-masked]>
Date: Tue, 7 Sep 93 18:30:42 EDT

\include{chapter-head}
% Context chapter.
%
% Version of September 6, 1993
% Lyndon Clarke, Tom Henderson, Mark Sears, Anthony Skjellum,
% Marc Snir, Rik Littlefield, Jim Cownie
%
% [now uses \funcdef, \const, \func per Steve Otto]
%
% Non-portable lines...
\setcounter{chapter}{2}
\newcommand{\dross}[1]{}
%
%
% ********************************************************************
% ********************************************************************
% ********************************************************************
% ********************************************************************

% Rest goes to Steve Otto each time...
\chapter{Groups, Contexts, and Communicators}
\label{sec:context}
\label{chap:context}

\section{Introduction}

This section defines the concepts of group, context, and communicator
and discuss operations on those.

Each communication operation (point-to-point or collective) accepts as parameter
a {\bf communicator}.  This parameter specifies the ``universe'' of the
communication operation.
The current practice in many communication libraries is that there is a
a unique, predefined communication universe
that includes all processes available when the library is initiated; the
processes are assigned consecutive ranks.
Participants in a point-to-point communication  are identified by their
rank; a collective communication (such as broadcast) involves all processes.
This practice can
be followed in MPI by using the predefined communicator {\tt MPI\_COMM\_WORLD}.
Users that are satisfied with such practice can plug in {\tt
MPI\_COMM\_WORLD} wherever a communicator argument is required, and ignore
the rest of this section.

User defined communicators allow to create multiple distinct
``universes'' of noninterfering communication.
Such universe may include only a subset of the processes.
It often desireable to execute a collective operation
on a subset of processes, without involving in any way the remaining processes.
The same holds true of user defined parallel procedures.
Quite often a parallel program is built by composing several parallel modules
({\em e.g.}, a numerical solver, and a graphic display module).
It is highly desirable that processes executing a parallel procedure
use a ``virtual process name space'' local to the invocation.  Thus,
the code of the parallel procedure will look identical, irrespective
of the absolute addresses of the executing processes.  This is done by using
rank within the subset to address local communication.
Support of a virtual name space for each module will
allow for the composition of modules that were developed separately
without changing all message passing calls within each module.

Distinct communication universes
may be needed even within the same set of processes, in
order to allow predictable behavior in subprograms, and to allow dynamicism in
message usage that cannot be reasonably anticipated or managed.
Normally, a parallel procedure is written so that all messages
produced during its execution are also consumed by the processes that
execute the parallel procedure.  However, if one parallel procedure calls
another, then it might be desirable to allow such call to proceed
while messages are pending (the messages will be consumed by the
procedure after the call returns).  In such case, a new communication
``universe'' is needed for the called parallel procedure, even if the
transfer of control is synchronized.

Communicators bring together the concepts of
process group and communication context.  A {\bf group} is an ordered set of
processes.  Processes in a group are assigned consecutive ranks, starting from
zero.  A collective communication involves all processes in the group
indentified by the communicator parameter.  It is expected that
parallel
libraries will be built to accept a communicator as parameter.  In a point to
point communication,
the communicator parameter provides the translation from virtual process names,
which are ranks within the group, into absolute addresses.
A {\bf context} is a mechanism to partition the message-passing space into
separate, noninterfering universes.  Specifically, a message sent in
one context can only be received in the same context.

A communicator has to be defined in a consistent manner at all processes in the
communicator group before it is used.  To achieve this, operations that
define
communicators are collective:  they are executed by all processes in the group
that contains the new group,
and all processes provide matching parameters;  furthermore, all
processes execute the calls in the same order  (see Section~\ref{chap:coll} for
a more precise definition).

The definition of a communicator consists of two suboperations:  The new
communication group is defined and this group is bound to a context.
MPI allows groups to be defined and manipulated locally.  They are
represented by explicit, opaque group objects.  Contexts do not have
explicit representation:  they manifest themselves only as a binding
aof a group into a communicator.

Dynamic communicator creation at parallel
procedure call boundaries lead to a clean, modular programming styel.  Yet,
users may be reluctant to avail themselves of this facility if an expensive
collective communication is required for each communicator creation.
In order to alleviate this problem, we allow local creation of
communicators.  The user has to follow the same calling convention as for
collective calls; there is no change in semantics and performance is gained at
the expense of error checking.
 Additional
operations are available for (pre)allocating contexts.

The discussion has dealt so far with {\bf intra-communication}: communication
within a group.  MPI also supports {\bf inter-communication}:
communication across groups.  When an application is built by composing several
parallel modules, it is convenient to allow one module to communicate with the
other using local ranks within the second module for addressing.  This is
especially convenient in a client-server computing paradigm, where either
client or server are parallel.   The support of inter-communication also
provides a mechanism for the extension of MPI to a dynamic model where not all
processes are preallocated at initialization time.  In such situation, it
becomes necessary to support communication across ``universes''.
Inter-communication is supported by {\bf inter-communicators}.  These bind
together two groups and a context that is shared by both groups.
MPI provides mechanisms for creating and manipulating inter-communicators.
They are used in point-to-point communication
in the same manner as regular {\bf
intra-communicators}.   Users that do not need inter-communication in their
applications can ignore this extension.

Finally, a general mechanism is available for attaching additional
attributes to communicators.  This additional information is used, for example,
to carry information on topology (see Section~\ref{chap:topol}).
This general caching mechanism can be used to build more complex, collective
objects.

\section{Basic Concepts}

\subsection{Groups}
A {\bf group} is an ordered set of process identifiers (henceforth
processes); process identifiers are implementation dependent.
Each process in a group is associated with an
integer {\bf rank}, starting from zero.

Groups are represented by opaque {\bf group objects},
and hence cannot be directly transferred from one
process to another.  Such group can be though as of an unbound communicator; a
communicator is created by binding a group (or two groups, for
inter-communicators) to a context.

\implement{
A group may be represented by a virtual-to-real process address translation
table.  Each communicator object would have a pointer to such table.

}

\subsection{Contexts}
A {\bf context} is the MPI mechanism for partitioning communication
space.  A defining property of a context is that a message sent in a
context cannot be received in another context.
Only one communicator in a process may bind the same context.
Contexts are not explicit MPI objects; they appear only as bindings of
groups into communicators.
For int\-ra-com\-mun\-i\-cat\-ion, a context is
essentially a tag (or tags) needed to make a communicator safe for
point-to-point and MPI-defined collective communication.
Contexts have additional attributes for
int\-er-com\-mun\-i\-cat\-ion,
to be discussed below.

\implement{
A possible implementation is for a context to be a label attached to
messages and matched on receive.  Each intra-communicator stores the value of
that label.  Since collective communication traffic has to
be kept separate from point-to-point traffic, a pair of labels would actually
be needed, if collective communication is implemented on top of point to point.
In inter-communication, it is more convenient to use two labels, one used by
group A to send and group B to receive, and the second used by group B to send
and group A to receive.   Since contexts are not explicit objects, other
implementations are possible.

}

\subsection{Communicators}

Communicators bring
together the concepts of group and context. Furthermore, to support
implementation-specific optimizations, and virtual topologies, they
``cache'' additional information opaquely.  The source and
destination of a message is identified by the rank of that process
within the group.
For collective
communication, the communicator specifies the set of processes that
participate in the collective operation and their order, when significant.
Thus, the communicator
restricts the ``spatial'' scope of communication, and provides local
process addressing.

Communicators are represented by opaque {\bf communicator objects},
and hence cannot be directly transferred from one
process to another.

% \paragraph{Raison d'\^{e}tre for Contexts and Communicators}
% Within a communicator, one or more contexts are cached.
% We want to make it possible for libraries quickly to achieve
% additional safe communication space without MPI-communicator-based
% synchronization.  The only way to do this is to provide a means to
% preallocate many contexts, and bind them locally, as needed.  This
% choice weakens the overall, inherent ``safety'' of MPI, if programmed
% in this way, but provides added performance which library designers
% will demand.  We are convinced that the means we have chosen provides
% a good compromise between efficiency and safety.

\subsection{Predefined Communicators}
\label{sec:predef-comms}
Initial communicators defined once \func{ MPI\_INIT} has
been called are as follows:
\begin{itemize}

\item \const{ MPI\_COMM\_WORLD},~~~A communicator of all processes the local
process can communicate with after initialization (itself included).

\item \const{ MPI\_COMM\_PEER},~~~A communicator of all processes the local
process can communicate with after initialization, excluding a ``host'' process
(if any).
In the absence of a host process this communicator will have the same group
as \const{MPI\_COMM\_WORLD}, but will still contain a different context.

\end{itemize}

These two communicators are available on any MPI implementation.  Other
implementation dependent predefined communicators may also be provided.

In a static MPI implementation all processes that participate in the
computation
are available after MPI is initialized.  In such case, \const{MPI\_COMM\_WORLD}
is a communicator of all processes available for the computation; this
communicator has the same value at all processes.
In an implementation of MPI
where processes can dynamically join an MPI execution it may be the
case that a process starts an MPI computation without having access to
all other
processes.
In such situation, \const{MPI\_COMM\_WORLD} is a communicator of all
processes the joining process can start communicating with;
\const{MPI\_COMM\_WORLD} may have at the same time different values at different processes.

MPI implementations are required to provide these two communicators.  They
cannot be deallocated during the computation. The
groups corresponding to these communicators do not appear as pre-defined
constants, but they may be accessed using \func{MPI\_COMM\_GROUP} (see
below).
MPI does not specify
the correspondance between the process rank in
\const{MPI\_COMM\_WORLD} and its
(machine-dependent) absolute address.  Also, MPI does not specify the function
of the host process.

\discuss{

A recommended implementation for dynamic process spawning is to add a function
\mpifunc{MPI\_SPAWN(text, n, newcomm,...)} which spawns {\tt n} copies of {\tt
text}.  The parent is returned in {\tt newcomm} a communicator for itself and
the new children;  each child is started with \const{MPI\_COMM\_WORLD} set to
that same communicator, and \const{MPI\_COMM\_PEER} set to a communicator for
all sibblings (e.g. the parent is a ``local host'').  An inter or
intra-communicator including the new
children
and previous processes can new be built explicitly, using the parent as
a bridge.   Generally, a new group of processes can merge into an existing
group, provided these two groups have a nonempty intersection, or both
have a nonempty intersection with a third group.

I changed from ``ALL'' to ``WORLD'' in order to make more sense in the case
where multiple ``worlds'' exist, e.g. dynamic process spawning.
}

\discuss{

In the host process, if there is one, what should
\const{MPI\_COMM\_PEER} be? There are two consistent possibilities: a
null communicator; a communicator in which the group contains only the
host process.

Is the host, if there is one, at a fixed rank in \const{MPI\_COMM\_WORLD}?
Should that be zero
or n-1?  The first choice seems more natural, but the second choice allow slave
processes to have the same rank in \const{MPI\_COMM\_WORLD} and
\const{MPI\_COMM\_PEER}

}

\section{Group Management}

This section describes the manipulation of process groups in MPI.  These
operations are local and their execution do not require interprocess
communication.

\subsection{Group Accessors}

\begin{funcdef}{MPI\_GROUP\_SIZE(group, size)}
\funcarg{\IN}{ group}{ handle to group object.}
\funcarg{\OUT}{ size}{ is the integer number of processes in the group. }
\end{funcdef}

\begin{funcdef}{MPI\_GROUP\_RANK(group, rank)}
\funcarg{\IN}{ group}{ handle to group object.}
\funcarg{\OUT}{ rank}{ is the integer rank of the calling process in
group, or \const{ MPI\_UNDEFINED} if the process is not a member.}
\end{funcdef}

\begin{funcdef}{MPI\_TRANSLATE\_RANKS (group\_a, n, ranks\_a, group\_b,
ranks\_b)}
\funcarg{\IN}{ group\_a}{ handle to group object ``A''}
\funcarg{\IN}{ n}{ number of ranks in \mpiarg{ ranks\_a} array}
\funcarg{\IN}{ ranks\_a}{ array of zero or more valid ranks in group ``A''}
\funcarg{\IN}{ group\_b}{ handle to group object ``B''}
\funcarg{\OUT}{ ranks\_b}{ array of corresponding ranks in group ``B,''
\const{ MPI\_UNDEFINED} when no correspondence exists.}
\end{funcdef}

\discuss{

{\bf (language binding issue)}  We may need multiple ``{\tt
MPI\_UNDEFINED}'', one for each datatype that can be undefined: undefined
integer, undefined communication handle, etc.

}

\subsection{Group Constructors}

These functions allow to construct new groups from existing groups.  These are
local operations, and distinct groups may be defined at different processes; a
process may also define a group that does not include it.  Consistent
definitions are required when groups are used as arguments in communicator
building functions.

MPI does not provide a mechanism to build a group from scratch, but only from
other, previously defined groups.  The base case for this recursion is
provided by the groups associated with the initial communicators {\tt
MPI\_COMM\_WORLD} and {\tt MPI\_COMM\_PEER}.

\begin{funcdef}{MPI\_GROUP\_DUP(group, new\_group)}
\funcarg{\IN}{ group}{ extant group object handle}
\funcarg{\OUT}{ new\_group}{ new group object handle}
\end{funcdef}
\func{ MPI\_GROUP\_DUP} duplicates a group with all its cached
information.

\discuss{

Do we need caching for groups?  Or is it sufficient to have it for
communicators?
}

\implement{

Since groups cannot be modified, then no copying of the group structure is
actually needed; one only needs keep count of active references.   If
information is cached, one may use
``copy on write'' for the cached information,
if updates are unfrequent.
}

The remaining group constructors do not carry any cached information into the
newly created group.

\begin{funcdef}{MPI\_GROUP\_UNION(group1, group2, group\_out)}
\funcarg{\IN}{ group1}{ first group object handle}
\funcarg{\IN}{ group2}{ second group object handle}
\funcarg{\OUT}{ group\_out}{ group object handle}
\end{funcdef}

\begin{funcdef}{MPI\_GROUP\_INTERSECTION(group1, group2, group\_out)}
\funcarg{\IN}{ group1}{ first group object handle}
\funcarg{\IN}{ group2}{ second group object handle}
\funcarg{\OUT}{ group\_out}{ group object handle}
\end{funcdef}

\begin{funcdef}{MPI\_GROUP\_DIFFERENCE(group1, group2, group\_out)}
\funcarg{\IN}{ group1}{ first group object handle}
\funcarg{\IN}{ group2}{ second group object handle}
\funcarg{\OUT}{ group\_out}{ group object handle}
\end{funcdef}

The set-like operations are defined as follows:
\begin{description}
\item[union] All elements of the first group (\mpiarg{group1}), followed by
all elements of second group (\mpiarg{group2}) not in first
\item[intersect] all elements of the first group which are also
in the second group, ordered as in first group.
\item[difference] all elements of the first group which are not
in the second group, ordered as in the first group.
\end{description}
Note that for these operations the order of processes in the output
group is determined first by order in the first group (if possible)
and then by order in the second group (if necessary).  Neither union nor
intersection are commutative, but both are associative.

\discuss {

Do we know why we want these operations?
}

\begin{funcdef}{MPI\_GROUP\_INCL(group, n, ranks, new\_group)}
\funcarg{\IN}{ group}{ handle to group object}
\funcarg{\IN}{ n}{ number of elements in array ranks
(and size of \mpiarg{ new\_group})}
\funcarg{\IN}{ ranks}{ array of integer ranks in \mpiarg{group} to appear
in \mpiarg{new\_group}.}
\funcarg{\OUT}{ new\_group}{ new group derived from above, in the order
defined by \mpiarg{ ranks}.}
\end{funcdef}
The function \func{MPI\_GROUP\_INCL} creates a group {\tt
new\_group} of size {\tt n} which is a subgroup of {\tt old\_group} such that
the process with rank {\tt i} in {\tt new\_group} is the process with rank
{\tt ranks[i]} in {\tt old\_group}.
Each of the {\tt n} elements of {\tt ranks} must be a valid
rank in {\tt group} and all elements must be distinct, else the
program is erroneous.
If {\tt n=0}, then \mpiarg{new\_group} is empty.
This function can be used to reorder the elements of a group.

\begin{funcdef}{MPI\_GROUP\_EXCL(group, n, ranks, new\_group)}
\funcarg{\IN}{ group}{ handle to group object}
\funcarg{\IN}{ n}{ number of elements in array ranks
(and size of \mpiarg{ new\_group})}
\funcarg{\IN}{ ranks}{ array of integer ranks in \mpiarg{group} not to appear
in \mpiarg{new\_group}}
\funcarg{\OUT}{ new\_group}{ new group derived from above, preserving the
order defined by \mpiarg{ ranks}.}
\end{funcdef}
The function \func{MPI\_GROUP\_EXCL} creates a group {\tt
new\_group} which is a subgroup of {\tt old\_group} such that
{\tt new\_group} contains all process in {\tt old\_group} except
the {\tt n} processes with ranks {\tt ranks[i], i = 0, ..., n - 1}.
The ordering of processes in {\tt new\_group} is identical to the ordering
in {\tt old\_group}.
Each of the {\tt n} elements of {\tt ranks} must be a valid
rank in {\tt old\_group} and all elements must be distinct, else the
program is erroneous.
If {\tt n=0}, then \mpiarg{new\_group} is identical to \mpiarg{group}.

\begin{funcdef}{MPI\_GROUP\_RANGE\_INCL(group, n, ranges, new\_group)}
\funcarg{\IN}{ group}{ handle to group object}
\funcarg{\IN}{ n}{ number of triplets in array \mpiarg{ ranges}. }
\funcarg{\IN}{ ranges}{ a one-dimensional array of integer triplets, of the
form (first rank, last rank, stride), to be included
in the output group \mpiarg{new\_group}. }
\funcarg{\OUT}{ new\_group}{ new group derived from above, in the
order defined by \mpiarg{ ranges}. }
\end{funcdef}

If \mpiarg{ ranges} consist of the triplets
\[
(first_1 , last_1, stride_1) , ..., (first_n, last_n, stride_n)
\]
then the new group consists of the processes in {\tt group} with ranks
\[
first_1 , first_1 + stride_1 , ... , first_1 + \left\lfloor \frac{last_1 -
first_1}{stride_1} \right\rfloor stride_1 , ...
\]
\[
first_n , first_n + stride_n , ... , first_n + \left\lfloor \frac{last_n -
first_n}{stride_n} \right\rfloor stride_n .
\]

Each computed rank must be a valid
rank in {\tt group} and all computed ranks must be distinct, else the
program is erroneous.
Note that we may have $first_i > last_i$, and $stride_i$ may be negative, but
cannot be zero.

The functionality of this routine is specified to be equivalent to
expanding the array of ranges to an array of the included ranks and
passing the resulting array of ranks and other arguments to
\mpifunc{MPI\_GROUP\_INCL}.  A call to \mpifunc{MPI\_GROUP\_INCL} is
equivalent to a call to
\mpifunc{MPI\_GROUP\_RANGE\_INCL} with each rank {\tt i}
in \mpiarg{ranks} replaced by the triplet {\tt (i,i,1)} in the argument {\tt
ranges}.

\begin{funcdef}{MPI\_GROUP\_RANGE\_EXCL(group, n, ranges, new\_group)}
\funcarg{\IN}{ group}{ handle to group object}
\funcarg{\IN}{ n}{ number of elements in array ranks
(and size of \mpiarg{ new\_group}) }
\funcarg{\IN}{ ranges}{ a one-dimensional
array of integer triplets of the
form (first rank, last rank, stride), to be excluded
from the output group \mpiarg{new\_group}. }
\funcarg{\OUT}{ new\_group}{ new group derived from above, preserving the
order in \mpiarg{ group}.}
\end{funcdef}

Each computed rank must be a valid
rank in {\tt group} and all computed ranks must be distinct, else the
program is erroneous.

The functionality of this routine is specified to be equivalent to
expanding the array of ranges to an array of the excluded ranks and
passing the resulting array of ranks and other arguments to
\mpifunc{MPI\_GROUP\_EXCL}. A call to \mpifunc{MPI\_GROUP\_EXCL} is
equivalent to a call to \mpifunc{MPI\_GROUP\_RANGE\_EXCL} with each rank {\tt
i} in \mpiarg{ranks} replaced by the triplet {\tt (i,i,1)} in the argument {\tt
ranges}.

\discuss{
Do we need all these group constructors?  Do we need more?

Note: the range operations do not explicitly enumerate ranks, and therefore
are more scalable if implemented efficiently\ldots}

\subsection{Group Destructors}

\begin{funcdef}{MPI\_GROUP\_FREE(group)}
\funcarg{\INOUT}{ group}{ handle to group}
\end{funcdef}
This operation marks a group object for deallocation.
The handle {\tt group} is set to null by the call.  The group object is actually
deallocated only if there are no other active references to it.  If a group has
been duplicated, or has been bound to communicators, then the user has to free
all ``copies'' of the group.
When a group is freed then all information cached with it becomes unavailable.

\change

\discuss {

I changed \func{MPI\_GROUP\_FREE}
to be consistent with other free functions: FREE marks the object
for deallocation;
the object is deallocated only when there are no other pending
references to it (reference count mechanism).
}

\implement{

One can keep a reference count that is incremented for each call to
\func{MPI\_GROUP\_DUP}, \func{MPI\_COMM\_MAKE} and \func{MPI\_COMM\_DUP}, and
and
decremented for each call to \func{MPI\_GROUP\_FREE} or \func{MPI\_COMM\_FREE};
the group object is deallocated when the reference count drops to zero.

}

\discuss{

MPI does not keep count of references to an opaque MPI object that are created
by assigning
to one handle the value of another, or are lost when a handle variable is
deallocated (e.g., at procedure exit).  In the first case, a call to
\func{MPI\_GROUP\_FREE} may leave a dangling reference; in the second case an
opaque MPI object may be left with no handle to it, and no possibility of
deallocating it.  It is the user responsibility to avoid these situations.  MPI
keeps track only of changes in the number of active references to the MPI
object that are due to explicit MPI calls.

(May want to move this discussion to chapter 2.)
}

\section{Communicator Management}

These section describes the manipulation of communicators in MPI.  Operations
that access communicators are local and their execution does not require
interprocess communication.  Operations that create communicators are collective
and may require interprocess communication.  Mechanisms are provided to avoid in
many cases the need for communication for these collective operations as well.

\subsection{Communicator Accessors}

The following are all local operations.

\begin{funcdef}{MPI\_COMM\_SIZE(comm, size)}
\funcarg{\IN}{ comm}{ handle to communicator object.}
\funcarg{\OUT}{ size}{ is the integer number of processes in the group of \mpiarg{ comm}.}
\end{funcdef}

\begin{funcdef}{MPI\_COMM\_RANK(comm, rank)}
\funcarg{\IN}{ comm}{ handle to communicator object.}
\funcarg{\OUT}{ rank}{ is the integer rank of the calling process in
group of \mpiarg{ comm}, or \const{ MPI\_UNDEFINED} if the process is not a member.}
\end{funcdef}

\begin{funcdef}{MPI\_COMM\_GROUP(comm, group)}
\funcarg{\IN}{ comm}{ communicator object handle}
\funcarg{\OUT}{ group}{ group object handle corresponding to {\tt comm}}
\end{funcdef}

\subsection{Communicator Constructors}

These functions are collective calls that are invoked by all processes in the
group associated with {\tt comm}.

\discuss{

There is a chicken-and-egg aspect to MPI in that a communicator is needed to
create a new communicator.  The
base case of this recursive process is provided by the predefined
communicators {\tt MPI\_COMM\_WORLD} and {\tt MPI\_COMM\_PEER},
which are defined outside MPI.

}

\begin{funcdef}{MPI\_COMM\_DUP(comm, new\_comm)}
\funcarg{\IN}{ comm}{ communicator object handle}
\funcarg{\OUT}{ new\_comm}{ communicator object handle}
\end{funcdef}

Duplicates the existing communicator {\tt
comm} with all its cached information.  Returns in {\tt new\_comm} a new
communicator with the same group, same cached information, but a new context.

\implement{

One need not actually copy the group information, but only add a new reference
and increment the reference count.  Copy on write can be used for the cached
information.

}

\begin{funcdef}{MPI\_COMM\_MAKE(comm, group,
comm\_new)} \funcarg{\IN}{ comm}{ Communicator handle}
\funcarg{\IN}{group}{ Group which is a subset of the group of {\tt comm}}
\funcarg{\OUT}{ comm\_new}{ Handle to new communicator.}
\end{funcdef}

Creates a new communicator {\tt new\_comm} with communication group defined by
{\tt group} and a new context.
No cached information propagates from {\tt comm} to {\tt comm\_new}.
For processes in the group of {\tt comm} which are not in {\tt group},
these functions return {\tt comm\_new} as the null communicator
\const{MPI\_COMM\_NULL}.

The call
is erroneous if not all {\tt group} arguments have the same value, or if {\tt
group} is not a subset of the group associated with {\tt comm}.
Note that the call is executed by all processes in {\tt comm}, even if they do
not belong to the new group.

\discuss{

The need to have all processes in {\tt comm} execute the call will become
clearer in the next section, where we discuss mechanisms to avoid communication
in call that create new communicators;  this allows all the processes to mark
the allocated context as used.

}

\begin{funcdef}{MPI\_COMM\_SPLIT(comm, color, key, comm\_new)}
\funcarg{\IN}{comm}{Handle to existing communicator}
\funcarg{\IN}{color}{control of subset assignment (integer)}
\funcarg{\IN}{key}{ control of rank assigment (integer)}
\funcarg{\OUT}{ comm\_new}{ Handle to new communicator.}
\end{funcdef}

Partition the group associated with {\tt comm} into disjoint subgroups, one for
each value of {\tt color}.  Each subgroup contains all processes of the same
color.  Within each subgroup, the processes are ranked in the order defined by
the value of the parameter {\tt key}, with ties broken according to their rank
in the old group.  A new communicator is created for each subgroup and returned
in {\tt comm\_new}.  A process may supply the color value {\tt MPI\_UNDEFINED},
in which case {\tt comm\_new} returns the null communicator {\tt
MPI\_COMM\_NULL}.  This is a collective call, but each process can provide
different values for {\tt color} and {\tt key}.

A call to \mpifunc{MPI\_COMM\_MAKE(comm, group, new\_comm)} is equivalent to a
call to \mpifunc{MPI\_COMM\_SPLIT(comm, color, key, new\_comm)}, where all
members of {\tt group} provide {\tt color = 0} and {\tt key} = rank in
{\tt group}, and  all processes that are not members of {\tt group} provide
{\tt color = MPI\_UNDEFINED}.
The function \mpifunc{MPI\_COMM\_SPLIT} allow more generally to partition the
original group into one or many subgroups, and reorder each subgroup.

\discuss{New Function below}

\change

\begin{funcdef}{MPI\_COMM\_MERGE(comm, leader, remote\_comm, new\_comm)}
\funcarg{\IN}{comm}{ handle to local communicator}
\funcarg{\IN}{leader}{ rank of shared process in \mpiarg{comm}}
\funcarg{\IN}{remote\_comm}{ handle to remote communicator}
\funcarg{\OUT}{new\_comm}{ handle to new communicator}
\end{funcdef}

Create a new communicator by merging the groups of two existing communicators.
Unlike all previous functions, this function does not require a preexisting
communicator
that encompasses the newly created group.   Rather, it only requires
that both groups share a process, and that the local rank of this shared
process is known within each group.
This function is
collective within each of the merged groups and within each group all
processes
supply the same value for {\tt leader} (different values may be supplied by the
two groups). The parameter {\tt
remote\_comm} is significant only at the shared process.
The group of the resulting communicator returned by {\tt new\_comm} contains all
the processes in {\tt comm}, followed by all processes in {\tt remote\_comm}
that are not in {\tt comm}.  (Thus, the order in which the two groups are
merged is determined by the order of the two arguments {\tt comm} and {\tt
remote\_comm} at the leader process.)

Application:  Consider a system where new processes can be created dynamically.
When a process spawns a set of new processes then a communicator is created for
the parent and the newly spawned children.  This new group can join the old
group of {\tt MPI\_COMM\_WORLD} using a call to {\tt MPI\_COMM\_MERGE} with the
parent as the leader of the merge.

\implement{

This merge requires a broadcast from the shared process within each subgroup.
}

\discuss{

This function bears a nonaccidental ressemblance to the inter-communicator
creation function \func{MPI\_INTERCOMM\_MAKE}.  It was simplified to use only
one leader, rather than two, no bridge communicator, and to create only one
output communicator.   Alternatives:

(i)  Keep this function consistent with \func{MPI\_INTERCOMM\_MAKE} (two
leaders, a bridge communicator).  The function above becomes a
special case of this more general construction.

(ii)  Introduce a function that makes an inter-communicator into an
intra-communicator by taking the union of both groups.   One still needs a
leader (or two) to break the symmetry between the two groups,
and one introduces
additional communication and a heavier construction.
}

\subsection{Communicator Destructors}

\begin{funcdef}{MPI\_COMM\_FREE(comm)}
\funcarg{\INOUT}{ comm}{ handle to communicator to be destroyed.}
\end{funcdef}
This call marks the communication object for deallocation.  The handle
is set to null.  The object is actually deallocated only if there are no
other active references to it.  The associated group may also be deallocated, if
there are no active references to it.  It is the user responsibility to free
each copy of a communicator object.

\change

\discuss {
Changed, here too, to a reference count mechanism
}

\implement{

A reference count mechanism can be used: the reference count is
incremented by each call to \func{MPI\_COMM\_DUP}, and decremented by each
call to \func{MPI\_COMM\_FREE}.  The object is deallocated when the count
reaches zero.

}

\section{Context Management}

The creation of a new communicator requires agreement among the
members of the communicator group on the context associated with the new
communicator.  This requires collective communication within a group that
contains the new communicator group, using a preexisting communicator.  MPI
provides a mechanism to amortize the cost of one such collective communication
over the creation of multiple communicators: one collective call can be used to
allocate
multiple contexts, and cache them with the communicator used in the call.
Subsequent calls with this same communicator as argument can use these cached
contexts to generate new communicators.  The effect of these subsequent calls is
as if a collective agreement protocol was run by the members of the communicator
group; however, communication was not required.

\subsection{Context Allocation}

\begin{funcdef}{MPI\_CONTEXTS\_ALLOC(comm, n)}
\funcarg{\IN}{ comm}{a communicator}
\funcarg{\IN}{ n}{ number of contexts to allocate}
\end{funcdef}
This function allocates {\tt n } contexts, which are unique within
the group bound to the communicator {\tt comm}, and stores them in the
unused context store of {\tt comm}.  This is a collective function
that is invoked by all processes in the group of {\tt comm}
and all processes provide the same value for {\tt n}.

\subsection{Context Deallocation}

\begin{funcdef}{MPI\_CONTEXTS\_FREE(comm, n)}
\funcarg{\IN}{comm} a communicator
\funcarg{\IN}{ n}{number of contexts to free}
\end{funcdef}
This function frees (i.e., returns to the MPI system) {\tt n}
contexts from the unused context store of the communicator {\tt comm},
which were previously allocated by calling \func{ MPI\_CONTEXTS\_ALLOC}
(below).  If less than {\tt n} contexts are available, then all contexts are
freed.  The function call is collective in {\tt comm}.

\discuss{

Do we want to return the number of contexts actually freed?

}

\subsection{Context Accessor}

\begin{funcdef}{MPI\_COMM\_CONTEXTS(comm, n)}
\funcarg{\IN}{ comm}{ handle to communicator object.}
\funcarg{\OUT}{ n}{ the number of contexts available in the unused context
store associated with {\tt comm}}
\end{funcdef}

This is a local call.

\subsection{Use of Preallocated Contexts}

Allocation and deallocation of contexts do not change the semantics of
communicator management functions if these are used correctly -- only their
performance.  If \func{MPI\_COMM\_DUP} or \func{MPI\_COMM\_MAKE} are called
with parameter {\tt comm}, and an unused context is available in the context
store of {\tt comm}, then the new communicator may be created with no
communication, binding this unused context.  If no context is available, then a
global communication will occur, in order to allocate the new context.
Since context allocation and deallocation are collective functions and so
are the communicator allocation and deallocation functions, then all processes
in the group associated with {\tt comm} have the same number of unused contexts
allocated to {\tt comm}; they either all proceed to communicate or all perform
the allocation locally.  The operation \func{MPI\_COMM\_FREE} does not
require communication; the operations \func{MPI\_COMM\_SPLIT} and
\func{MPI\_COMM\_MERGE} always require
collective communication.

The use of preallocated contexts may affect the behavior
of erroneous programs: errors that cause deadlock or can be easily detected when
communicator creation is a synchronizing call may run undetected when a
preallocated context is used locally.

An MPI implementation may actually allocate more or less contexts than required
by the user by calls to \func{MPI\_CONTEXTS\_ALLOC}.  At one extreme, one may
use an implementation where an esentially unbound number of contexts is
preallocated whenever a group is created; the operations
\func{MPI\_CONTEXTS\_ALLOC} and \func{MPI\_CONTEXTS\_FREE} are noops, and all
communicator creation and destruction operations are executed locally
(\func{MPI\_COMM\_SPLIT} and \func{MPI\_COMM\_MERGE} excepted)
and are not synchronizing.  At the other
extreme, one may never preallocate contexts, in which case, the operations
\func{MPI\_CONTEXTS\_ALLOC} and \func{MPI\_CONTEXTS\_FREE} are again noops, and
\func{MPI\_COMM\_DUP} and \func{MPI\_COMM\_MAKE} always
require global communication and are synchronizing.
As with all
collective operations, a program should be written
so that it works correctly whether the collective call is synchronizing or not.

The enquiry function ??? can be used to find out which mechanism is used for
context allocation.  MPI implementation may allow the user to control the
context allocation mechanism, e.g. to use synchronizing communicator creation in
debug mode, and nonsycnhronizing communicator creation in run mode.

\change

\discuss{

I left out the communicator making functions that are mandated to be local or
global, for several reasons:

(i) We made a similar decision w.r.t. collective communications (we do
not have a synchronizing and a nonsychronizing mode, as was proposed by Ho).

(ii) This would make implementation decisions on the number of preallocated
contexts visible to the application.
I feel this should be a performance issue,
not a correctness one.

(iii) We can always have a global switch (use / do not use synchronization or,
equivalently, preallocate / do not preallocate contexts).

(iv) We can use a barrier synchronization to get the effect of a
synchronizing operation.

}

\implement{

A communicator can be used for point-to-point communication as soon as the
communicator is created.  If communicator creation is nonsynchronizing, then a
process may receive a message sent with a newly allocated context before it has
allocated itself this context to a communicator (in case the sender runs ahead
of the receiver). However, since context preallocation is synchronizing, such
context must be already preallocated at the receiver.  The communication
subsystem should be built so that arriving messages that carry a context
preallocated at the receiver are put on hold (waiting for the receiver to bind
this context to a communicator, next executing a receive with this
communicator).  Messages arriving with a context that has not been preallocated
can be rejected as erroneous.

}

\discuss{

We miss a mechanism to allow a new communicator to inherit part of the pool of
unused contexts of its communicator parent (e.g., an additional parameter in
communicator creating functions).  Do we want it?

}

\section{Inter-Communication}

This section introduces the concept of int\-er-com\-mun\-i\-cat\-ion and
describes the portions of MPI that support it.  It describes support for
writing programs which contain user-level servers.  It also describes a
name service which simplifies writing programs containing
int\-er-com\-mun\-i\-cat\-ion.

All point-to-point communication described thus far has involved
communication between processes that are members of the same group.
This type of communication is called
``int\-ra-com\-mun\-i\-cat\-ion'' and the communicator used is called an
``intra-communicator.''

In modular and multi-disciplinary applications, different process
groups execute different modules and processes within different
modules communicate with one another in a pipeline or a more general
module graph.  In these applications the most natural way for a
process to specify a target process is by the rank of the target
process within the target group.  In applications that contain
internal user level servers, each server may be a process group that
provides services to one or more clients, and each client may be a
process group which uses the services of one or more servers.  In
these applications it is again most natural to specify the target
process by rank within the target group.  This type of communication
is called ``int\-er-com\-mun\-i\-cat\-ion'' and the communicator used is called an
``inter-communicator.''

An int\-er-com\-mun\-i\-cat\-ion operation is a point-to-point communication
between processes in different groups.  The group containing a process
that initiates an int\-er-com\-mun\-i\-cat\-ion operation is called the ``local
group,'' that is, the sender in a send and the receiver in a receive.
The group containing the target process is called the ``remote
group,'' that is, the receiver in a send and the sender in a receive.
As in int\-ra-com\-mun\-i\-cat\-ion, the target process is specified using a
\mpiarg{(communicator, rank)} pair.
Unlike int\-ra-com\-mun\-i\-cat\-ion, the rank is
relative to the remote group.

% One additional needed concept is the ``group leader.''  The process
% with rank 0 in a process group is designated ``group leader.''  This
% concept is used in support of user-level servers, and elsewhere.

Local and remote groups of an inter-communicator are not required to be
disjoint.
An intra-communicator can be seen as a particular case of an inter-communicator,
where local and remote groups happen to be identical.  The semantics of accessor
function are defined so as to be consistent with this interpretation.
Here is a summary
of the properties of int\-er-com\-mun\-i\-cat\-ion and inter-communicators:
\begin{itemize}
\item
The syntax of point-to-point communication is the same for both inter-
and int\-ra-com\-mun\-i\-cat\-ion.   The
same communicator can be used both for send and for receive operations.

\item
A target process is addressed by its rank in the remote group, both for sends
and for receives.

\item
Communications  using  an  inter-communicator are guaranteed not  to
conflict with any communications that use a different communicator.

\item
An inter-communicator cannot be used for collective communication.

\item
A  communicator  will provide  either  intra- or  int\-er-com\-mun\-i\-cat\-ion,
never both.

\item
Once constructed, the remote group of an inter-communicator may not be
changed.  Communication  with any process outside  of the remote group
is not allowed.
\end{itemize}

The routine \func{MPI\_COMM\_STAT()} may be used to determine if a
communicator is an inter- or intra-communicator.  Inter-communicators
can be used as arguments to some of the other communicator access
routines.  Inter-communicators cannot be used as input
to any of the constructor routines for intra-communicators or
the context management routines.

\implement{

Communicators can be represented at each process by a tuple consisting of:
\begin{description}
\item[group]
\item[send\_context]
\item[receive\_context]
\item[source]
\end{description}

For inter-communicators, {\bf group} describes the remote group, and
{\bf source} is the rank of the process in the local group.
For intra-communicators, {\bf group} is the communicator group
(remote=local), {\bf source} is the rank of the process in this group,
and {\bf send context} and {\bf receive context} are identical.
A group is represneted by a rank to absolute address tranlation table.

The inter-communicator cannot be discussed sensibly without
considering processes in both the local and remote groups.  Imagine a
process {\bf P} in group $\cal P$ which has an inter-communicator
{\bf Cp}, and a process
{\bf Q} in group $\cal Q$ which has an inter-communicator
{\bf Cq}. (Note that $\cal P$ and $\cal Q$ do not have to
be distinct.)
Then
\begin{itemize}
\item
{\bf Cp.group} describes the group $\cal Q$ and {\bf Cq.group}
describes the group $\cal P$.
\item
{\bf  Cp.send\_context~=~Cq.receive\_context} and the context is
unique in $\cal Q$; \\
{\bf Cp.receive\_context~=~ Cq.receive\_context} and this context is
unique in $\cal P$.
\item
{\bf Cp.source} is rank of {\bf P} in $\cal P$ and {\bf Cq.source} is
rank of {\bf Q} in $\cal Q$.
\end{itemize}

Assume that {\bf P} sends a message to {\bf Q} using the
inter-communicator.  Then
{\bf P} uses the {\bf group} table to find the absolute address
of {\bf Q}; {\bf source} and {\bf send\_context} are appended to the
message.

Assume that {\bf Q} posts a receive with an explicit source parameter
using the inter-communicator.
Then {\bf Q} matches {\bf receive\_context} to the message context and
source parameter to the message source.

The same algorithm is used for intra-communicators as well.
}

\subsection{Communicator Accessors}

\begin{funcdef}{MPI\_COMM\_STAT(comm, status)}
\funcarg{\IN}{  comm}{ handle to  communicator}
\funcarg{\OUT}{ status}{   integer status}
\end{funcdef}

This local routine allows the calling process to determine if a
communicator is an inter-communicator or an intra-communicator.  This
returns the status of communicator \mpiarg{comm}.  Valid status values
are \const{ MPI\_INTRA}, \const{ MPI\_INTER}, \const{ MPI\_INVALID}.

When an inter-communicator is used as an input argument to the
communicator accessors described under intra-communication, the
following table describes behavior.

\begin{center}
\begin{tabular}{|l|p{3.0in}|}
\hline
\multicolumn{2}{|c|}{\func{ MPI\_COMM\_} Function Behavior} \\
\multicolumn{2}{|c|}{(in Inter-Communication Mode)}\\
\hline
\hline
\func{MPI\_COMM\_SIZE()}     & returns the size of the remote group. \\
\func{MPI\_COMM\_GROUP()}    & returns the remote group. \\
\func{MPI\_COMM\_RANK()}     & returns \const{MPI\_UNDEFINED} \\
\func{MPI\_COMM\_CONTEXTS()} & erroneous \\
\hline
\end{tabular}
\end{center}

\discuss{Should there be any other status values?}

\subsection{Intercommunicator Constructors and Destructors}

Construction of an inter-communicator requires two separate collective
operations (one in the local group and one in the remote group) and a
point-to-point communication between a process in the local group and a process
in the remote group.
These operations may be performed with explicit synchronization of the two
groups and within each group by calling \func{MPI\_INTERCOMM\_MAKE()}.  The
explicit synchronization can cause deadlock in modular programs with cyclic
communication graphs, even if within each local group calls are executed in the
same order.  So, the local and remote operations
can be decoupled and the construction performed ``loosely synchronously'' by
calling the two routines \func{MPI\_COMM\_INTERCOMM\_START()} and
\func{MPI\_INTERCOMM\_FINISH()}.

\func{ MPI\_INTERCOMM\_START()} and \func{ MPI\_INTERCOMM\_FINISH()}
are  both collective operations in their local group, but the call within each
group need not by synchronized with the call in the other group.

These  routines  can  construct multiple  inter-communicators  with  a
single call.  This improves performance by  allowing  amortization  of
the synchronization overhead.

The inter-communicator objects are destroyed in the same way as
intra-communicator objects, by calling \func{MPI\_COMM\_FREE()}.

\begin{funcdef}{MPI\_INTERCOMM\_MAKE(local\_comm, local\_leader, bridge\_comm,
remote\_leader, tag, n, new\_comms)}
\funcarg{\IN}{  local\_comm  }{ handle to local intra-communicator}
\funcarg{\IN}{  local\_leader}{   rank of local group leader in
\mpiarg{my\_comm}}
\funcarg{\IN}{  bridge\_comm}{   handle  to parent intra-communicator}
\funcarg{\IN}{  remote\_leader}{   rank of remote group leader in \mpiarg{
bridge\_comm}}
\funcarg{\IN}{  tag      }{   ``safe'' tag}
\funcarg{\IN}{  n}{  number of new inter-communicators to construct}
\funcarg{\OUT}{ new\_comms}{  array of handles to new inter-communicators}
\end{funcdef}

This routine constructs an array of {\tt n} inter-communicators and sets
the first {\tt n} entries in array {\tt new\_comms} to point to them.
Intra-communicator \mpiarg{my\_comm} describes the
local group.  Intra-communicator \mpiarg{bridge\_comm} describes a group
that contains members from both local and remote groups, the local leader and
the remote leader.
The local leader is identified by its rank {\tt local\_leader} in the local
group.   The remote leader is identified by its rank {\tt remote\_leader} in
the bridge group.
Integer {\tt tag} is used to distinguish this
operation from others with the same bridge communicator.  Integer
\mpiarg{n}
is the number of new inter-communicators constructed.

The routine is
collective in each (local) group and synchronizes with the remote group.  All
calling processes in a local group provide
the same value for {\tt local\_leader}, {\tt tag} and {\tt n}.  The value of
{\tt bridge\_comm} and {\tt remote\_leader} is significant only at the process
which is the local leader.   (We thus have four possible combinations
of parameter values: those
provided by a nonleader in each of the two groups and the one provided by each
leader.)
Each of the inter-communicators produced provides int\-er-com\-mun\-i\-cat\-ion
with the remote group.

The two groups may intersect.
The same process can be both local and remote leader.

The function \func{MPI\_INTERCOMM\_MAKE} allow to combine two groups
into an inter-communicator even if no process in one group has
knowledge of the other group.  All that is required is that a third
group interesect with both groups and that a process in the
intersection is known in each group.

\implement{

The operation requires an exchange between the two leaders, followed by a
broadcast in each local group with the leader at the broadcast root.
}

\discuss{

Rather than allocating multiple inter-communicators, may want to allocate only
one inter-communicator and a store of hidden contexts.  Then {\tt
MPI\_COMM\_DUP} can be used to create additional ones.  This is more in line
with intra-communicator functions.
}

\begin{funcdef}{MPI\_INTERCOMM\_START(local\_comm, local\_leader,
bridge\_comm, remote\_leader, tag, n, handle)}
\funcarg{\IN}{  local\_comm  }{  local intra-communicator}
\funcarg{\IN}{  local\_leader}{   rank of local group leader in
\mpiarg{my\_comm}}
\funcarg{\IN}{  peer\_comm}{  ``parent'' intra-communicator}
\funcarg{\IN}{  remote\_leader}{  rank of remote group leader in \mpiarg{
peer\_comm}}
\funcarg{\IN}{  tag      }{ ``safe'' tag}
\funcarg{\IN}{  n}{   number of new inter-communicators to construct}
\funcarg{\OUT}{ handle }{    handle for \func{ MPI\_INTERCOMM\_FINISH()}}
\end{funcdef}

This starts off an inter-communicator creation operation, returning
a handle for the completion of the operation in \mpiarg{handle}.  It
is collective in \mpiarg{my\_comm}.
It does not wait for the remote group to execute
\func{MPI\_INTERCOMM\_START()}.
\mpiarg{handle} is
conceptually similar to the communication handle used by non-blocking
point-to-point routines.  It is constructed by a
\func{\_START} routine and destroyed by the matching \func{\_FINISH}
routine.  These handles are not valid for any other use.
It is
erroneous to call this routine again with the same \mpiarg{bridge\_comm},
\mpiarg{remote\_leader} and \mpiarg{tag} arguments, without calling
\func{MPI\_INTERCOMM\_FINISH()} to finish the first call.

\begin{funcdef}{MPI\_INTERCOMM\_FINISH(handle, new\_comms)}
\funcarg{\IN}{  handle   }{   handle returned by \func{
MPI\_INTERCOMM\_START()}}
\funcarg{\OUT}{ new\_comms }{  array of handles to new inter-communicators}
\end{funcdef}

This completes an asynchronous inter-communicator creation
operation, returning an array of handles to \mpiarg{n} new inter-communicators
in \mpiarg{new\_comms}, where {\tt n} is the count that was passed to the
\func{\_START} routine.
This routine is collective in the goup associated with communicator
\mpiarg{localy\_comm} of the corresponding call to
\func{MPI\_INTERCOMM\_START()}.  It
waits for the remote group to call \func{MPI\_INTERCOMM\_START()}
but does not wait for the remote group to call
\func{MPI\_INTERCOMM\_FINISH()}.

Inter-communicator objects are destroyed in the same fashion as
intra-communiation objects, using \func{MPI\_COMM\_FREE} described
above.

\implement{

\func{MPI\_INTERCOMM\_START} initiates asynchronous sends and receives for an
exchange of information between leaders.  \func{MPI\_INTERCOMM\_FINISH}
completes the exchange of information, next execute a broadcast in each local
group, with the local leader at the root.

}

\discuss{

({\bf Language binding}) we need yet another handle type.

}

\change

\discuss{

I deleted \func{MPI\_COMM\_SPLITL}.  Seems of limited usefulness (Since will
need
it only once, it is acceptable to use a more awkward mechanism for generating an
array of leaders, especially as any process in a group can be its leader)
If we salvage this procedure, I suggest to make it consistent with
\func{MPI\_COMM\_SPLIT}.
}

%%%%%%
\dross{

\subsection{Support for User-Level Servers}

The support for user-level servers takes into account the prevailing
view that all processes (possibly excepting a host process) are
initially equivalent members of the group of all processes.  This
group is described by pre-defined intra-communicator
\func{MPI\_COMM\_ALL}.  The user splits this group such that processes
in each parallel server are placed within a specific sub-group.  The
non-server processes are placed in a group of all non-servers.
Provided that the user can determine the ranks of the server group
leaders ({\em i.e.,} rank zero) and assign some tags for clients to send a
message to the group leaders, then a group leader can at any time
notify a server that it wishes to become a client.

MPI provides a routine, \func{MPI\_COMM\_SPLITL()}, that splits a parent
group, creates sub-groups (intra-communicators) according to supplied
keys, and returns the rank of each sub-group leader (relative to the
parent group).  This allows a process that does not know about a
sub-group to contact that sub-group via the sub-group leader, using
the parent communicator.  The keys may be used as unique tags.  This
information may also be used as input to \func{MPI\_COMM\_PEER\_MAKE()},
for example.

\begin{funcdef}{MPI\_COMM\_SPLITL(comm, key, nkeys, leaders, sub\_comm)}
\funcarg{\IN}{  comm    }{ extant intra-communicator to be ``split''}
\funcarg{\IN}{  key     }{ key for sub-group membership}
\funcarg{\IN}{  nkeys   }{ number of keys (number of sub-groups)}
\funcarg{\OUT}{ leaders }{ ranks of sub-group leaders in comm}
\funcarg{\OUT}{ sub\_comm}{  intra-communicator describing sub-group of calling
                  process}
\end{funcdef}

This routine splits the group described by intra-communicator comm
into nkeys sub-groups.  Each calling process must specify a value of
key in the range [0\ldots(\mpiarg{nkeys}-1)].  Processes specifying the
same key are placed in the same sub-group.  Ranks of the leaders of
each sub-group (relative to \mpiarg{comm}) are returned in integer array
leaders.  This routine returns a new intra-communicator,
\mpiarg{sub\_comm}, that describes the sub-group to which the calling
process belongs.
}
%%%%

\subsection{Name Service}

MPI provides a name service to simplify construction of
inter-communicators.  This service allows a local process group to
create an inter-communicator when the only available information about
the remote group is a user-defined character string.  A synchronizing
version is provided by routine \func{MPI\_INTERCOMM\_NAME}.  A loosely
synchronous version is provided by routines
\func{MPI\_INTERCOMM\_NAME\_START} and
\func{MPI\_INTERCOMM\_NAME\_FINISH}.

\begin{funcdef}{MPI\_INTERCOMM\_NAME(comm, name, n,
new\_comms)}

\funcarg{\IN}{  comm}{  handle to local intra-communicator}
\funcarg{\IN}{  name}{   character string }
\funcarg{\IN}{  n}{ number of new inter-communicators to construct}
\funcarg{\OUT}{ new\_comms}{ Array of handles to new inter-communicators}
\end{funcdef}

This is the name-served equivalent of \func{MPI\_INTERCOMM\_MAKE} in which
the caller need only know a name for the peer connection.
The call is collective within each local group and all memebers of the
group provide the same values for {\tt name} and {\tt n}.  The call
blocks until
another group executes a call to \func{MPI\_INTERCOMM\_NAME} or
\func{MPI\_INTERCOMM\_NAME\_START} with the same {\tt name} parameter.
An array of handles to {\tt n} inter-communicators for these two groups
is then returned in {\tt new\_comms}.

\begin{funcdef}{MPI\_INTERCOMM\_NAME\_START(comm, name, n, handle)}
\funcarg{\IN}{  comm}{  handle to local intra-communicator}
\funcarg{\IN}{  name}{   character string }
\funcarg{\IN}{  n}{    number of new inter-communicators to construct}
\funcarg{\OUT}{ handle}{      handle for
MPI\_INTERCOMM\_NAME\_FINISH()}
\end{funcdef}

This is the name-served equivalent of
\func{MPI\_INTERCOMM\_START}.  The operation is compelted by a call to
\mpifunc{MPI\_INTERCOMM\_FINISH}.

\change

\discuss{

I use the same {\tt \_FINISH} routine for the name served
and the regular inter-communicator making routines

Here, too, rather then creating n communicators, one could return n
cached contexts.

}

\implement{

Assume that the ``host'' process is used as name server.  A call to
\func{MPI\_INTERCOMM\_NAME} can be implemented by having a selected group
leader (say, process with rank 0) send a message to the name server.
When the name server has received two requests with matching names,
it sends back to each leader a description of the remote group, and a
``clean'' context.  The leaders next broadcast this information within
each group.  In the nonblocking version, the {\tt \_START} function
causes the leader to send a nonblocking message to the name server and
post a nonblocking receive;
the {\tt \_FINISH} function causes the leaders to receive the reply
from the name server and execute the local broadcast.

}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%% No changes made below this line     MS
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\section{Cacheing}
MPI provides a ``cacheing'' facility that allows an application to attach
arbitrary pieces of information, called {\em attributes}, to context,
group, and communicator descriptors; it provides this facility to user
programs as well.  Attributes are local to the process and are not
included if the descriptor were somehow sent to another
process\footnote{The deletion of flatten/unflatten makes this point
moot.}. This facility is intended to support optimizations such as
saving persistent communication handles and recording topology-based
decisions by adaptive algorithms.  However, attributes are propagated
intentionally by specific MPI routines.

To summarize, cacheing is, in particular, the process by which
implementation-defined data (and virtual topology data) is propagated
in groups and communicators.

\discuss{Attribute propagation must be discussed carefully.}

\subsection{Functionality}
MPI provides the following services related to cacheing.  They are
all process-local.

\begin{funcdef}{MPI\_ATTRIBUTE\_ALLOC(n,handle\_array,len)}
\funcarg {\IN}{ n}{  number of handles to allocate}
\funcarg {\OUT}{ handle\_array}{ pointer to array of opaque attribute handling structure}
\funcarg {\OUT}{ len}{ length of each opaque structure}
\end{funcdef}
Allocates a new attribute, so user programs and functionality layered
on top of MPI can access attribute technology.

\begin{funcdef}{MPI\_ATTRIBUTE\_FREE(handle\_array,n)}
\funcarg {\IN}{ handle\_array}{ array of pointers to opaque attribute handling structures}
\funcarg {\IN}{ n}{ number of handles to deallocate}
\end{funcdef}
Frees attribute handle.

\begin{funcdef}{MPI\_GET\_ATTRIBUTE\_KEY(keyval)}
\funcarg {\OUT}{ keyval}{ Provide the integer key value for future storing.}
\end{funcdef}
Generates a new cache key.

\begin{funcdef}{MPI\_SET\_ATTRIBUTE(handle, keyval, attribute\_val, attribute\_len,
                   attribute\_destructor\_routine)}
\funcarg{\IN}{ handle}{ opaque attribute handle}
\funcarg{\IN}{ keyval}{ The integer key value for future storing.}
\funcarg{\IN}{ attribute\_val}{ attribute value (opaque pointer)}
\funcarg{\IN}{ attribute\_len}{ length of attribute (in bytes)}
\funcarg{\IN}{ attribute\_destructor\_routine}{ What one calls to get
rid of this attribute later}
\end{funcdef}
Stores attribute in cache by key.

\begin{funcdef}{MPI\_TEST\_ATTRIBUTE(handle,keyval,attribute\_ptr,len)}
\funcarg{\IN}{ handle}{ opaque attribute handle}
\funcarg{\IN}{ keyval}{ The integer key value for future storing.}
\funcarg{\OUT}{ attribute\_ptr}{ void pointer to attribute, or NULL if not found}
\funcarg{\OUT}{ len}{ length in bytes of attribute, if found.}
\end{funcdef}
Retrieve attribute from cache by key.

\begin{funcdef}{MPI\_DELETE\_ATTRIBUTE(handle, keyval)}
\funcarg{\IN}{ handle}{ opaque attribute handle}
\funcarg{\IN}{ keyval}{ The integer key value for future storing.}
\end{funcdef}
Delete attribute from cache by key.

\subsubsection{Example}
Each attribute consists of a pointer or a value of the same size as a
pointer, and would typically be a reference to a larger block of
storage managed by the module.  As an example, a global operation
using cacheing to be more efficient for all contexts of a group after
the first call might look like this:

\begin{verbatim}
   static int gop_key_assigned = 0;    /* 0 only on first entry */
   static int gop_key;        /* key for this module's stuff */

   efficient_global_op (comm, ...)
   void *comm;
   {
     struct gop_stuff_type *gop_stuff;   /* whatever we need */
     void  *group = mpi_comm_group(comm);

     if (!gop_key_assigned)     /* get a key on first call ever */
     { gop_key_assigned = 1;
       if ( ! (gop_key = mpi_Get_Attribute_Key()) ) {
         mpi_abort ("Insufficient keys available");
       }
     }
     if (mpi_Test_Attribute (mpi_group_attr(group),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_set_attribute (mpi_group_attr(group), 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 delete */
    struct gop_stuff_type *gop_stuff;
    {
      /* ... free storage pointed to by gop_stuff ... */
    }
\end{verbatim}

\discuss{The cache facility could also be provided for other descriptors, but
it is less clear how such provision would be useful. It is suggested
that this issue be reviewed in reference to Virtual Topologies.}

%----------------------------------------------------------------------

\section{Formalizing the Loosely Synchronous Model (Usage, Safety)}

\subsection{Basic Statements}
When a caller passes a communicator (which contains a context and
group) to a callee, that communicator must be free of side effects
throughout execution of the subprogram (quiescent). This provides one
model in which libraries can be written, and work ``safely.''
For libraries so designated, the callee has permission to do whatever
communication it likes with the communicator, and under the above
guarantee knows that no other communications will interfere. Since we
permit the creation of new communicators without synchronization
(assuming preallocated contexts), this does not impose a significant
overhead.

This form of safety is analogous to other common computer science
usages, such as passing a descriptor of an array to a library routine.
The library routine has every right to expect such a descriptor to
be valid and modifiable.

\subsection{Models of Execution}

We say that a parallel procedure is {\em active} at a process if the process
belongs to a group that may collectively execute the procedure, and
some member of that group is currently executing the procedure code.
If a parallel procedure is active at a process, then this process may
be receiving messages pertaining to this procedure, even if it
does not currently execute the code of this procedure.

\subsubsection{Nonreentrant parallel procedures}

This covers the case where, at any point in time, at most one
invocation of a parallel procedure can be active at any process.  That
is, concurrent invocations of the same parallel procedure may occur
only within disjoint groups of processes.  For example, all
invocations of parallel procedures involve all processes, processes
are single-threaded, and there are no recursive invocations.

In such a case, a context can be statically allocated to each
procedure.  The static allocation can be done in a preamble, as part
of initialization code.  Or, it can be done a compile/link time, if
the implementation has additional mechanisms to reserve context
values.  Communicators to be used by the different procedures can be
build in a preamble, if the executing groups are statically defined;
if the executing groups change dynamically, then a new communicator
has to be built whenever the executing group changes, but this new
communicator can be built using the same preallocated context.  If the
parallel procedures can be organized into libraries, so that only one
procedure of each library can be concurrently active at each
processor, then it is sufficient to allocate one context per library.

\subsubsection{Parallel procedures that are nonreentrant within each
executing group}

This covers the case where, at any point in time, for each process
group, there can be at most one active invocation of a parallel
procedure by a process member.  However, it might be possible that the
same procedure is concurrently invoked in two partially (or
completely) overlapping groups.  For example, the same collective
communication function may be concurrently invoked on two partially
overlapping groups.

In such a case, a context is associated with each parallel procedure
and each executing group, so that overlapping execution groups have
distinct communication contexts.  (One does not need a different
context from each group; one merely needs a ``coloring'' of the
groups, so that One can generate the communicators for each parallel
procedure when the execution groups are defined.  Here, again, one
only need one context for each library, if no two procedures from the
same library can be concurrently active in the same group.

Note that, for collective communication libraries, we do allow several
concurrent invocations within the same group: a broadcast in a group
may be started at a process before the previous broadcast in that
group ended at another process.  In such a case, one cannot rely on
context mechanisms to disambiguate successive invocations of the same
parallel procedure within the same group: the procedure need be
implemented so as to avoid confusion.  For example, for broadcast, one
may need to carry additional information in messages, such as the
broadcast root, to help in such disambiguation; one also relies on
preservation of message order by MPI.\@ With such an approach, we may
be gaining performance, but we loose modularity.  It is not sufficient
to implement the parallel procedure so that it works correctly in
isolation, when invoked only once; it needs to be implemented so that
any number of successive invocations will execute correctly.  Of
course, the same approach can be used for other parallel libraries.

\subsubsection{Well-nested parallel procedures}

Calls of parallel procedures are well nested if a new parallel
procedure is always invoked in a subset of a group executing the same
parallel procedure.  Thus, processes that execute the same parallel
procedure have the same execution stack.

In such a case, a new context need to be dynamically allocated
for each new invocation of a parallel procedure.   However, a
stack mechanism can be used for allocating new contexts.
Thus, a possible mechanism is to allocate first a large number of
context's (up to the upper bound on the depth of nested parallel
procedure calls), and then use a local stack management of these
context's on each process to create a new communicator (using
\func{ MPI\_COMM\_MAKE}) for each new invocation.

\subsubsection{The General case}

In the general case, there may be multiple concurrently active
invocations of the same parallel procedure within the same group;
invocations may not be well-nested.  A new context need to be
created for each invocation.  It is the user responsibility to make
sure that, if two distinct parallel procedures are invoked
concurrently on overlapping sets of processes, then context
allocation or communicator creation is properly coordinated.

\section{Motivating Examples}
\discuss{The int\-ra-com\-mun\-i\-cat\-ion examples were first presented at the June MPI meeting;
the int\-er-com\-mun\-i\-cat\-ion routines (when added) are new.}

\subsection{Current Practice \#1}
\label{context-ex1}
\noindent Example \#1a:
\begin{verbatim}
    int me, size;
    ...
    mpi_init();
    mpi_comm_rank(MPI_COMM_ALL, &me);
    mpi_comm_size(MPI_COMM_ALL, &size);

    printf("Process %d size %d\n", me, size);
    ...
\end{verbatim}
Example \#1a is a do-nothing program that initializes itself legally, and
refers to the the ``all'' communicator, and prints a message.  This
example does not imply that MPI supports printf-like communication itself.

\noindent Example \#1b:
\begin{verbatim}
    int me, size;
    ...
    mpi_init();
    mpi_comm_rank(MPI_COMM_ALL, &me);   /* local */
    mpi_comm_size(MPI_COMM_ALL, &size); /* local */

    if((me % 2) == 0)
       mpi_send(..., ((me + 1) % size), MPI_COMM_ALL);
    else
       mpi_recv(..., ((me - 1 + size) % size), MPI_COMM_ALL);
    ...
\end{verbatim} Example \#1b schematically illustrates
message exchanges between ``even'' and ``odd'' processes in the ``all''
communicator.

\subsection{Current Practice \#2}
\label{context-ex2}
\begin{verbatim}
    void *data;
    int me;
    int count;
    ...
    mpi_init();
    mpi_comm_rank(MPI_COMM_ALL, &me);

    if(me == 0)
    {
        /* get input, create buffer ``data'' */
        ...
    }

    mpi_broadcast(data, count, MPI_BYTE, 0, MPI_COMM_ALL);

    ...
\end{verbatim}
This example illustrates the use of a collective communication.
\subsection{(Approximate) Current Practice \#3}
\label{context-ex3}
\begin{verbatim}
    int me, count, count2;
    void *send_buf, *recv_buf, *send_buf2, *recv_buf2;
    MPI_Group MPI_GROUP_ALL, grp0, grprem;
    MPI_Comm commslave;
    static int ranks[] = {0};
    ...
    mpi_init();
    mpi_comm_group(MPI_COMM_ALL, &MPI_GROUP_ALL);
    mpi_comm_rank(MPI_COMM_ALL, &me);  /* local */
    mpi_local_subgroup(group_all, 1, ranks, &grp0); /* local */
    mpi_group_difference(group_all, grp0, &grprem); /* local */
    mpi_comm_make(MPI_COMM_ALL, grprem, &commslave);

    if(me != 0)
    {
        /* compute on slave */
        ...
        mpi_reduce(send_buf, recv_buff, count, MPI_BYTE, commslave);
        ...
    }
    /* zero falls through immediately to this reduce, others do later... */
    mpi_reduce(send_buf2, recv_buff2, count2, MPI_BYTE, MPI_COMM_ALL);
\end{verbatim}
This example illustrates how a group consisting of all but the zeroth
process of the ``all'' group is created, and then how a communicator
is formed (\mpiarg{ commslave}) for that new group.  The new communicator is used in
a collective call, and all processes execute a collective call
in the \const{ MPI\_COMM\_ALL} context.  This example illustrates
how the two communicators (which possess distinct contexts) protect
communication.  That is, communication in \const{ MPI\_COMM\_ALL} is
insulated from communication in \mpiarg{ commslave}, and vice versa.

In summary, for communication with ``group safety,''
contexts within communicators must be distinct.

\subsection{Example \#4}
\label{context-ex4}
The following example is meant to illustrate ``safety'' between
point-to-point and collective communication.  MPI guarantees that a single
communicator can do safe point-to-point and collective communication.
\begin{verbatim}
#define TAG_ARBITRARY 12345
#define SOME_COUNT       50
    int me;
    MPI_Group MPI_GROUP_ALL, subgroup;
    int ranks[] = {2, 4, 6, 8};
    ...
    mpi_init();
    mpi_comm_group(MPI_COMM_ALL, &MPI_GROUP_ALL);
    mpi_local_subgroup(MPI_GROUP_ALL, 4, ranks, &subgroup); /* local */
    mpi_group_rank(subgroup, &me);     /* local */

    mpi_comm_make(MPI_COMM_ALL, subgroup, &the_comm);

    if(me != MPI_UNDEFINED)
    {
        /* asynchronous receive: */
        mpi_irecv(handle, start, count, MPI_DOUBLE,
                   MPI_SRC_ANY, TAG_ARBITRARY, the_comm);
    }

    for(i = 0; i < SOME_COUNT, i++)
        mpi_reduce(..., the_comm);
\end{verbatim}

\subsection{Library Example \#1}
\label{context-ex5}
The main program:
\begin{verbatim}
    int done = 0;
    user_lib_t *libh_a, *libh_b;
    void *dataset1, *dataset2;
    ...
    mpi_init();
    ...
    init_user_lib(MPI_COMM_ALL, &libh_a);
    init_user_lib(MPI_COMM_ALL, &libh_b);
    ...
    user_start_op(libh_a, dataset1);
    user_start_op(libh_a, dataset2);
    ...
    while(!done)
    {
        /* work */
        ...
        mpi_reduce(..., MPI_COMM_ALL);
        ...
        /* see if done */
        ...
    }
    user_end_op(libh_a);
    user_end_op(libh_b);
\end{verbatim}

\noindent The user library initialization code:
\begin{verbatim}
void init_user_lib(void *comm, user_lib_t **handle)
{
   user_lib_t *save;
   void *context;
   void *group;
   int len;

   user_lib_initsave(&save); /* local */
   mpi_contexts_alloc(comm, 1);
   mpi_comm_dup(comm, &(save -> comm));

   /* other inits */
   *handle = save;
}
\end{verbatim}
Notice that the communicator \mpiarg{ comm} passed to the library {\em is}
needed to allocate new contexts.

\noindent User start-up code:
\begin{verbatim}
void user_start_op(user_lib_t *handle, void *data)
{
    mpi_irecv(&(handle -> irecv_handle), ..., handle -> comm);
    mpi_isend(&(handle -> isend_handle), ..., handle -> comm);
}
\end{verbatim}

\noindent User clean-up code:
\begin{verbatim}
void user_end_op(user_lib_t *handle)
{
    mpi_wait(handle -> isend_handle);
    mpi_wait(handle -> irecv_handle);
}
\end{verbatim}

\subsection{Library Example \#2}
\label{context-ex6}
The main program:
\begin{verbatim}
    int ma, mb;
    ...
    list_a := ``[0,1]'';
    list_b := ``[0,2{,3}]'';

    mpi_local_subgroup(MPI_GROUP_ALL, 2, list_a, &group_a);
    mpi_local_subgroup(MPI_GROUP_ALL, 2(3), list_b, &group_b);

    mpi_comm_make(MPI_COMM_ALL, group_a, &comm_a);
    mpi_comm_make(MPI_COMM_ALL, group_b, &comm_b);

    mpi_comm_rank(comm_a, &ma);
    mpi_comm_rank(comm_b, &mb);

    if(ma != MPI_UNDEFINED)
       lib_call(comm_a);
    if(mb != MPI_UNDEFINED)
    {
       lib_call(comm_b);
       lib_call(comm_b);
    }
\end{verbatim}

\noindent The library:
\begin{verbatim}
void lib_call(void *comm)
{
    int me, done = 0;
    mpi_comm_rank(comm, &me);
    if(me == 0)
        while(!done)
        {
            mpi_recv(..., comm, MPI_SRC_ANY);
            ...
        }
    else
    {
        /* work */
        mpi_send(..., comm, 0);
        ....
    }
    MPI_SYNC(comm);   /* include/no safety for safety/no safety */
}
\end{verbatim}
The above example is really two examples, depending on whether or not you
include rank 3 in {\tt list\_b}.  This example illustrates that, despite
contexts, subsequent calls to {\tt lib\_call} with the same context
need not be safe from one another (``back masking'').  Safety is realized
if the \func{ MPI\_SYNC} is added.  What this demonstrates is that
libraries have to be written carefully, even with contexts.

Algorithms like ``combine'' have strong enough source selectivity so that
they are inherently OK.  So are multiple calls to a typical tree
broadcast algorithm with the same root.  However, multiple calls
to a typical tree broadcast algorithm -- with different roots ---
could break.   Therefore, such algorithms would have to utilize the
tag to keep things straight.  All of the foregoing is a discussion
of ``collective calls'' implemented with point to point operations.
MPI implementations may or may not implement collective calls using
point-to-point operations.  These algorithms are used to illustrate
the issues of correctness and safety, independent of how MPI implements
its collective calls.

\subsection{Inter-Communication Examples}

\subsubsection{Example 1:  Three-Group ``Pipeline"}
\label{context-ex7}
\begin{verbatim}

              +---------+         +---------+         +---------+
              |         |         |         |         |         |
              | Group 0 | <-----> | Group 1 | <-----> | Group 2 |
              |         |         |         |         |         |
              +---------+         +---------+         +---------+

\end{verbatim}

Groups 0 and 1 communicate.  Groups 1 and 2 communicate.  Therefore, group
0 requires one inter-communicator, group 1 requires two inter-communicators,
and group 2 requires 1 inter-communicator.  Note that the synchronous
inter-communicator constructor (\func{MPI\_COMM\_PEER\_MAKE()}) can be safely used
here since there is no cyclic communication.

\begin{verbatim}
    void * myComm;                   /* intra-communicator of local sub-group */
    void * myFirstComm;                                 /* inter-communicator */
    void * mySecondComm;          /* second inter-communicator (group B only) */
    int membershipKey;
    int subGroupLeaders[3];

    MPI_INIT();
    ...

    /* User code must generate membershipKey in the range [0, 1, 2] */
    membershipKey = ... ;

    /* Build intra-communicator for local sub-group and get group leaders */
    /* of each sub-group (relative to MPI_COMM_ALL). */
    MPI_COMM_SPLITL(MPI_COMM_ALL, membershipKey, 3,
                          subGroupLeaders, &myComm);

    /* Build inter-communicators.  Tags are hard-coded. */
    if (membershipKey == 0)
        {                             /* Group 0 communicates with group 1. */
        MPI_COMM_PEER_MAKE(myComm, 0, MPI_COMM_ALL,
            subGroupLeaders[1], 10, 1, &myFirstComm);
        }
    else if (membershipKey == 1)
        {                      /* Group 1 communicates with groups 0 and 2. */
        MPI_COMM_PEER_MAKE(myComm, 0, MPI_COMM_ALL,
            subGroupLeaders[0], 10, 1, &myFirstComm);
        MPI_COMM_PEER_MAKE(myComm, 0, MPI_COMM_ALL,
            subGroupLeaders[2], 21, 1, &mySecondComm);
        }
    else if (membershipKey == 2)
        {                             /* Group 2 communicates with group 1. */
        MPI_COMM_PEER_MAKE(myComm, 0, MPI_COMM_ALL,
            subGroupLeaders[1], 21, 1, &myFirstComm);
        }
\end{verbatim}

\subsubsection{Example 2:  Three-Group ``Ring"}
\label{context-ex8}

\begin{verbatim}
         +-----------------------------------------------------------+
         |                                                           |
         |    +---------+         +---------+         +---------+    |
         |    |         |         |         |         |         |    |
         +--> | Group 0 | <-----> | Group 1 | <-----> | Group 2 | <--+
              |         |         |         |         |         |
              +---------+         +---------+         +---------+
\end{verbatim}

Groups 0 and 1 communicate.  Groups 1 and 2 communicate.  Groups 0 and
2 communicate.  Therefore, each requires two inter-communicators.
Note that the "loosely synchronous" inter-communicator constructor (
\func{MPI\_COMM\_PEER\_MAKE\_START()} and \func{MPI\_COMM\_PEER\_MAKE\_FINISH()}) is the
best choice here due to the cyclic communication.

\begin{verbatim}
    MPI_Comm  myComm;              /* intra-communicator of local sub-group */
    MPI_Comm myFirstComm;                            /* inter-communicators */
    MPI_Comm mySecondComm;
    make_id firstMakeID, secondMakeID;              /* handles for "FINISH" */
    int membershipKey;
    int subGroupLeaders[3];

    MPI_INIT();
    ...

    /* User code must generate membershipKey in the range [0, 1, 2] */
    membershipKey = ... ;

    /* Build intra-communicator for local sub-group and get group leaders */
    /* of each sub-group (relative to MPI_COMM_ALL). */
    MPI_COMM_SPLITL(MPI_COMM_ALL, membershipKey, 3, subGroupLeaders, &myComm);

    /* Build inter-communicators.  Tags are hard-coded. */
    if (membershipKey == 0)
        {                      /* Group 0 communicates with groups 1 and 2. */
        MPI_COMM_PEER_MAKE_START(myComm, 0, MPI_COMM_ALL, subGroupLeaders[2], 20,
                                 1, &firstMakeID);
        MPI_COMM_PEER_MAKE_START(myComm, 0, MPI_COMM_ALL, subGroupLeaders[1], 10,
                                 1, &secondMakeID);
        }
    else if (membershipKey == 1)
        {                      /* Group 1 communicates with groups 0 and 2. */
        MPI_COMM_PEER_MAKE_START(myComm, 0, MPI_COMM_ALL, subGroupLeaders[0], 10,
                                 1, &firstMakeID);
        MPI_COMM_PEER_MAKE_START(myComm, 0, MPI_COMM_ALL, subGroupLeaders[2], 21,
                                 1, &secondMakeID);
        }
    else if (membershipKey == 2)
        {                      /* Group 2 communicates with groups 0 and 1. */
        MPI_COMM_PEER_MAKE_START(myComm, 0, MPI_COMM_ALL, subGroupLeaders[1], 21,
                                 1, &firstMakeID);
        MPI_COMM_PEER_MAKE_START(myComm, 0, MPI_COMM_ALL, subGroupLeaders[0], 20,
                                 1, &secondMakeID);
        }

    /* Everyone has the same "FINISH" code... */
    MPI_COMM_PEER_MAKE_FINISH(firstMakeID, &myFirstComm);
    MPI_COMM_PEER_MAKE_FINISH(secondMakeID, &mySecondComm);
\end{verbatim}

\subsubsection{Example 3:  Three-Group ``Pipeline" Using Name Service}
\label{context-ex9}

\begin{verbatim}
              +---------+         +---------+         +---------+
              |         |         |         |         |         |
              | Group 0 | <-----> | Group 1 | <-----> | Group 2 |
              |         |         |         |         |         |
              +---------+         +---------+         +---------+
\end{verbatim}

Groups 0 and 1 communicate.  Groups 1 and 2 communicate.  Therefore,
group 0 requires one inter-communicator, group 1 requires two
inter-communicators, and group 2 requires 1 inter-communicator.  Note
that the synchronous inter-communicator constructor
(\func{MPI\_COMM\_NAME\_MAKE()}) can be safely used here since there
is no cyclic communication.

\begin{verbatim}
    MPI_Comm myComm;                /* intra-communicator of local sub-group */
    MPI_Comm myFirstComm;                              /* inter-communicator */
    MPI_Comm mySecondComm;       /* second inter-communicator (group B only) */

    MPI_INIT();
    ...

    /* User builds intra-communicator myComm describing the local sub-group */
    /* using any appropriate MPI routine(s).  (For example, myComm could */
    /* have been passed in as an argument to a user subroutine.) */
    myComm = ... ;

    /* Build inter-communicators.  Group membership conditions must be */
    /* provided by the user. */
    if (<I am in group 0>)
        {                             /* Group 0 communicates with group 1. */
        MPI_COMM_NAME_MAKE(myComm, "Connect 10", 1, &myFirstComm);
        }
    else if (<I am in group 1>)
        {                      /* Group 1 communicates with groups 0 and 2. */
        MPI_COMM_NAME_MAKE(myComm, "Connect 10", 1, &myFirstComm);
        MPI_COMM_NAME_MAKE(myComm, "Connect 21", 1, &mySecondComm);
        }
    else if (<I am in group 2>)
        {                             /* Group 2 communicates with group 1. */
        MPI_COMM_NAME_MAKE(myComm, "Connect 21", 1, &myFirstComm);
        }
\end{verbatim}

\subsubsection{Example 4:  Three-Group ``Ring" Using Name Service}
\label{context-ex10}

\begin{verbatim}
         +-----------------------------------------------------------+
         |                                                           |
         |    +---------+         +---------+         +---------+    |
         |    |         |         |         |         |         |    |
         +--> | Group 0 | <-----> | Group 1 | <-----> | Group 2 | <--+
              |         |         |         |         |         |
              +---------+         +---------+         +---------+
\end{verbatim}

Groups 0 and 1 communicate.  Groups 1 and 2 communicate.  Groups 0 and
2 communicate.  Therefore, each requires two inter-communicators.
Note that the "loosely synchronous" inter-communicator constructor (
\func{MPI\_COMM\_NAME\_MAKE\_START()} and \func{MPI\_COMM\_NAME\_MAKE\_FINISH()}) is the
best choice here due to the cyclic communication.

\begin{verbatim}
    MPI_Comm  myComm;              /* intra-communicator of local sub-group */
    MPI_Comm  myFirstComm;                           /* inter-communicators */
    MPI_Comm  mySecondComm;
    make_id firstMakeID, secondMakeID;              /* handles for "FINISH" */

    MPI_INIT();
    ...

    /* User builds intra-communicator myComm describing the local sub-group */
    /* using any appropriate MPI routine(s).  (For example, myComm could */
    /* have been passed in as an argument to a user subroutine.) */
    myComm = ... ;

    /* Build inter-communicators.  Group membership conditions must be */
    /* provided by the user. */
    if (<I am in group 0>)
        {                      /* Group 0 communicates with groups 1 and 2. */
        MPI_COMM_NAME_MAKE_START(myComm, "Connect 20", 1, &firstMakeID);
        MPI_COMM_NAME_MAKE_START(myComm, "Connect 10", 1, &secondMakeID);
        }
    else if (<I am in group 1>)
        {                      /* Group 1 communicates with groups 0 and 2. */
        MPI_COMM_NAME_MAKE_START(myComm, "Connect 10", 1, &firstMakeID);
        MPI_COMM_NAME_MAKE_START(myComm, "Connect 21", 1, &secondMakeID);
        }
    else if (<I am in group 2>)
        {                      /* Group 2 communicates with groups 0 and 1. */
        MPI_COMM_NAME_MAKE_START(myComm, "Connect 21", 1, &firstMakeID);
        MPI_COMM_NAME_MAKE_START(myComm, "Connect 20", 1, &secondMakeID);
        }

    /* Everyone has the same "FINISH" code... */
    MPI_COMM_NAME_MAKE_FINISH(firstMakeID, &myFirstComm);
    MPI_COMM_NAME_MAKE_FINISH(secondMakeID, &mySecondComm);

\end{verbatim}

%---------------------------------------------------------------------------
%---------------------------------------------------------------------------
%-------STOP HERE-----------------------------------------------------------
%---------------------------------------------------------------------------
%---------------------------------------------------------------------------

\end{document}