From: "Marc Snir" <[email-masked]>
Date: Sun, 14 Mar 93 22:09:34 EST

\documentstyle[12pt]{article}

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

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

\begin{document}

\title{
        Point to Point Communication
}

\author{Marc Snir \\ William Gropp and Ewing Lusk}
\maketitle
\section{Point to Point Communication}
\subsection{Introduction}

This section is a draft of the current proposal for point-to-point
communication.  It does not yet include a description of the Fortran 77
and C bindings.

I have tried to indicate, wherever appropriate, gaps and unresolved issues,
using small type.

\discuss{
The following subsections of the introduction contain general information
on the design of MPI procedures.   The material should be moved to a general
introduction for the entire document.
}

\subsection{Data Types}

\subsubsection{Handle}

MPI procedures use at various places {\em handles}.  Handles
are used to access opaque objects.  Such object
can be created, updated and destroyed only by by calling suitable MPI
procedures, and providing the handle as parameter. Opaque
objects hide from the user the internal representation used for
various
MPI objects, thus allowing to have similar calls in C and Fortran, allowing to
overcome problems with the typing rules in these languages, and allowing for
future extension of their functionality.  Handles are of type {\tt
void *} in C and of type {\tt integer} in Fortran.

An opaque object can be {\em persistent} or {\em ephemeral}.  A persistent
object persists until destroyed by an explicit operation.  An ephemeral object
is good for a single use; thus an ephemeral object associated with a
communication operation disappears once this operation is completed (or once
this object is not needed anymore for the completion of the operation).

An opaque object is created by a call to {\tt MPI\_CREATE}, and
destroyed by a call to {\tt MPI\_FREE}.  Additional MPI functions are
available to create, access and update specific opaque objects.

{\bf \ \\ MPI\_CREATE(handle, type, persistence)}
\begin{description}
\item[OUT handle] handle to object
\item[IN type] state value that identifies the type of object to be created
(e.g., {\tt MPI\_COMMUNICATION, MPI\_BUFFER, MPI\_CONTEXT}, etc.).
\item[IN persistence] state value; either {\tt MPI\_PERSISTENT} or {\tt
MPI\_EPHEMERAL}.
\end{description}

{\bf \ \\ MPI\_FREE(handle)}
\begin{description}
\item[IN handle] handle to object
\end{description}

An object can be destroyed only if there is no pending operation that is using
this object; after successful return of the routine, the handle is undefined.

{\bf \ \\ MPI\_ASSOCIATED(handle, type)}
\begin{description}
\item[IN handle] handle to object
\item[OUT type] state
\end{description}

Returns the type of the object the handle is currently associated with, if
such exists.  Returns the special type {\tt MPI\_NULL} if the handle is
not currently associated with any object.

MPI may provide predefined opaque objects and predefined, static handles to
these objects.  Such objects may not be destroyed.

\paragraph*{List of handles}
An MPI call may need a parameter that is a {\em list of handles}.  In C, such
list will be a record with one component being the length of the list, the other
components being an array of pointers.  In Fortran, the list will be an array of
integers, the first one of which is the length of the list.

\discuss{
The mechanism for opaque objects used here follows the POSIX Fortran binding
standard.  An alternative choice is to have different type declarations for each
type of opaque object.  Then, opaque objects are created/destroyed like regular
variables, rather than by MPI calls; they are still accessed and updated only
via MPI functions.

}

\subsubsection{State}

MPI procedures use at various places arguments with {\em state} types.  The
values of such data type are all identified by names, and no operation is
defined on them. For example, the {\tt MPI\_CREATE} routine has a
state type parameter with values {\tt MPI\_PERSISTENT} and {\tt MPI\_EPHEMERAL}.

An {\tt enumeration} declared in an included MPI.h file will be used in C for
state datatypes.   The Fortran 77 mechanism needs to be decided.

\discuss{
Named integer constants can be used in Fortran 90, using the {\tt
PARAMETER} mechanism.  The constant declarations can be made available via an
{\tt INCLUDE} file.
Fortran 77 does not seem to offer any convenient mechanism.  One possibility is
to specify explicit integer values, and allow the use of named constants with
those Fortran 77 compilers that support them conveniently.  Another possibility
is to use character strings, rather than integers.
}

\subsubsection{Named constants}

MPI procedures sometimes assign a special meaning to a special value of a
basic type parameter; e.g. {\tt tag} is an integer valued parameter of
point-to-point communication operations, with a special {\tt DONTCARE} value.
Such parameters will have a range of regular values, which is a proper
subrange
of the range of values of the corresponding basic type; special values (such as
DONTCARE) will be outside the regular range.   The range of regular values can
be queried, and sometimes set, using environment inquiry or environment setting
functions (Section~\ref{sec:inquiry}).   The special values are provided by
named constant, that are made available via an MPI.h include file in a C
binding.

\discuss{

Need to agree on a Fortran mechanism for named constants (see the
discussion above).

Implementers should try to detect illegal uses of ``special values''.  Thus,
the use of the {\tt DONTCARE} value to tag a message sent should be flagged as
an error.

}

\subsubsection{Choice}

MPI functions sometimes use parameters with a {\em choice} (or union) data
type.  I.e., distinct calls to the same routine may pass by reference actual
parameters of different types. The mechanism for providing such
parameters will differ from language to language.  In C, a formal
parameter of type {\tt void *} will be used, with an actual pointer parameter.
in Fortran, we shall cheat.

\discuss{

The Fortran 77 standard specifies that the type of actual arguments need to
agree with the type of dummy arguments; no construct equivalent to C pointers is
available.  Thus, it would seem that there is no standard conforming mechanism
to support choice parameters.
However, most Fortran compiler either don't check type
consistency of calls to external routines, or support a special mechanism to
link foreign (e.g., C) routines.  I suggest that we accept this nonconformity
with Fortran 77 standard.  I.e., we accept that the same routine may be passed
an actual parameter of a different type at distinct calls.

Generic routines can be used in Fortran 90 to provide a standard
conforming solution.  This solution will be consistent with our nonstandard
conforming Fortran 77 solution.

}

