Subject: draft of MPI Context proposals (Latex)

From: Tony Skjellum <[email-masked]>
Date: Wed, 24 Mar 93 10:57:27 CST

\documentstyle{report}
\begin{document}
\title{Context Subcommittee Proposals}
\author{Lyndon~Clarke \and Anthony Skjellum \and Rik~Littlefield
\and Marc~Snir}
\date{March 24, 1993}
\maketitle
\newpage
%======================================================================%
% BEGIN "Proposal I"

%======================================================================%
% BEGIN "Proposal I"
% Written by Marc Snir
% Edited by Lyndon J. Clarke
% March 1993
%

\newcommand{\discuss}[1]{
\ \\ \ \\ {\small {\bf Discussion:} #1} \ \\ \ \\
}

\newcommand{\missing}[1]{
\ \\ \ \\ {\small {\bf Missing:} #1} \\ \ \\
}

\chapter{Proposal I --- Marc~Snir}

\section{Contexts}

A {\bf context} consists of:
\begin{itemize}
\item
A set of processes that currently belong to the context (possibly all processes,
or a proper subset).
\item
A {\bf ranking} of the processes within that context, i.e., a numbering of the
processes in that context from 0 to $n-1$, where $n$ is the number of processes
in that context.
\end{itemize}

A process may belong to several contexts at the same time.

Any interprocess communication occurs within a context, and messages sent within
one context can be received only within the same context.  A context is
specified using a {\em context handle} (i.e., a handle to an opaque object that
identifies
a context).  Context handles cannot be transferred for one process to another;
they can be used only on the process where they where created.

Follows examples of possible uses for contexts.

\subsection{Loosely synchronous library call interface}

Consider the case where a parallel application executes a ``parallel call'' to a
library routine, i.e., where all processes transfer control to the library
routine.  If the library was developed separately, then one should beware of the
possibility that the library code may receive by mistake messages send by the
caller code, and vice-versa.  To prevent such occurrence one might use
a barrier synchronization before and after the parallel library call.  Instead,
one can allocate a different context to the library, thus preventing unwanted
interference.  Now, the transfer of control to the library need not be
synchronized.

\subsection{Functional decomposition and modular code development}

Often, a parallel application is developed by integrating several distinct
functional modules, that is each developed separately.  Each module is a
parallel program that runs on a dedicated set of processes, and the computation
consists of phases where modules compute separately, intermixed with
global phases where all processes communicate.  It is convenient to allow each
module to use its own private process numbering scheme, for the intramodule
computation.  This is achieved by using a private module context for
intramodule computation, and a global context for intermodule communication.

\subsection{Collective communication}

MPI supports collective communication within dynamically created groups of
processes.  Each such group can be represented by a distinct context.  This
provides a simple mechanism to ensure that communication that pertains to
collective communication within one group is not confused with
collective communication within another group.

\subsection{Lightweight gang scheduling}

Consider an environment where processes are multithtreaded.  Contexts can be
used to provide a mechanism whereby all processes are time-shared
between several parallel executions, and can context
switch from one parallel execution to another, in a loosely synchronous manner.
A thread is allocated on each process to each parallel execution, and a
different context is used to identify each parallel execution.  Thus, traffic
from one execution cannot be confused with traffic from another execution.  The
blocking and unblocking of threads due to communication events provide a
``lazy'' context switching mechanism.  This can be extended to the case where
the parallel executions are spanning distinct process subsets. (MPI does not
require multithreaded processes.)

\discuss{
A context handle might be implemented as a pointer to a
structure that consists of context label (that is carried by messages sent
within this context) and a context member table, that
translates process ranks within a context to absolute addresses or to routing
information.  Of course, other implementations are possible, including
implementations that do not require each context member to store a full list of
the context members.

Contexts can be used only on the process where they were created.  Since the
context carries information on the group of processes that belong to this
context, a process can send a message within a context only to other processes
that belong to that context.  Thus, each process needs to keep track only of
the contexts that where created at that process; the total number of contexts
per process is likely to be small.

The only difference I see between this current definition of context, which
subsumes the group concept, and a pared down definition, if that I assume here
that process numbering is relative to the context, rather then being global,
thus requiring a context member table.  I argue that this is not much added
overhead, and gives much additional needed functionality.
\begin{itemize}
\item
If a new context is created by copying a previous context, then one
does not need a new member table;
rather, one needs just a new context label and a new pointer to the same old
context member table.  This holds true, in particular, for contexts that include
all processes.
\item
A context member table makes sure that a message is sent only to a process that
can execute in the context of the message.  The alternative mechanism, which is
checking at reception, is less efficient, and requires that each context label
be system-wide unique.  This requires that, to the least, all processes in a
context execute a collective agreement algorithm at the creation
of this context.
\item
The use of relative addressing within each context is needed to support true
modular development of subcomputations that execute on a subset of the
processes.  There is also a big advantage in using the same context construct
for collective communications as well.
\end{itemize}
}

\section{Context Operations}

A global context {\bf ALL} is predefined.  All processes belong to this context
when computation starts.  MPI does not specify how processes are initially
ranked within
the context ALL.  It is expected that the start-up procedure used to
initiate an MPI program (at load-time or run-time) will provide information or
control on this initial ranking (e.g., by
specifying that processes are ranked according to their pid's, or according to
the physical addresses of the executing processors, or according to a numbering
scheme specified at load time).

\discuss{If we think of adding new processes at run-time, then {\tt ALL}
conveys the wrong impression, since it is just the initial set of processes.}

The following operations are available for creating new contexts.

{\bf \ \\ MPI\_COPY\_CONTEXT(newcontext, context)}

Create a new context that includes all processes in the old context.
The rank of the processes in the previous context is preserved.  The call must
be executed by all processes in the old context.  It is a blocking call:  No
call returns until all processes have called the function.
The parameters are

\begin{description}
\item[OUT newcontext]  handle to newly created context.  The handle should not
be associated with an object before the call.
\item[IN context] handle to old context
\end{description}

\discuss{
I considered adding a string parameter, to provide a unique identifier
to the next context.  But, in an environment where processes are single
threaded, this is not much help:  Either all processes agree on the order they
create new contexts, or the application deadlocks.  A key may help in an
environment where processes are multithreaded, to distinguish call from distinct
threads of the same process; but it might be simpler to use a mutex algorithm at
each process.

{\bf Implementation note:}  No communication is needed to create a new context,
beyond a barrier synchronization; all processes can agree to use the same naming
scheme for successive copies of
the same context.  Also, no new rank table is needed, just a new context label
and a new pointer to the same old table.
}

{\bf \ \\ MPI\_NEW\_CONTEXT(newcontext, context, key, index)}

\begin{description}
\item[OUT newcontext] handle to newly created context at calling process.   This
handle should not be associated with an object before the call.
\item[IN context] handle to old context
\item[IN key] integer
\item[IN index] integer
\end{description}

A new context is created for
each distinct value of {\tt key}; this context is shared by all processes that
made the call with this key value.  Within each new context the processes are
ranked according to the order of the {\tt index} values they provided; in case
of ties, processes are ranked according to their rank in the old context.

This call is blocking:  No call returns until all processes in the old context
executed the call.

Particular uses of this function are:

(i) Reordering processes:  All processes provide the same {\tt key} value, and
provide their index in the new order.

(ii) Splitting a context into subcontexts, while preserving the old relative
order among processes:  All processes provide the same {\tt index} value, and
provide a key identifying their new subcontext.

{\bf \ \\ MPI\_RANK(rank, context)}

\begin{description}
\item[OUT rank] integer
\item[IN context] context handle
\end{description}

Return the rank of the calling process within the specified context.

{\bf \ \\ MPI\_SIZE(size, context)}

\begin{description}
\item[OUT size] integer
\item[IN context] context handle
\end{description}

Return the number of processes that belong to the specified context.

\subsection{Usage note}

Use of contexts for libraries:  Each library may provide an initialization
routine that is to be called by all processes, and that generate a context for
the use of that library.

Use of contexts for functional decomposition:  A harness program, running in the
context {\tt ALL} generates a subcontext for each module and then starts the
submodule within the corresponding context.

Use of contexts for collective communication:  A context is created for each
group of processes where collective communication is to occur.

Use of contexts for context-switching among several parallel executions:  A
preamble code is used to generate a different context for each execution; this
preamble code needs to use a mutual exclusion protocol to make sure each thread
claims the right context.

\discuss{
If process handles are made explicit in MPI, then an additional function needed
is {\bf MPI\_PROCESS(process, context, rank)}, which returns a handle to
the process identified by the {\tt rank} and {\tt context} parameters.

A possible addition is a function of the form  {\bf
MPI\_CREATE\_CONTEXT(newcontext, list\_of\_process\_handles)} which creates a
new context out of an explicit list of members (and rank them in their order of
occurrence in the list).  This, coupled with a mechanism for requiring the
spawning of new processes to the computation, will allow to create a new
all inclusive context that includes the additional processes.  However, I oppose
the idea of requiring dynamic process creation as part of MPI.  Many
implementers want to run MPI in an environment where processes are statically
allocated at load-time.
}

%
% END "Proposal I"
%======================================================================%
%\end{document}
%\documentstyle{report}
%

\chapter{Proposal VII --- Lyndon~J~Clarke \& Rik~J~Littlefield}

%----------------------------------------------------------------------
% Introduction

\section{Introduction}

This chapter is similar in basic principles to Proposal~I and includes
all of the functionality of that proposal as a subset --- it extends
in several ways and differs in some details. Certain features of
other, now defunct, proposals discussed in the context subcommittee
are included.  In particular, this chapter proposes that:

\begin{enumerate}

\item
Contexts and groups are not identical.  A context is always
associated with one group, but a group may have several
contexts. Properties of groups are inherited by all of the
associated contexts, for example process rank.

\item
Context and group descriptors can be
explicitly transferred to processes that are not members
of the context or group.

\item
In point-to-point messages, processes can be identified in
any of three ways: by process, by rank in a shared context,
or by ranks in separate sender and receiver contexts.

\item
A ``cache'' facility is provided that allows modules to attach
arbitrary information to both contexts and groups.

\end{enumerate}

These extensions are somewhat independent of each other.  The first
reflects the observation that multiple modules often operate within
each process group, so that context formation should be lighter weight
than group formation.  The second and third together provide
expressive support for communication between modules within different
groups of processes.  The fourth allows modules to be significantly
faster in common cases, without complicating their interface to the
application.

Much of this proposal must be viewed as recommendations to other
subcommittees of {\sc mpi}, primarily the point-to-point communication
subcommittee and the collective communications subcommittee.  Concrete
syntax is given in the style of the ANSI C host language, only for
purposes of discussion.

%----------------------------------------------------------------------
% Processes

\section{Processes}

This proposal views processes in the familiar way, as one thinks of
processes in Unix or NX for example.  Each process is a distinct space
of instructions and data.  Each process is allowed to compose multiple
concurrent threads and {\sc mpi} does not distinguish such threads.

\subsection*{Process Identifier}

Each process is identified by a process-local {\it process handle},
which is a reference to a {\it process descriptor} of undefined size
and opaque structure.  In a static process model process handles can
be obtained by mapping from a group (or context) and rank.  In a
future extension for dynamic processes, handles may be returned by
process creation functions.

{\sc mpi}  provides a procedure which returns a handle for the calling process.
\begin{verbatim}
process = mpi_my_process()
\end{verbatim}

\subsection*{Process Creation \&  Destruction}

This proposal makes no statements regarding creation and destruction
of processes.

{\sc mpi} provides facilities for descriptor transmission allowing the user
to explicitly transfer a process decriptor from one process to
another. These facilities are described below.

%----------------------------------------------------------------------
% Groups

\section{Process Groups}

This proposal views a process group as an ordered collection of
(references to) distinct processes, the membership and ordering of
which does not change over the lifetime of the group. The canonical
representation of a group is a one-to-one map from the integers $(0,
1, \ldots, N-1)$ to handles of the $N$ processes composing the group.

There may be structure associated with a process group defined by a
process topology.  This proposal makes no further statements regarding
such structures.

\subsection*{Group Identifier}

Each group is identified by a process-local {\it group handle},
which is a reference to a {\it group descriptor} of 
undefined size and opaque structure. 

The initialization of {\sc mpi} makes each process a member of the
``initial'' group. {\sc mpi} provides a procedure that returns a handle to
this group.  
\begin{verbatim}
group = mpi_initial_group()
\end{verbatim}

{\sc mpi} provides facilities for descriptor transmission allowing the
user to explicitly transfer a group descriptor from one process to
another. 

\subsection*{Group Creation and Deletion}

{\sc mpi} provides facilities which allow users to dynamically create
and delete process groups.  The
procedures described here generate groups which are static in
membership.

{\sc mpi} provides a procedure which allows users to create one or
more groups which are subsets of existing groups. 
\begin{verbatim}
groupb = mpi_group_partition(groupa, key)
\end{verbatim}
This procedure creates one or more new groups {\tt groupb} which are
distinct subsets of an existing group {\tt groupa} according to the
supplied values of {\tt key}.  This procedure is called by and
synchronises all members of {\tt groupa}.

{\sc mpi} provides a procedure which allows users to create a group by
permutation of an existing group. 
\begin{verbatim}
groupb = mpi_group_permutation(groupa, rank)
\end{verbatim}
This procedure creates one new group with the same membership as {\tt
groupa} with a permutation of process ranking, and returns the created
group descriptor in {\tt groupb}.  It is called by and synchronises all
members of {\tt groupa}.

{\sc mpi} provides a procedure which allows users to create a group by
explicit definition of its membership as a list of process handles.
\begin{verbatim}
group = mpi_group_definition(listofprocess)
\end{verbatim}
This procedure creates one new group {\tt group} with membership and
ordering described by the process handle list {\tt listofprocess}.  It
is called by and synchronises all processes identified in {\tt
listofprocess}.

{\sc mpi} provides a procedure which allows users to delete user
created groups.
\begin{verbatim}
mpi_group_deletion(group)
\end{verbatim}
This procedure deletes an existing group {\tt group}. It is called by and
synchronises all members of {\tt group}.

{\sc mpi} may provide additional procedures which allow users to
construct process groups with a process group topology.

\subsection*{Group Attributes}

{\sc mpi} provides a procedure which accepts a valid group handle
and returns the rank of the calling process within the identified
group.
\begin{verbatim}
rank = mpi_group_rank(group)
\end{verbatim}

{\sc mpi} provides a procedure which accepts a valid group handle
and returns the number of members, or {\it size}, of the identified
group.  
\begin{verbatim}
size = mpi_group_size(group)
\end{verbatim}

{\sc mpi} provides a procedure which accepts a valid group handle
and process order number, or {\it rank}, and returns the valid
process handle to which the supplied rank maps within the
identified group.  
\begin{verbatim}
process = mpi_group_process(group, rank)
\end{verbatim}

{\sc mpi} may provide additional procedures which allow users to
determine the process group topology attributes.

{\sc mpi} provides a group descriptor cache facility which allows the
user to attach attributes to group descriptors.

%----------------------------------------------------------------------
% Contexts

\section{Communication Contexts}

This proposal views a communication context as the combination of a
process group and a protection mechanism that avoids collision between
messages sent to different contexts.  The context inherits process
ranking from its associated group, referred to as a {\it frame}.  Each
process group may be used as a frame for multiple contexts.

\subsubsection*{Context Identifier}

Each context is identified by a process-local {\it context handle},
which is a reference to a {\it context descriptor} of 
undefined size and opaque structure.

The creation of a process group allocates a {\it base
context} which inherits the created group as a frame and can be
thought of as an attribute of the created group.  {\sc mpi} provides
a procedure which accepts a valid group handle and returns a
handle to the base context within the identified group.
\begin{verbatim}
context = mpi_base_context(group)
\end{verbatim}

{\sc mpi} provides facilities for descriptor transmission allowing the
user to explicitly transfer a context descriptor from one process to
another.

\subsubsection*{Context Creation and Deletion}

{\sc mpi} provides facilities which allows user to dynamically create
and delete contexts in addition to the base context associated with a
process group. Contexts created in this fashion can be thought of as
copies of the base context of the process group.

{\sc mpi} provides a procedure which allows users to create contexts.
This procedure accepts the handle of a group of which the calling
process is a member, and returns a handle to the new context.  
\begin{verbatim}
context = mpi_context_creation(group).  
\end{verbatim}
This procedure must be called loosely synchronously by all members of
{\tt group}.  The procedure may not actually synchronize the member
processes --- it is suggested that this is a lightweight procedure
that can be implemented so as to not require interprocess
communication.

{\sc mpi} provides a procedure which allows users to delete user
created contexts.  The procedure accepts a context handle
that was created by the calling process and deletes the identified
context.  
\begin{verbatim}
mpi_context_deletion(context)
\end{verbatim}
This procedure has the same synchronization behavior as context
creation.

\subsubsection*{Context Attributes}

{\sc mpi} provides a procedure which allows users to determine the
process group that is the frame of a context.  
\begin{verbatim}
group = mpi_context_frame(context)
\end{verbatim}

{\sc mpi} provides a group descriptor cache facility which allows user
to attach attributes to group descriptors.

%----------------------------------------------------------------------
% Descriptors

\section{Descriptor Facilities}

This section describes the descriptor transmission and user cache
facilities.

\subsection*{Transmission Facility}

{\sc mpi} provides a mechanism whereby the user can transmit a valid
descriptor in a message such that the received descriptor handle is
valid.  This can be integrated with the capability to transmit typed
messages, and it is suggested that a notional data type should be
introduced for this purpose, e.g.  {\tt MPI\_DSCR\_TYPE}. There are
other reasonable approaches to providing this facility.

The descriptor is translated as necessary to be meaningful on the
destination process, storage is allocated for it, and a handle to
that storage is returned. Decorations are not transmitted. 

Handles are guaranteed to be unique within each process --- if
processes A and B independently send to process C a descriptor for an
object D, then process C will get two copies of the same handle.  As
with all transfers of descriptors, the receiving process is
responsible for releasing the descriptor and its handle when it is no
longer needed or becomes stale. MPI provides a procedure which frees a
descriptor.
\begin{verbatim}
mpi_free_dscr(handle)
\end{verbatim}

A descriptor registry service which allows descriptors to be
identified by name would be a useful additional feature. This service
can be implemented at the user level using the point-to-point chapter
of {\sc mpi} and the descriptor transmission facilities. These
services can be deferred in this session of {\sc mpi}.

\subsection*{Cache Facility}

{\sc mpi} provides a ``cache'' facility that allows an application to
attach arbitrary pieces of information, called {\em decorations}, to
context and group descriptors.  Decorations are local to the process
and are not included if the descriptor is sent to another process.
This facility is intended to support optimizations such as saving
persistent communication handles and recording topology-based
decisions by adaptive algorithms.

{\sc mpi} provides the following services related to cacheing: 
\begin{description}
\item
[Generate key:] Generate cache key.
\begin{verbatim}
keyval = mpi_GetDecorationKey()
\end{verbatim}

\item
[Store decoration:] Store decoration in cache by key.
\begin{verbatim}
mpi_SetDecoration(handle, keyval, decoration_val, 
                   decoration_destructor_routine)
\end{verbatim}

\item
[Retrieve decoration:] Retrieve decoration from cache by key.
\begin{verbatim}
mpi_TestDecoration(handle,keyval,decoration)
\end{verbatim}

\item
[Delete decoration:] Delete decoration from cache by key.
\begin{verbatim}
mpi_DeleteDecoration(handle,keyval)
\end{verbatim}

\end{description}

Each decoration 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 aall contexts of a group after
the first call might look like this:

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

   efficient_global_op (context, ...)
   int context_handle;
   {
     struct gop_stuff_type *gop_stuff;   /* whatever we need */
     int group_handle = mpi_context_frame(context_handle);

     if (!gop_key_assigned)     /* get a key on first call ever */
     { gop_key_assigned = 1;
       if ( ! (gop_key = MPI_GetDecorationKey()) ) {
         MPI_abort ("Insufficient keys available");
       }
     }
     if (MPI_TestDecoration (group_handle,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_SetDecoration (group_handle, 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}
}

The cache facility could also be provided for process descriptors, but
it is less clear how such provision would be useful. It is suggested
that the cache store, retrieve and delete decoration procedures should
fail when applied to a process descriptor handle.

%----------------------------------------------------------------------
% Point-to-point

\section{Point-to-Point Communication}

This proposal recommends three forms for {\sc mpi} point-to-point
message addressing and selection: null context; closed context; open
context. It is further recommended that messages communicated in each
form are distinguished such that a {\tt Send} operation of form X
cannot match with a {\tt Receive} operation of form Y, requiring that
form is embedded into the message envelope.

The three forms are described, followed by considerations of uniform
integration of these forms in the point-to-point communication chapter
of {\sc mpi}.

\subsection*{Null Context Form}

The {\it null context\/} form contains no message context.  Message
selection and addressing are expressed by
\begin{verbatim}
(process, tag)
\end{verbatim}
where: {\tt process} is a process handle; {\tt tag} is a message tag.

{\tt Send} supplies the {\tt process} of the receiver.  {\tt Receive}
supplies the {\tt process} of the sender.

{\tt Receive} can wildcard on {\tt process} by supplying the wildcard
descriptor handle value {\tt MPI\_WILDCARD}. In this case the receiver
may have obtained the process descriptor of the sender, and the null
descriptor handle {\tt MPI\_NULL} is returned in the relevant
point-to-point enquiry procedure.

\subsection*{Closed Context Form}

The {\it closed context\/} form permits communication between members
of the same context.  Message selection and addressing are expressed
by
\begin{verbatim}
(context, rank, tag)
\end{verbatim}
where: {\tt context} is a context handle; {\tt rank} is a process rank
in the frame of {\tt context}; {\tt tag} is a message tag. The calling
process must be a member of the frame of {\tt context}.

{\tt Send} supplies the {\tt context} of the receiver (and sender),
and the {\tt rank} of the receiver.  {\tt Receive} supplies the {\tt
context} of the sender (and receiver), and the rank of the sender.
The {\tt (context, rank)} pair in {\tt Send} ({\tt Receive}) is
sufficient to determine the process identifier of the receiver
(sender).

{\tt Receive} cannot wildcard on {\tt context}.  {\tt Receive} can
wildcard on {\tt rank} by supplying the wildcard integer {\tt
MPI\_DONTCARE}. This proposal makes no statement about the provision
for wildcard on {\tt tag}.

\subsection*{Open Context Form}

The {\it open context\/} form permits communication between members of
any two contexts.  Message selection and addressing are expressed by
\begin{verbatim}
(lcontext, rcontext, rank, tag)
\end{verbatim}
where: {\tt lcontext} is a context handle; {\tt rcontext} is a context
handle; {\tt rank} is a process rank in the frame of {\tt rcontext};
{\tt tag} is a message tag. The calling process must be a member of
the frame of {\tt lcontext} and need not be a member of the frame of
{\tt rcontext}.

{\tt Send} supplies the context of the sender in {\tt lcontext}, the
context of the receiver in {\tt rcontext}, and the {\tt rank} of the
receiver in the frame of {\tt rcontext}.  {\tt Receive} supplies the
context of the receiver in {\tt lcontext}, the context of the sender
in {\tt rcontext}, and the {\tt rank} of the sender in the frame of
{\tt rcontext}.  The {\tt (rcontext, rank)} pair in {\tt Send} ({\tt
Receive}) is sufficient to determine the process identifier of the
receiver (sender).

{\tt Receive} cannot wildcard on {\tt lcontext}. {\tt Receive} can
wildcard on {\tt rcontext} by supplying the wildcard descriptor handle
value {\tt MPI\_WILDCARD}, in which case it must also wildcard on {\tt
rank} since the process descriptor of the sender cannot be determined.
In this case the receiver may not have obtained the context descriptor
of the sender, and the null descriptor handle {\tt MPI\_NULL} is
returned in the relevant point-to-point enquiry procedure.  {\tt
Receive} can wildcard on {\tt rank} by supplying the wildard intger
value {\tt MPI\_DONTCARE}. 

\subsection*{Uniform Integration}

The three forms of addressing and selection described have different
syntactic frameworks.  We can consider integrating these forms into
the point-to-point chapter of {\sc mpi} by defining a further
orthogonal axis (as in the multi-level proposal of Gropp \& Lusk)
which deals with form.  This is at the expense of multiplying the
number of {\tt Send} and {\tt Receive} procedures by a factor of
three, and some further but trivial work with details of the current
point-to-point chapter which uniformly assumes a single addressing and
selection form.

There are various approaches to unification of the syntactic
frameworks which may simplify integration.  Two options are now
described, each based on retention and extension of the framework of
the closed and open contexts forms.

The framework of the open context form could be adopted and extended.
The null context form is expressed as {\tt (MPI\_NULL, MPI\_NULL,
process, tag)}, which is a little clumsy.  The closed context form is
expressed as {\tt (MPI\_NULL, context, rank, tag)}, which is
marginally inconvenient.  The open context form is expressed as {\tt
(lcontext, rcontext, rank, tag}), which is of course natural.

The framework of the closed context form could be adopted and
extended.  The null context form is expressed as {\tt (MPI\_NULL,
process, tag)}, which is marginally inconvenient, and requires that
descriptor handles are expressed as intgers.  The closed context form
is expressed as {\tt (context, rank, tag)}, which is of course
natural.  Expression of the open context form requires a little more
work.  We can use the {\tt context} field as ``shorthand notation''
for the {\tt (lcontext, rcontext)} pair at the expense of introducing
some trickery.  We define a ``duplet descriptor'' which is formally
composed of two references to contexts, and provide a procedure which
constructs such a descriptor given two context descriptors.  Both {\tt
Send} and {\tt Receive} accept a duplet descriptor in {\tt context},
are able to distinguish the duplet descriptor from a singlet
descriptor, and treat the duplet as shorthand notation.  It is
conjectured that using this framework is the best choice for {\sc
mpi}.

%----------------------------------------------------------------------
% Point-to-point

\section{Collective Communication}

Symmetric collective communication operations are compliant with the
closed context form described above.  This proposal recommends that
such operations accept a context descriptor which identifies the
context (thus frame) in which they are to operate.

{\sc mpi} does plan to describe symmetric collective communication
operations.  It is not possible to determine whether this proposal is
sufficient to allow implementation of the collective communication
chapter of {\sc mpi} in terms of the point-to-point chapter of {\sc
mpi} without loss of generality, since the collective operations are
not yet defined.

Asymmetric collective communication operations, especially those in
which sender(s) and receiver(s) are distinct processes, are compliant
with the open context form described above.  This proposal recommends
that such operations accept a pair of context descriptors (a duplet
descriptor) which identify the contexts (thus frames) in which they
are to operate.

{\sc mpi} does not plan to describe asymmetric collective
communication operations.  Such operations are expressive when writing
programs beyond the SPMD model, which are composed of communicative
functionally distinct process groups.  These services can be deferred
in this session of {\tt mpi}.

%----------------------------------------------------------------------
% Conclusion

\section{Conclusion}

This chapter presented a proposal for communication contexts and
process groups with {\sc mpi}. In the proposal process groups are
created dynamically and are static in membership. Associated with each
process group are one or more communication contexts which inherit
process ranking.

The recommendations for point-to-point communication are powerful. The
proposal provides process addressed communication which occurs within
an extended context. The proposal also contains closed context
communication addressed in terms of context and rank which protects
messages belonging to one context from those belonging to other
contexts. The proposal also contains open context communications
adressed in terms of sender context, receiver context, and process
rank which provides expressive power for intercommunication between
modules within different groups.

The proposal is extensible to a number of features which might be
included in future sessions of {\sc MPI}, for example: dynamic
processes; dynamic groups; multiple group collective communications.

%
% END "Proposal VII"
%======================================================================%

%
% BEGIN "Proposal III"
% Anthony Skjellum
% March 1993
%
\chapter{Proposal III - A.~Skjellum {\em et al.}}

%----------------------------------------------------------------------
% Introduction

\section{Introduction}

This chapter takes a slightly different approach to contexts
and groups, than does Proposal~VII.  It is of roughly equal
conceptual ``power'' as Proposal~VII, with some differences.
As appropriate, this chapter borrows directly from Proposal~VII, by
Clarke and Littlefield.

\begin{enumerate}

\item
Contexts are supported to discriminate between messages in the
system.  A context is a conceptual extension of the tag space
into a system-defined part (not wildcardable), and a  totally
user-defined part (the traditional 32-bit tag).  

\item
A context is a lower-level concept than a group, so that
contexts not associated with groups are permitted.  This
permits the user to develop codes that build on the server
model, or which build up groups dynamically (not otherwise
supported by MPI1).

\item
Groups are used to describe cooperative communication in the system.
Groups have one or more context of communication associated with them.
When created, a group is given a context of communication.

\item
Context and group descriptors can be explicitly transferred to
processes that are not members of the context or group.

\item
In point-to-point messages, processes can be identified in
either of two ways: by opaque process identifier, or by rank in a group;
in either case, communication scope is within a given context.

\item
The cache facility, allowing groups to add additional information
(described in Proposal~VII) is embraced by this Proposal, with
reservations as noted.  The possible need to omit this cacheing
feature from MPI1 should not invalidate the remainder of Proposal~VII
from further consideration (severability).

\end{enumerate}

%----------------------------------------------------------------------
% Processes

\section{Processes}

This Proposal views processes in the familiar way, as one thinks of
processes in Unix or NX for example.  Each process is a distinct space
of instructions and data.  Each process is allowed to compose multiple
concurrent threads and {\sc MPI\/} does not distinguish such threads.
{\sc MPI\/} shall be thread-aware, but not thread supporting, so
we make every attempt to make thread safe programs possible in
defining what follows.

\subsection*{Process Identifier}

Each process is identified by an opaque process identifier,
which is associable to a {\it process descriptor} of undefined size
and opaque structure, through {\sc MPI} accessor
calls.  In a static process model process identifiers can
be obtained by mapping from a group and rank.  In a
future extension for dynamic processes, identifiers may be returned by
process creation functions.

{\sc MPI}  provides a procedure that returns 
an identifier for the calling process.
\begin{verbatim}
    my_process = mpi_my_process()
\end{verbatim}
This identifier can be converted to a transmittable form by
{\sc MPI} converter functions, though opaque,
it is conceptually a pointer.

\subsection*{Process Creation \&  Destruction}

This proposal makes no statements regarding creation and destruction
of processes.  

{\sc MPI} provides facilities for identifier transmission allowing the user
explicitly to transfer a process identifier from one process to
another. These facilities are described below.  MPI also provides
means to transfer underlying information about the opaque process
descriptor underlying.

%----------------------------------------------------------------------
% Groups

\section{Process Groups}

This proposal views a process group as an ordered collection of
distinct processes (via process identifiers), the membership and ordering of
which does not change over the lifetime of the group. The canonical
representation of a group is a one-to-one map from the integers $(0,
1, \ldots, N-1)$ to identifiers of the $N$ processes composing the group.

There may be structure associated with a process group defined by a
process topology.  This proposal makes no further statements regarding
such structures.

There may be non-enumerative ways to construct and manipulate special
groups, or for special machine architectures ({\em e.g.}, cohorts).
This proposal makes no further statements about such special groups,
other than the desirability of avoiding group-name enumeration, when
possible.

\subsection*{Group Identifier}

Each group is identified by an opaque  {\it group identifier},
which is a associable to a {\it group descriptor} of 
undefined size and opaque structure, through {\sc MPI} accessor
functions. 

The initialization of {\sc MPI} makes each process a member of the
``initial'' group. {\sc MPI} provides a procedure that returns an
identifier to this group.  
\begin{verbatim}
    group_ident = mpi_initial_group()
\end{verbatim}

{\sc MPI} provides facilities for descriptor transmission allowing the
user explicitly transfer a group descriptor from one process to
another. 

\subsection*{Group Creation and Deletion}

{\sc MPI} provides facilities which allow users dynamically to create
and delete process groups.  The procedures described here generate
groups which are static in membership.

{\sc mpi} provides a procedure that allows users to create one or
more groups which are subsets of existing groups. 
\begin{verbatim}
  new_group = mpi_group_partition(old_group, key)
\end{verbatim}
This procedure creates one or more new groups {\tt new\_group} which are
distinct subsets of an existing group {\tt old\_group} according to the
supplied values of {\tt key}.  This procedure is called by and
synchronises all members of {\tt new\_group}.  No overlapping is
permitted, so that exactly one {\tt new\_group} is achieved in each
{\tt old\_group} process.  The new groups have new contexts
of communication.  The number of new contexts depends on the number
of different key values asserted.

{\sc MPI} provides a procedure which allows users to create a group by
permutation of an existing group. 
\begin{verbatim}
    new_group = mpi_group_permutation(old_group, rank)
\end{verbatim}
This procedure creates one new group with the same membership as {\tt
old\_group} with a permutation of process ranking, and returns the created
group descriptor in {\tt new\_group}.  It is called by and synchronises all
members of {\tt gha}.  The new group has a new context of communication.

{\sc MPI} provides a procedure that allows users to create a group by
explicit definition of its membership as a list of process identifiers.
\begin{verbatim}
    new_group = mpi_group_definition(array_of_process_ids,length,
			context_to_use)
\end{verbatim}
This procedure creates one new group {\tt new\_group} with membership and
ordering described by the process handle list {\tt array\_of\_process\_ids},
of length {\tt length}.  If {\tt context\_to\_use} 
is specified as the special context {\tt MPI\_GET\_CONTEXT}, then
the system allocates the new context.  Else, the system trusts
the user to have allocated the context legally (see below).
This procedure must be
called by and synchronises all processes identified in 
the list.    A further approach to new group definition is as follows
\begin{verbatim}
    new_group = mpi_group_def_by_leader(leader_id, in_length,
                        in_array_of_process_ids, context_to_use,
                        out_array_of_process_ids, out_length)
\end{verbatim}
This weaker form requires all future group members to have identified
only a leader (specified by {\tt leader\_id}).  The leader knows the
length a names of all participants.  This is a synchronization of all
participants.  Same semantics for {\tt context\_to\_use} as above.

{\sl MPI} provides a way formally to duplicate a group, in order
to obtain a separate context of communication.  This can be achieved
by using other operations, but this procedure allows optimization
in some implementations (no explicit group copy, for instance).
\begin{verbatim}
	new_group = mpi_group_duplicate(old_group)
\end{verbatim}
The only difference between the old and new groups is that there
is a new context of communication.

{\sc MPI} provides a procedure which allows users to delete user
created groups.
\begin{verbatim}
    mpi_group_deletion(group)
\end{verbatim}
This procedure deletes an existing group {\tt group}. It is called by and
synchronises all members of {\tt group}.

{\sc MPI} may provide additional procedures which allow users to
construct process groups with a process group topology. 

\subsection*{Group Attributes/Accessors}

{\sc MPI} provides a procedure that accepts a valid group identifier
and returns the rank of the calling process within the identified
group.
\begin{verbatim}
    rank = mpi_group_rank(group)
\end{verbatim}

{\sc MPI} provides a procedure that accepts a valid group identifier
and returns the number of members, or {\it size}, of the identified
group.  
\begin{verbatim}
    size = mpi_group_size(group)
\end{verbatim}

{\sc MPI} provides a procedure that accepts a valid group identifier
{\it rank-in-group}, and returns the valid
process identifier to which the supplied rank maps within the
identified group.  
\begin{verbatim}
    process_id = mpi_group_process(group, rank)
\end{verbatim}

{\sc MPI} may provide additional procedures which allow users to
determine the process group topology attributes.

{\sc mpi} provides a group descriptor cache facility thath allows the
user to attach attributes to group descriptors.  See Proposal~VII
for details.

%----------------------------------------------------------------------
% Contexts

\section{Communication Contexts}

This proposal views a communication context as a partition of the
tag space, which is a protection mechanism that avoids collision between
messages sent between processes.   Process groups have one or more
contexts in {\sl MPI}.  Unlike Proposal~VII, more contexts are
obtained for a group using the above-discussed group creation
and replication functions.  Replication may only be formal for
good implementations.  This approach is viewed as simpler than
what Proposal~VII describes.

\subsubsection*{Context Identifier}

Each context is identified by an opaque process identifier.  It
is conceptually an integer assigned by the system to partition
a large tag space into a user-defined and system-controlled
subspaces.  This stategy provides the minimal level of 
isolation needed to build large libraries, and is close to practice.

\subsubsection*{Context Creation and Deletion}

{\sc MPI} provides facilities that allow user dynamically to 
allocate and free contexts.  When contexts are used with groups,
these calls are not needed.  For more advanced users (such as
building your own dynamic groups), these calls will be used.
Above, where {\tt context\_to\_use} appears as an argument,
the following call would have been used to secure such a context
in advance.

\begin{verbatim}
    mpi_context_creation(number_of_contexts_wanted,array_of_contexts,
		number_of_contexts_provided)  
\end{verbatim}
This call is called by any process, with no synchronization to other
processes.

{\sc MPI} provides a procedure that allows users to delete user-
created contexts.  The procedure accepts a context identifier array,
containing 
zero or more contexts created previously in the system.
\begin{verbatim}
    mpi_context_deletion(context_array,length)
\end{verbatim}
No synchronization occurs here.  The user can do erroneous things
by freeing contexts that are still in use.

For general applications, it may be nice to have a name service
for contexts  (necessary for building dynamic groups and servers,
for yourself).  Herewith:
\begin{verbatim}
    mpi_associate_contexts_with_name(string_name,context_array,length)
    mpi_disassociate_contexts_with_name(string_name)
    mpi_get_contexts_by_name(string_name,max_length,out_length,
                context_array
\end{verbatim}
As with context generation, the above calls assume a simple
reactive, global server, or shared name space mechanism (both
achieveable easily in  practice).
%----------------------------------------------------------------------
% Descriptors

\section{Descriptor Facilities}

This section describes the descriptor transmission and user cache
facilities.

\subsection*{Conversion Facility}

{\sc MPI} provides a mechanism whereby the user can convert a valid
descriptor ({\em e.g.}, a group descriptor) idenfied through an identifier
({\em e.g.}, a group identifier) for use 
in a message such that the received descriptor can be reconstructed
on the remote end.  This can be integrated with message transmission
as the user sees fit, without additional complication to the
send/receive semantics of {\sc MPI}.
An example follows:
\begin{verbatim}
    error = mpi_group_group_transmit(group, group_buffer,
         max_length, act_length)	
\end{verbatim}
If the buffer is not long enough to hold the information, an error
occurs.  A network independent format can be assumed in the 
{\tt group\_buffer}.  Cached ``attributes'' are not transmitted
(see below).

\subsection*{Cache Facility}

{\sc MPI} provides a ``cache'' facility that allows an application to
attach arbitrary pieces of information, called {\em attributes}, to
context and group descriptors.  Attributes are local to the process
and are not included if the descriptor is sent to another process.
This facility is intended to support optimizations such as saving
persistent communication handles and recording topology-based
decisions by adaptive algorithms.

{\sc MPI} provides the following services related to cacheing.  We
call our attributes `attributes'; Proposal~VII calls them (equivalently)
decorations (no big difference, except naming, is anticipated).
\begin{description}
\item
[Generate key:] Generate cache key.
\begin{verbatim}
keyval = mpi_get_attribute_key()
\end{verbatim}

\item
[Store attribute:] Store attribute in cache by key.
\begin{verbatim}
mpi_set_attribute(handle, keyval, attribute_val, 
                   attribute_destructor_routine)
\end{verbatim}

\item
[Retrieve attribute:] Retrieve attribute from cache by key.
\begin{verbatim}
mpi_Test_Attribute(handle,keyval,attribute)
\end{verbatim}

\item
[Delete attribute:] Delete attribute from cache by key.
\begin{verbatim}
    mpi_delete_attribute(handle,keyval)
\end{verbatim}

\end{description}

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.  Our example will appear in a later
draft, because we have semantic differences from some of
the ancillary aspects of the example
of Proposal~VII.

The cache facility could also be provided for process identifiers, but
it is less clear how such provision would be useful. It is suggested
that the cache store, retrieve and delete attribute procedures should
fail when applied to a process identifiers.

Implementations should use AVL trees, or similar efficient data
structures to provide relatively efficient access to attributes.

%----------------------------------------------------------------------
% Point-to-point

\section{Point-to-Point Communication}

This proposal recommends two forms for {\sc MPI} point-to-point
message addressing and selection: by-group notation, by process-ID
notation; always, one is working in a context, as this is the
fundamental management tactic of {\sc MPI} for messages.  As a
group always has a context at creation, and an ALL group is
anticipated, this should prove fine for a static process model.
We disagree significantly from Proposal~VII in what follows.

The two forms are described, followed by considerations of uniform
integration of these forms in the point-to-point communication chapter
of {\sc MPI}.

\subsection*{Group-Rank Form}
The {\it group-rank\/} form permits communication between members
of the same context and group.  Message selection and addressing are expressed
by
\begin{verbatim}
(group, rank, tag)
\end{verbatim}
where: {\tt group} is a group identifier; {\tt rank} is a process rank
in that group; {\tt tag} is a message tag. The calling
process must be a member of the frame of {\tt context}.

{\tt Send} determines the context using information in the group
identifier.  It does all necessary mappings to the process identifier
space.  {\tt Receive} cannot wildcard on context, so
a valid matching receive must refer to the same group information. 
{\tt Receive} can
wildcard on {\tt rank} by supplying the wildcard integer {\tt
MPI\_DONTCARE}. This proposal makes the
following statement about the provision
for wildcard on {\tt tag}.  Two integer-form wildcard is needed
for layering: {\tt care\_bits}, {\tt dont\_care\_bits}.  Tags
are matched if and only if 
\begin{equation}
(received\_tag AND NOT dont\_care_bits) XOR care\_bits== 0
\end{equation}
This general format can be used to partition the tag space for
virtual topologies or other user-defined needs, and is quite important
to the standard's flexibility.

\subsection*{Process-Identifier Form}
Communication takes place using the following parameters:
\begin{verbatim}
(context, process_identifier, tag)
\end{verbatim}
where: {\tt context} is a context identifier,
{\tt process\_identifier} is a process identifier,
{\tt tag} is a message tag. The calling process must be a member of
the same context as the recipient.  There is no reference to groups
here.  Contexts can have been shared by using a least common
ancestor prior to this call, or by the above-mentioned context
naming service.  

There is never wildcarding on context.  Wildcarding on
{\tt process\_identifier} is through {\tt MPI\_DONTCARE}.  Tag
wildcarding is through the integer pair described above.

\subsection*{Uniform Integration}

The two forms of addressing and selection described have different
syntactic frameworks.  We can consider integrating these forms into
the point-to-point chapter of {\sc MPI} by defining a further
orthogonal axis (as in the multi-level proposal of Gropp \& Lusk)
which deals with form.  This is at the expense of multiplying the
number of {\tt Send} and {\tt Receive} procedures by a factor of
two, and some further but trivial work with details of the current
point-to-point chapter which uniformly assumes a single addressing and
selection form.  No further details, other than naming that
disambiguates the rank-group form from the process-id-context form
is really needed, and the naming would seem uncontroversial.

%----------------------------------------------------------------------
% Collective

\section{Collective Communication}

Symmetric collective communication operations are compliant with the
group-rank form described above.  This proposal recommends that
such operations accept a group-identifier  (which contains
context and other information) needed to operate correctly.
We recommend that the tag argument be included in collective
calls where this could help with debugging.

{\sc MPI} does plan to describe symmetric collective communication
operations.  It is impossible to determine whether this proposal is
sufficient to allow implementation of the collective communication
chapter of {\sc MPI} in terms of the point-to-point chapter of {\sc
mpi} without loss of generality, since the collective operations are
not yet defined.

Asymmetric collective communication operations, especially those in
which sender(s) and receiver(s) are distinct processes, 
should be made compliant
with the group-rank form described above.

{\sc MPI1} should forego non-blocking collective operations, but
ask vendors to support thread models in lieu of such operations.

%----------------------------------------------------------------------
% Conclusion

\section{Conclusion}

This proposal is substantially simpler than Proposal~VII, while
incorporating many of its finer elements, specifically the ability
to cache attributes, which would let users extend the usefulness
of groups, in their applications.  It places groups as conceptually
higher objects than contexts, and removes a lot of the framework
needed by Proposal~VII to accomplish inter-group transfers, by
providing context-process-identifier communication and group-rank
communication.  Through a simple context management server, and
name registry server, dynamic groups support becomes simple, and
synchronizations via least-common ancestors becomes avoidable.

Compared to Proposal~I, we have offered a more convenient process
model, because contexts are seen clearly to partition and manage
the tag space, whereas groups are seen as ways to describe collective
operations, and attributes of cooperative communication.  This offers
a much more open interface an either VII or I, including a legitimate
ability to do server-like computation.  However, a simple, reactive
server is needed to accomplish these services.  Arguably, this
server would also be needed in Proposal~VII, though not in Proposal~I.

%
% END "Proposal VI"
%======================================================================%
\end{document}