\subsection{Processes}

An MPI program is executed by several autonomous processes that execute each
their own code, in a MIMD style. The codes executed by each process need not be
identical.  The processes communicate via calls to MPI communication primitives.
Typically, each processor executes in its own address space, although
shared-memory implementations of MPI are possible.
This document specifies the behavior of a parallel program assuming that only
MPI calls are used for communication.  The interaction of an MPI program with
other possible means of communication (e.g., shared memory) is not specified.
In particular, it is assumed that message buffers at distinct
processors are disjoint.

MPI does not specify the execution model for each process.  A process can be
sequential, or can be multithreaded, with threads possibly executing
concurrently.  Care has been taken to make MPI ``thread-safe'', by avoiding the
use of implicit global states.

The initial allocation of processes to an MPI computation and their
binding to physical processors is not specified by the
program itself.  It is expected that vendors will provide mechanisms to do so
either at load time or at run time.   Such mechanisms will allow to specify
the initial number of required processes, the
code to be executed by each initial process, and the allocation of processes to
processors.  Also, the current proposal does not provide for dynamic creation or
deletion of processes during program execution, although it is intended to be
consistent with such extension.   Finally, the current proposal does not specify
a naming scheme for processes.  We propose to always identify processes
according to their relative rank in a context (group), so that, effectively,
processes are identified by consecutive integers.  Absolute, system-wide unique
process id's are (will be) needed only if dynamic process creation is to be
supported  (in such eventuality we propose to use handles to opaque {\em process
structures} for that purpose).

\subsection{Contexts}

\discuss{ This section contains a proposal for use of contexts that will subsume
groups.  It borrows heavily on the current group proposal.  This proposal has
not yet been discussed in MPI meetings.}

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.

\paragraph*{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.

\paragraph*{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.

\paragraph*{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.

\paragraph*{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}
}

\subsubsection{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.

\paragraph*{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.
}

\subsubsection{Error Handling}

It is assumed that MPI is implemented on top of an error-free
communication subsystem: A message sent is always received
correctly, and the user does not need to check for transmission errors,
time-outs, and the likes.  In
other words, MPI does not provide mechanisms to deal with failures in the
underlying communication subsystem -- it is the responsibility of the MPI
implementer to insulate the user from such errors (or to reflect them as global
program failures). The same holds true for node failures.

Of course, MPI programs may still be erroneous.  A {\bf program error} can
occur when an MPI call is called with an incorrect parameter (non-existing
destination in a send operation, buffer too small in a receive operation, etc.)
This type of error would occur in any implementation.
In addition, a {\bf resource error} may occur when a program exceeds the amount
of available system resources (number of pending messages, system buffers,
etc.).   The occurrence of this type of error depends on the amount of
available resources in the system and the resource allocation mechanism used;
this may differ from system to system.   The recommended implementation profile
provides several mechanisms to alleviate the portability problem this
represents.  One can also write {\bf safe} programs, that are not subject to
resource errors.

All MPI procedure calls return an error parameter that indicates successful
completion of the operation, or the error condition that occurred, otherwise.

The recommended implementation profile in a POSIX environment is for any MPI
routine that encounters a recoverable error to store an error number in
a global variable ({\em errno} in a C environment) and generate an {\em MPI
error signal}, using a special signal value.  The default handler for
this signal terminates the execution of all involved processes, with a suitable
error message being returned to the user.  However, the user can provide his or
her own signal handling routine.  In particular, the user can
specify a ``noop'' signal handler, thus relegating all error handling to the
user code, using the error parameters returned by the MPI calls.

MPI calls may initiate operations that continue
asynchronously after the call returned.  Thus, the operation may return with a
code indicating successful completion, yet later cause an error exception to be
raised.  If there is a subsequent call that relates to the same operation (e.g.,
a call that verifies that an asynchronous operation has completed) then the
error parameter associated with this call will be used to indicate the nature
of the error.  In a few cases, the error may occur after all calls that
relate to the operation have completed, so that no error parameter can be used
to indicate the nature of the error (e.g., an error in
a send with the ready mode).  In such cases, an error will be undetected, if
the user disabled the MPI error signal.

\discuss{
The alternative choice is to have fatal and non-fatal signals.
}

\subsection{Messages}

A message consists of an {\em envelope} and {\em data}.

\subsubsection{Data}

The data part of a message consists of a sequence of values, each of a basic
datatype in the host language.  Thus, in Fortran, a message consists of
a sequence of values that are each of type {\tt INTEGER}, {\tt REAL}, {\tt
DOUBLE PRECISION}, {\tt
COMPLEX}, {\tt LOGICAL}, or (length 1) {\tt CHARACTER}.  A message may mix
values of different types.

\discuss{ May also need {\tt DOUBLE COMPLEX} in Fortran.}

\subsubsection{Envelope}
\label{subsec:envelope}

The following information is associated with each message:
\begin{description}
\item[source] The rank the sending process
\item[destination] The rank of the receiving process
\item[tag] User defined
\item[context]  handle
\end{description}

The range of valid values for the {\bf
source} and {\bf destination} fields is {\tt 0 ... n-1}, where
{\tt n} is the number of processes in the current context. The ranges of
valid values for {\tt tag} is implementation dependent, and
can be found by calling a suitable query function, as described in
Section~\ref{sec:inquiry}.  {\tt Context} should be a context shared by both
source and destination.

The {\tt tag} field can be arbitrarily set by the application, and can be used
to distinguish different messages.

The actual mechanism used to associate an envelope with a message
is implementation dependent; some of the information (e.g., {\bf
sender} or {\bf receiver}) may be implicit,  and need not be
explicitly carried by a message.

\subsection{Data Buffers}
\label{subsec:buffers}

The basic point to point communication operations are {\bf send} and {\bf
receive}. A {\bf send} operation creates a message; the message data is
assembled from the {\bf send buffer}.  A {\bf receive} operation consumes a
message; the message data is moved into the {\bf receive buffer}.  The
specification of send or receive buffers uses the same syntax.

A buffer consists of a sequence {\bf buffer components}.  Each
component consists of a sequence variables of the same basic type.
There are three basic types of buffer components:

\begin{description}
\item[block]
A sequence of contiguous values of the same basic type,
specified by
\begin{description}
\item[start]
Initial element
\item[len]
Number of elements  ($\tt len \ge 0$)
\item[datatype]
Type of elements
\end{description}
\item[vector]
A sequence of equally spaced and equally sized blocks of elements of the same
basic type, specified by
\begin{description}
\item[start]
Initial element
\item[len]
Number of elements ($\tt len \ge 0$)
\item[stride]
Number of elements between the start of each block
\item[lenblk]
Number of elements in each block  ($\tt lenblk \le stride$)
\item[datatype]
Type of elements
\end{description}
Note that a constant stride becomes contiguous when
{\tt stride = lenblk}.   A vector buffer component can be an arbitrary submatrix
of a two-dimensional matrix.
\item[indexed]
A sequence of elements of the same basic type, specified by
\begin{description}
\item[start]
initial element
\item[list\_of\_indices]
List of displacements of the elements in the buffer components, relative to the
initial element.
\item[datatype]
Type of elements
\end{description}
\end{description}

For example, if a Fortran array is declared as
{\tt double precision a(10)}, then the tuple
{\tt $<$(a(3), (0,3,6,2), DOUBLE$>$} specifies a buffer component with entries
{\tt a(3) a(6), a(9), a(5)}.

\discuss{
Do we allow entries to be repeated in an indexed buffer component?

Do we allow different buffer components to overlap?

Do we require in an vector buffer component that {\tt len} be a multiple of
{\tt lenblk}?

}

A buffer is described by an opaque object accessed via a {\bf buffer handle}.
Such object is created and destroyed via calls to {\tt
MPI\_CREATE} and {\tt MPI\_FREE}. It is
associated with successive buffer components by calling in succession one of the
functions {\tt MPI\_ADD\_BLOCK}, {\tt MPI\_ADD\_VECTOR} or {\tt
MPI\_ADD\_INDEX}, in order to append a component to the buffer associated with
a buffer handle.
A buffer object can be destroyed only if there is no pending communication
operation using it.  After a buffer object is destroyed the associated buffer
handle is undefined.

{\bf \ \\ MPI\_ADD\_BLOCK( buffer, start, len, datatype)} \\

Append a block component to buffer.
The parameters are:
\begin{description}
\item[INOUT buffer]
buffer handle
\item[IN start]
buffer component initial element (choice)
\item[IN len]
Number of elements (integer)
\item[IN datatype]
datatype identifier (status)
\end{description}

{\bf \ \\ MPI\_ADD\_VEC( buffer, len, stride, lenblk, datatype )} \\

Append a vector buffer component to buffer.
The parameters are:
\begin{description}
\item[INOUT buffer]
buffer handle
\item[IN start]
buffer component initial element (choice)
\item[IN len]
Number of elements (integer)
\item[IN stride]
Number of elements between the start of each block (integer)
\item[IN lenblk]
Number of elements in each block (integer)
\item[IN datatype]
datatype identifier (status)
\end{description}

{\bf \ \\ MPI\_ADD\_INDEX( buffer, start, list\_of\_indices, datatype)}
\\

Append an indexed buffer component to buffer.
The parameters are:
\begin{description}
\item[INOUT buffer]
buffer handle
\item[start]
initial position for indexing (choice)
\item[list\_of\_indices]
list of relative indices of entries (array of integers)
\item[IN datatype]
datatype identifier (status)
\end{description}

Consider, for example, the following fragment of Fortran code

\begin{verbatim}
DOUBLE PRECISION A(10,20)
INTEGER B, C(5,10)
INTEGER BH
...
CALL MPI_CREATE(BH, MPI_BUFFER, MPI_PERSISTENT)
CALL MPI_ADD_BLOCK (BH, B, 1, MPI_INT)
CALL MPI_ADD_VEC (BH, A(1,3), 11, 4, 2, MPI_DOUBLE)
CALL MPI_ADD_INDEX(BH, C(3,7), (4,2,1), MPI_INT)
\end{verbatim}

Then the buffer associated with the handle {\tt BH} consists of the sequence of
variables

{\tt B, A(1,3), A(2,3), A(5,3), A(6,3), A(9,3), A(10,3),  A(3,4), A(4,4),
A(7,4), A(8,4), A(1,5), C(2,8), C(5,7), C(4,7)}.

A message created from this buffer will consist of a sequence of one integer,
followed by eleven double precision reals, followed by three integers.

A buffer handle can be used for communication, even if it is not associated with
any  variables (i.e., even if it was not set by any {\tt MPI\_ADD\_xxx} call).
Such handle is associated with an empty buffer, and a message created from it
contains no data.

\discuss{

The main modifications w.r.t. the proposal of Gropp and Lusk is measuring
length in elements, rather than bytes. Seems more natural, since type is known.
Also, object creation uses a generic
function, rather than a function specific to buffer descriptors.  As result,
I gave up on the size parameter.  This may not be such a loss:
it is not clear that specifying a maximum length at buffer object creation is
useful, since indices of arbitrary size may need to be stored in
the object.

}

\subsubsection{Data Conversion}

The types and the locations of the entries used to create a message
is solely determined from the information in the buffer
descriptor, using the storage association rules specified by the host language
and its implementation; the type and the locations of these
entries do not depend on the declaration for the corresponding variables in
the calling program.  It is not required that the data
types specified in a buffer descriptor match the data types of the corresponding
elements in the host program.  However, in case of mismatches, the
correspondence between entries in the host program and entries in a message
created with the buffer descriptor may be implementation dependent.
No data
conversion occurs when data is moved from a sender buffer into a message.

Consider the following fragment of Fortran code

\begin{verbatim}
REAL A(100)
INTEGER BH
...
CALL MPI_CREATE(BH, MPI_BUFFER, MPI_PERSISTENT)
CALL MPI_ADD_BLOCK (BH, A(1), 1, MPI_REAL)
CALL MPI_ADD_BLOCK (BH, A(2), 1, MPI_INT)
CALL MPI_ADD_BLOCK (BH, A(3), 1, MPI_LOGICAL)
CALL MPI_ADD_BLOCK (BH, A(4), 1, MPI_COMPLEX)
CALL MPI_ADD_BLOCK (BH, A(6), 1, MPI_DOUBLE)
CALL MPI_ADD_BLOCK(BH, A(8), 4, MPI_CHAR)
\end{verbatim}

A message created from this buffer will consist of a sequence containing one
real, one integer, one logical, one complex, one double, and four characters.
No data conversion occurs
when values are copied from the sender buffer to the message.  Thus, the first
entry in the message is a real number equal to {\tt A(1)}; the second entry is
an integer number that happens to have the same binary representation as
{\tt A(2)}; the third entry is a logical value that happens to have the same
binary representation as {\tt A(3)}; the fourth entry in a complex number
with a binary representation identical to {\tt A(4), A(5)}; the fifth entry is
a double precision value with a binary representation identical to {\tt A(6),
A(7)}; and if words have four bytes then the last four entries are bytes that
make the binary representation of {\tt A(8)}, in the byte order of the
executing machine.

The correspondence between the first seven entries of the array {\tt A} and the
first five entries of the message created from this buffer is determined by
the rules of Fortran 77 on storage association:  Each variable of type {\tt
INTEGER}, {\tt REAL}, or {\tt LOGICAL} occupy one {\em numeric storage unit}; a
variable of type {\tt DOUBLE} or {\tt COMPLEX} occupy two numeric storage units.
Thus, the same correspondence will hold for any implementation.  However,
different implementations may have different binary encodings of integer, real
and logical values, so that the actual values transferred by the message may
differ.

The correspondence between the entry {\tt A(8)} of the array, and the
last four character entries in the message is implementation dependent, since
the Fortran language does not specify a correspondence between character storage
units and numeric storage units (an array of characters cannot be equivalenced
with an array of integers).  Different results may occur in big-endians or
small-endians machines, or in 32 bit or 64 bit machines.

The same holds, symmetrically, when a message is received.  Entries are moved
from the message into the receiver memory according to the information provided
by the buffer descriptor, with no regard to the way the corresponding variables
are declared in the receiving program.

When data is moved in a homogeneous environment between nodes having the same
architecture, then no data conversion occur at any point during data transfer.
Assume, in the previous example, that an identically declared buffer descriptor
is used to receive data into an identically declared array at the receiving
process.  Then, when these two nodes communicate, the values in the first eight
entries of array {\tt A} of the sender will be copied into the first eight
entries of array {\tt A} at the receiver (assuming that reals occupy the
same storage as four bytes).  In particular, in a homogeneous environment, it
is possible to communicate using only character typed messages.

When data is moved into a heterogeneous environment between nodes having
distinct architectures, data conversion may occur during the transfer:  Each
entry is converted from the data representation used on the sending node to the
data representation used in the receiving node.

Consider the following fragment of Fortran code.

\begin{verbatim}
REAL X, Y
CHARACTER (4) Z
INTEGER BH
...
CALL MPI_CREATE(BH, MPI_BUFFER, MPI_PERSISTENT)
CALL MPI_ADD_BLOCK (BH, X, 1, MPI_REAL)
CALL MPI_ADD_BLOCK (BH, Y, 4, MPI_CHAR)
CALL MPI_ADD_BLOCK (BH, Z, 4, MPI_CHAR)
\end{verbatim}

Assume that the same arrays {\tt X, Y, Z} and buffer handle {\tt BH} are
created at two processes A and B; this handle is used by A to create and send
a message for B, by B to receive this message.  Further assume that both A and B
run on distinct nodes, with possibly different 32 bit architectures.
Then {\tt X} at process B is assigned
the value of {\tt X} at process A (up to rounding errors that may occur during
conversion);  {\tt Z} on process B is assigned the character string value of
{\tt Z} on process A; if both nodes use ASCII encoding, then no conversion is
required for the characters.  On the other hand, variable {\tt Y} on process B
may be allocated a value that differs from the value of variable {\tt Y} on
process A.  This may occur if the two nodes use a different byte sequence
(little-endian vs big-endian), or use a different binary representation for
reals (IEEE vs HEX).  Thus, in order to ensure correct execution in a
heterogeneous environment, it is important that the types of values in a
message match the types of the corresponding values in the sending and in the
receiving program.

\subsection{Receive Criteria}

The selection of a message by a receive operation is done uniquely
according to the value of the message envelope.  The receive operation specifies
an {\bf envelope pattern}; a message can be received by that receive operation
only if its envelope matches that pattern.
A pattern specifies
values for the {\tt source}, {\tt tag} and {\tt context} fields of
the message envelope.  In addition, the value for the {\tt dest} field is set,
implicitly, to be equal to the receiving process id.
The receiver may specify a {\bf DONTCARE} value for {\tt source}, or {\tt tag},
indicating that any source and/or tag are acceptable.   It cannot specify a
DONTCARE value for {\tt context} or {\tt dest}.
Thus, a message can be received by a receive
operation only if it is addressed
to the receiving task, has a matching context, has matching source unless
source=DONTCARE in the pattern, and has a matching tag unless tag=DONTCARE in
the pattern.

The length of the received message must be less or equal the length of the
receive buffer.  I.e., all incoming data must fit, without truncation, into the
receive buffer.  It is erroneous to receive a message which length exceed the
receive buffer, and the outcome of program where this occurs is undetermined.

\subsection{Communication Mode}

A sending operation can occur in one of two modes:
\begin{description}
\item[REGULAR]
The send may start whether or not a matching receive has been posted.
\item[READY]
The send may start only if a matching receive has been posted.
\end{description}

A {\bf ready send} can start only if a matching receive is already posted;
otherwise the operation is erroneous and its outcome is undefined.  In some
systems, this will allow to optimize communication and avoid a hand-shaking
operation that is otherwise required.

\discuss{I deleted the symmetric ready receive.  Will revive it if there is a
requirement for it.}

\subsection{Communication Objects}

An opaque communication object identifies various properties of a communication
operation, such as the buffer descriptor that is associated with it, its
context, the tag and destination parameters to be used for a send, or the tag
and source parameters to be used for a receive.  In addition, this object stores
information about the status of the last communication  operation that was
performed with this object.  This object is accessed using a communication
handle.

One can consider
communication operations to consist of the following suboperations:

\begin{description}
\item[INIT(operation, params, handle)]
Process provides all relevant parameters for its participation in the
communication operation (type of operation, data buffer, tag, participants,
etc.). An object is created that identifies the operation.
\item[START(handle)]
The communication operation is started
\item[COMPLETE(handle)]
The communication operation is completed.
\item[FREE(handle)]
The communication object, and associated resources are freed.
\end{description}
Correct invocation of these suboperations is a sequence of the form
\[ \bf INIT \ (START \ COMPLETE )^* \ FREE .\]
I.e., an object needs be created before communication occurs; it can be reused
only after the previous use has completed; and it needs to be freed eventually
(of course, one can assume that all objects are freed at program termination,
by default).

The above scenario pertains to {\em persistent} objects.  One can also create
{\em ephemeral} objects.  Such object persists only until the communication
operation is completed, at which point it is destroyed.  Thus, correct
invocation of suboperations with an ephemeral object is
{\bf INIT START COMPLETE}.

A user may directly invokes these suboperations.  This would allow to amortize
the overhead of setting up a communication over many successive uses of the same
handle, and allows to overlap communication and computation.   Simpler
communication operations combine several of these suboperations into one
operation, thus simplifying the use of communication primitives.
Thus, one only needs to specify
precisely the semantics of these suboperations in order to specify the semantics
of MPI point to point communication operations.

We say that a communication operation (send or receive) is {\bf posted} once
a {\bf start} suboperation was invoked; the operation is {\bf completed} once
the {\bf complete} suboperation completes.  A send and a receive operation
{\bf match} if the receive pattern specified by the receive matches the message
envelope created by the send.

\subsubsection{Communication Object Creation}

An object for a send operation is created by a call to {\bf MPI\_INIT\_SEND}.
A call to {\bf MPI\_INIT\_RECV} is similarly used for creating an object for a
receive operation.   The creation of a communication object is a local operation
that need not involve communication with a remote process.

{\bf \ \\ MPI\_INIT\_SEND (handle, buffer\_handle, dest, tag, context, mode,
persistence)} \\

Creates a send communication object.  Parameters are
\begin{description}
\item[OUT handle] message handle.  The handle should not be associated with any
object before the call.
\item[IN buffer\_handle] handle to send buffer descriptor
\item[IN dest] rank in context of destination (integer)
\item[IN tag] user tag for messages sent with this handle (integer)
\item[IN context] handle to context of messages sent with this handle
\item[IN mode] send mode (state type, with two values: {\tt MPI\_REGULAR} and
{\tt MPI\_READY})
\item[IN persistence] handle persistence (state type, with two values: {\tt
MPI\_PERSISTENT} and {\tt MPI\_EPHEMERAL})
\end{description}

{\bf \ \\ MPI\_INIT\_RECV (handle, buffer\_handle, source, tag, context,
persistence)} \\

Create a receive handle.  Parameters are
\begin{description}
\item[OUT handle] message handle.  The handle should not be associated with any
object before the call.
\item[IN buffer\_handle] handle to receive buffer descriptor.
\item[IN source] rank in context of source, or DONTCARE (integer).
\item[IN tag] user tag for messages received with this handle, or DONTCARE
(integer).
\item[IN context] handle to context of messages received with this handle.
\item[IN persistence] handle persistence (state type, with two values: {\tt
MPI\_PERSISTENT} and {\tt MPI\_EPHEMERAL})
\end{description}

See Section~\ref{subsec:envelope} for a discussion of source, tag and context.

\discuss{
I have not included proposals for partially specified message handles, that
some peoples seem to desire.

I have merged all handle setup into one call.

}

\subsubsection{Communication Start}

{\bf \ \\ MPI\_START(handle)}
\begin{description}
\item[IN handle] communication handle
\end{description}

The {\tt MPI\_START} function starts the execution of a communication operation
(send or receive).  A sender should not update the send buffer after a
send operation has started and until it is completed.  A receiver should not
access the receive buffer after a receive operation was started and until it is
completed.  A program that does not satisfy this condition is erroneous and its
outcome is undetermined.

\subsubsection{Communication Completion}
\label{subsec:complete_ops}

{\bf \ \\ MPI\_WAIT ( handle, return\_status\_handle)}
\begin{description}
\item[IN handle]  communication handle
\item[OUT return\_handle] handle that is associated with return status object.
\end{description}

A call to {\bf MPI\_WAIT} returns when the send operation
identified by {\tt handle} is complete.
The completion of a send operation indicates that the sender is now free to
update the locations in the send buffer, or any other location that can be
referenced by the send operation.  However, it does not indicate that the
message has been received; rather it may have been buffered by the communication
subsystem.

The completion of a receive operation indicates that the receiver is now free to
access the locations in the receive buffer, which contain the received message,
or any other location that can be referenced by the receive operation.  It does
not indicate that the matching send operation has completed.

The call returns a handle to an opaque object that contains information on
the completed operation -- the {\bf return status} object.

{\bf \ \\ MPI\_STATUS (handle, flag, return\_handle)}
\begin{description}
\item[IN handle]  communication handle
\item[OUT flag] logical
\item[OUT return\_handle] handle that is associated with return status
object.
\end{description}

A call to {\bf MPI\_STATUS} returns {\tt flag=true} if the
operation identified by {\tt handle} is complete,  In such case, the return
handle points to an opaque object that contains information on the completed
information.  It returns
{\tt flag=false}, otherwise. In such case, the value of the return handle is
undefined.

Implementation notes:

A call to {\tt MPI\_WAIT} blocks only the executing thread.  If the
executing process is multithreaded, then other threads within the process can be
scheduled for execution.

The use of a blocking receive operation ({\tt
MPI\_WAIT}) allows the operating system to deschedule the blocked thread
and schedule another thread for execution, if such is available.  The use of
a nonblocking receive operation ({\tt MPI\_STATUS}) allows the user to
schedule alternative activities within a single thread of execution.

The intended implementation of {\tt MPI\_STATUS} is for that operation
to return as soon as possible.  However, if repeatedly called for an operation
that is enabled, it must eventually succeed.

The return status object for a send operation carries no information.  The
return status object for a receive operation carries information on the source,
tag and length of the received message.  These fields are required because the
receive operation may have specified {\tt DONTCARE} in either source or tag
field, and the message may have been shorter than the receive buffer.

{\bf \ \\ MPI\_RETURN\_STAT( handle, len, source, tag)}
\begin{description}
\item[IN handle] handle to return status object
\item[OUT len] difference between length of receive buffer and length of
received message, in bytes.  Thus, the value returned is zero if the received
message matches the the receive buffer, positive if it is shorter (integer).
\item[OUT source] rank of message sender in message context (integer).
\item[OUT tag] tag of received message (integer).
\end{description}

\discuss{

I put the difference between message buffer and message length as the value
returned, rather than length of received message, so that it might be easy to
test for exact match.

The use of a return status object, rather than a list of parameters may simplify
the use of MPI routines, if the values stored in the object are seldom checked.
A predefined  return status object should be provided, to ease programming.}

\subsubsection{Multiple Completions}

It is convenient to be able to wait for the completion of any or all the
operations in a set, rather than having to wait for specific message.
A call to {\tt MPI\_WAITANY} or {\tt MPI\_STATUSANY} can be used to wait for the
completion of one out of several operations; a call to {\tt MPI\_WAITALL} can be
used to wait for all pending operations in a list.

{\bf \ \\ MPI\_WAITANY ( list\_of\_handles, index, return\_handle)} \\

Blocks until one of the operations associated with the communication
handles in the array has completed.  Returns the index of that handle in the
array, and returns the status of that operation in the object associated with
the return\_handle.  The parameters are:

\begin{description}
\item[IN list\_of\_handles] list of handles to communication objects.
\item[OUT index] index of handle for operation that completed (integer).
\item[OUT return\_handle] handle that is associated with return status
object.  Set to return status of operation that completed.
\end{description}

The successful execution of {\tt MPI\_WAITANY(list\_of\_handles, index,
return\_handle)} is equivalent to the successful execution of {\tt
MPI\_WAIT(handle[i], return\_handle)}, where {\tt i} is the value
returned by {\tt index} and {\tt handle[i]} is the {\tt i}-th handle in the
list.

If more then one operation is enabled and can terminate, one is arbitrarily
chosen (subject to the restrictions on operation termination order, see
Section~\ref{subsec:correct}).

{\tt \ \\ MPI\_WAITANY ( list\_of\_handles, index, return\_status\_handle)} \\
is
\begin{verbatim}
   {MPI_WAIT_RECV (handle[1], return_handle); index = 0} || ...
||
   {MPI_WAIT_RECV (handle[n], return_handle); index = n-1}
\end{verbatim}

(``$||$'' indicates choice; one of the alternatives is chosen,
nondeterministically.)

{\bf \ \\ MPI\_STATUSANY ( list\_of\_handles, index,
return\_handle)} \\

Causes either one or none of the operations associated with the communication
handles to return.   In the former case, it has the same return semantics as a
call to {\tt MPI\_WAIT\_ANY}.  In the later case, it returns a value of -1 in
{\tt index} and {\tt return\_handle} is undefined.
The parameters are:

\begin{description}
\item[IN list\_of\_handles] list of handles to communication objects.
\item[OUT index] index of handle for operation that completed, or -1 if none
completed (integer).
\item[OUT return\_handle] handle that is associated with return status
object.  Set to return status of operation that completed, if any; undefined
when {\tt index = -1}.
\end{description}

{\bf MPI\_WAITALL(list\_of\_handles, list\_of\_return\_handles)} \\

Blocks until all communication operations associated with handles in the list
complete, and return the status of all these operations.
The parameters are:

\begin{description}
\item[IN list\_of\_handles] list of handles to communication objects.
\item[OUT list\_of\_return\_handles]  Must have the same length as the
first list.  Each return status object is set to the return status of the
corresponding operation in the first list.
\end{description}

\subsection{Blocking Communication}

Blocking send and receive operations combine all communication suboperations
into
one call.  The operation returns only when the communication completes and no
communication object persists after the call completed.  However, the buffer
descriptor object needs be created ahead of the call.

We use the following naming convention for such operations:

\[
\left[ \begin{array}{c} - \\ \bf R \end{array} \right]
\left[ \begin{array}{c} \bf SEND \\ \bf RECV \end{array} \right]
\]

The first letter (void or {\bf R}) indicates the start mode (regular or ready).

{\bf \ \\ MPI\_SEND (buffer\_handle, dest, tag, context)}   \\
is
\begin{verbatim}
MPI_INIT_SEND(handle, buffer_handle, dest, tag, context, REGULAR, EPHEMERAL)
MPI_START(handle)
MPI_WAIT(handle, null)
\end{verbatim}

{\bf \ \\ MPI\_RSEND (buffer\_handle, dest, tag, context)}   \\
is
\begin{verbatim}
MPI_INIT_SEND(handle, buffer_handle, dest, tag, context, READY, EPHEMERAL)
MPI_START(handle)
MPI_WAIT(handle, null)
\end{verbatim}

{\bf \ \\ MPI\_RECV(buffer\_handle, source, tag, context,
return\_handle)} \\ is
\begin{verbatim}
MPI_INIT_RECV(handle, buffer_handle, source, tag, context, EPHEMERAL)
MPI_START(handle)
MPI_WAIT(handle,return_handle)
\end{verbatim}

{\bf Implementation note:}

While these functions can be implemented via calls to functions that
implement suboperations, as described in this subsection, an efficient
implementation may optimize away these multiple calls, provided it does not
change the behavior of correct programs.

\subsection{Nonblocking Communication}

Nonblocking send and receive operations combine the first two
suboperations ({\tt INIT} and {\tt START}) into one call.
They use ephemeral communication objects, so that the operation is completed,
and the associated resources are freed, by using one of the functions {\tt
MPI\_WAIT, MPI\_STATUS, MPI\_WAITANY, MPI\_STATUSANY}, or {\tt MPI\_WAITALL}.
Here, too, a buffer object has to be created ahead of the communication
initiation operation.

We use the same naming convention as for blocking operations:  a prefix of
{\bf R} indicates the {\tt READY} mode.   In addition, a prefix of {\bf I} is
used to indicate {\em immediate} (i.e., nonblocking) execution.

{\bf \ \\ MPI\_ISEND (handle, buffer\_handle, dest, tag, context)}   \\
is
\begin{verbatim}
MPI_INIT_SEND(handle, buffer_handle, dest, tag, context, REGULAR, EPHEMERAL)
MPI_START(handle)
\end{verbatim}

{\bf \ \\ MPI\_IRSEND (handle, buffer\_handle, dest, tag, context)}   \\
is
\begin{verbatim}
MPI_INIT_SEND(handle, buffer_handle, dest, tag, context, READY, EPHEMERAL)
MPI_START(handle)
\end{verbatim}

{\bf \ \\ MPI\_IRECV(handle, buffer\_handle, source, tag, context,
return\_status\_handle)} \\
is
\begin{verbatim}
MPI_INIT_RECV(handle, buffer_handle, source, tag, context, EPHEMERAL)
MPI_START(handle)
\end{verbatim}

\subsection{Block Sending Operations}

The most frequent type of buffer used is a contiguous buffer of numeric storage
units, i.e., a contiguous buffer of words that may contain either
INTEGER, REAL or LOGICAL values (in FORTRAN).   In a homogeneous environment
such messages can be used to send arbitrary sequences of contiguous items, where
each item occupies an integer number of words.

We specialize the functions in
the two previous subsections to this case, thus avoiding the need for the
creation of a buffer descriptor object.  We use the same naming scheme used
in the previous subsections, and append a {\bf B} in the function name, for {\tt
BLOCK}.

{\bf \ \\ MPI\_SENDB (start, len, dest, tag, context)}   \\
is
\begin{verbatim}
MPI_CREATE(buffer_handle, MPI_BUFFER, MPI_EPHEMERAL)
MPI_ADD(buffer_handle, start, len, MPI_REAL)
MPI_SEND (buffer_handle, len, dest, tag, context)
\end{verbatim}

{\bf \ \\ MPI\_RSENDB (buffer\_handle, dest, tag, context)}   \\
is
\begin{verbatim}
MPI_CREATE(buffer_handle, MPI_BUFFER, MPI_EPHEMERAL)
MPI_ADD(buffer_handle, start, len, MPI_REAL)
MPI_RSEND (buffer_handle, len, dest, tag, context)
\end{verbatim}

{\bf MPI\_RECVB(buffer\_handle, source, tag, context, return\_status\_handle)}
\\ is
\begin{verbatim}
MPI_CREATE(buffer_handle, MPI_BUFFER, MPI_EPHEMERAL)
MPI_ADD(buffer_handle, start, len, MPI_REAL)
MPI_RECV(buffer_handle, source, tag, context, return_status_handle)
\end{verbatim}

{\bf \ \\ MPI\_ISENDB (handle, buffer\_handle, dest, tag, context)}   \\
is
\begin{verbatim}
MPI_CREATE(buffer_handle, MPI_BUFFER, MPI_EPHEMERAL)
MPI_ADD(buffer_handle, start, len, MPI_REAL)
MPI_ISEND(handle, buffer_handle, dest, tag, context)
\end{verbatim}

{\bf \ \\ MPI\_IRSENDB (handle, buffer\_handle, dest, tag, context)}   \\
is
\begin{verbatim}
MPI_CREATE(buffer_handle, MPI_BUFFER, MPI_EPHEMERAL)
MPI_ADD(buffer_handle, start, len, MPI_REAL)
MPI_IRSEND(handle, buffer_handle, dest, tag, context)
\end{verbatim}

{\bf \ \\ MPI\_IRECVB(handle, buffer\_handle, source, tag, context,
return\_status\_handle)} \\
is
\begin{verbatim}
MPI_CREATE(buffer_handle, MPI_BUFFER, MPI_EPHEMERAL)
MPI_ADD(buffer_handle, start, len, MPI_REAL)
MPI_IRECV(handle, buffer_handle, source, tag, context)
\end{verbatim}

\discuss{

I use word count, rather than byte count.  I believe word messages are much more
prevalent than byte messages, and it's a blessing not to have to multiply by 4
for each message.  Byte messages are still available the hard way.  Also, word
messages fit well with the Fortran numeric storage unit concept.

If we are to add more functions, my next addition would be a vector send
operation.

}

\subsection{Correctness}
\label{subsec:correct}

\discuss{The material in this section has not yet been discussed by MPIF.
Some or all of it is likely to move to Section~\ref{sec:formal}.
It is incorporated here for completeness.}

\subsubsection{Order}

MPI preserves the order of messages between any fixed pair of processes.
In other words, if process A executes two successive send {\tt start}
suboperations,
process B executes two successive receive {\tt start} operations, and both
receives
match either sends, then the first receive will receive the message sent by the
first send, and the second receive will receive the message sent by the second
send.  Thus, if a two messages from the same source can satisfy a pending
receive, the first message sent is accepted; if a message can satisfy two
pending receives, the first receive posted is satisfied.

The last paragraph assumes that the send {\tt start} operations are ordered by
the
program order at process A, and the receive {\tt start} operations are ordered
by the
program order at process B.  If a process is multithreaded and the operations
are executed by distinct threads, then the semantics of the threaded system may
not define an order between the two operations, in which case the condition is
void.

\subsubsection{Progress and Fairness}

We can model the execution of MPI programs as an interaction between executing
processes that execute each their own program, and the {\bf communication
subsystem}.  The communication subsystem may have various constraints on the
amount of resources it can use.  E.g.:

Bounds on the number and total sizes of active communication objects.
Such bound can be global, per node, or per pair of communicating nodes.

Bounds on the number and total sizes of messages buffered in the system.  Such
bound can, again, be global, per node, or per pair of communicating node.  In
addition, a message may be buffered at the sender, at the receiver, at both, or
perhaps at another place altogether.

Thus, it will be difficult to set rules on resource management of the
communication subsystem.   However, it is generally expected that implementers
will provide information on the mechanism used for resource allocation, and that
query and set functions will allow to query and possibly control the amount
of available resources.

We provide in this section a set of minimal requirements on the communication
subsystem.  Programs that execute on any subsystem that fulfils these minimal
requirements are {\bf safe} and will port to any MPI implementation.
{\bf Unsafe} programs may execute on some MPI implementations, depending on the
amount of available resources and the implementation used for the MPI
communication subsystem.  Finally {\bf  erroneous} programs never execute
correctly.  (While it is desirable to detect erroneous programs, it is not
possible to do so at compile time, and often prohibitive to do so a run time.
Thus, the document does not specify a behavior for erroneous programs, although
the desired behavior is to return a useful error message.)

\begin{enumerate}
\item
If a process executes an {\tt INIT}  operation,
then the operation eventually succeeds, or a {\em resource exception} occurs.
The standard does not specify when a resource exception is allowed to occur.  It
is expected that an operational definition will be made available, in the form
of test programs that have to execute with no resource exceptions.
It is highly desirable to have generous bounds on the number of
concurrently active communication objects each process may have, so that,
in practice, {\tt INIT} operations will always be guaranteed to succeed.
\item
Each process can initiate a communication operation for each active
communication object. I.e. correct {\tt START} operations always succeed
(eventually).
\item
A send operation is {\bf enabled} if the sending process has issued a
{\tt COMPLETE} operation and the receiving process has issued a {\tt
START} operation for a matching receive.  Symmetrically,
a receive operation is {\bf enabled} if the receiving process has issued
a {\tt COMPLETE} operation and the sending process has issued a {\tt
START} operation for a matching send.
An enabled operation may become {\bf disabled} either because it completes
successfully or, in the case of a receive, because the matching message is
successfully received by another receive operation.

{\bf An enabled operation either completes successfully or becomes permanently
disabled.}
\item
A {\tt FREE} operation always succeeds (eventually).
\end{enumerate}

The four conditions guarantee progress in the communication subsystem.  The
third condition guarantee (weak) fairness among competing communication
requests.

Examples (involving two processors with ranks 0 and 1)

The following program is safe, and should always succeed.
\begin{verbatim}

CALL MPI_RANK(rank, context)
IF (rank.EQ.0) THEN
   CALL MPI_SENDB(sendbuf, len, 1, tag, context)
   CALL MPI_RECVB(recvbuf, len, 1, tag, context)
ELSE    ! rank.EQ.1
   CALL MPI_RECVB(recvbuf, len, 0, tag, context)
   CALL MPI_SENDB(sendbuf, len, 0, tag, context)
END IF
\end{verbatim}

The following program is erroneous, and should always fail.

\begin{verbatim}

CALL MPI_RANK(rank, context)
IF (rank.EQ.0) THEN
   CALL MPI_RECVB(recvbuf, len, 1, tag, context)
   CALL MPI_SENDB(sendbuf, len, 1, tag, context)
ELSE    ! rank.EQ.1
   CALL MPI_RECVB(recvbuf, len, 0, tag, context)
   CALL MPI_SENDB(sendbuf, len, 0, tag, context)
END IF
\end{verbatim}

The receive operation of the first process must complete before its send, and
can complete only if the matching send
of the second processor is executed; the receive operation of the second
process must complete before its send and
can complete only if the matching send of the first process is executed.
This program will deadlock.

The following
program is unsafe, and may succeed or fail, depending on implementation.

\begin{verbatim}

CALL MPI_RANK(rank, context)
IF (rank.EQ.0) THEN
   CALL MPI_SENDB(sendbuf, len, 1, tag, context)
   CALL MPI_RECVB(recvbuf, len, 1, tag, context)
ELSE    ! rank.EQ.1
   CALL MPI_SENDB(sendbuf, len, 0, tag, context)
   CALL MPI_RECVB(recvbuf, len, 0, tag, context)
END IF

\end{verbatim}

The message sent by each process has to be copied out before the send operation
returns and the receive operation starts.  For the program to complete, it is
necessary that at least one of the two messages sent is buffered out of
either processes' address space.  Thus, this program can
succeed only if the communication system has sufficient
buffer space to buffer {\tt len} words of data.

If additional requirements will become part of the standard (e.g., bounds
on the minimal number of concurrently active handles that need be supported,
then further programs become safe.

\end{document}