From: "Marc Snir" <[email-masked]>
Date: Mon, 8 Feb 93 09:37:16 EST

Some (all?) of you may have received a truncated version of this doc at
my previous attempt.  Trying again.

\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}
\maketitle
\section{Point to Point Communication}
\subsection{Introduction}

This section is a draft of the current proposal for point-to-point
communication.
We have not discussed in our last meeting the choice of a
syntax for the various
communication operations.  In particular, there have been no discussion on the
choice of function names.  There has been no decision whether its preferable to
use distinct function names or use additional parameters to distinguish between
different variants of the same operation.  There has been no discussion whether
parameters should be kept separated or bundled in one ``capsule'' that is
passed as one parameter.  There has been no discussion whether we prefer, in
Fortran, functions or subroutines.  Thus, the choice of a particular syntax in
this draft is merely for the sake of exposition, and is subject to change.

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

The current draft borrows heavily on the proposal of Gropp and Lusk for a
Multi-Level Message Passing Interface and on my previous outline.

\subsection{Messages}

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

\subsubsection{Data}

\paragraph*{Untyped Data}
The simplest (and most used) message data is untyped.  Such data
consists of a sequence of bytes.  Untyped messages can be used to transfer
arbitrary typed values between processors with identical data representations;
thus, untyped messages are sufficient in a homogeneous environment, where no
type conversion is required.

\discuss{
Is it legitimate to require that message length be a multiple of 4 or 8? -- or
should we require that any number of bytes be OK, with communication perhaps
faster for multiples of 4 or 8?}

\paragraph*{Typed data}

\missing{Need to add here typed messages.}

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

The following information is associated with each message:
\begin{description}
\item[source]
The id of the sending task
\item[dest]
The id of the receiving task
\item[tag]
User defined
\item[context]
\end{description}

All these fields are of type integer.  The range of valid values for the {\bf
sender} and {\bf receiver} fields is {\tt 0 ... number\_of\_tasks-1}, where
{\tt number\_of\_tasks} is the number of tasks currently participating in the
computation (i.e., both fields must include a valid task number).  The ranges of
valid values for {\tt tag} and {\tt context} are implementation dependent, and
can be found by calling a suitable query function, as described in
Section~\ref{sec:inquiry}.

\discuss{
Users would prefer to be able to use any integer as {\tt
tag} or {\tt context}.  Vendors may prefer small ranges (e.g. 8 or 16 bits) so
as to use fast tag and/or context matching hardware.

A defined arithmetic type could be used in C for {\tt tag} and {\tt context}.
}

The {\tt tag} field can be arbitrarily set by the application, and can be used
to distinguish different messages.   The {\tt context} field is used to
distinguish messages produced by different applications or different libraries.
Consider the case where an application calls in parallel on all executing nodes
a library function.  One needs to make sure that a message generated by the
library code will not be consumed by the application and vice-versa.  To do so,
one can
\begin{enumerate}
\item
Synchronize all nodes before and after the call, or
\item
Follow a programming convention that prevents such confusion (e.g., make sure
that the library code generate messages with tags that are distinct from the
tags used by the application, and accepts only messages with correct tags).
\end{enumerate}
The first solution may lead to less efficient code (it prevents a ``loosely
synchronous'' library call).  The second solution prevents modular code
development.  The use of a {\tt context} field, together with the context
setting mechanisms described in Section~\ref{sec:context}, solve this
problem.

Finally, we would like to note that the actual mechanism used to associate data
with envelope is implementation dependent; some of the information (e.g., {\bf
sender} or {\bf receiver}) may be implicit in some context, and may 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.

\paragraph*{Untyped Messages}

There are three kinds of buffers for untyped messages.
\begin{description}
\item[contiguous buffer]
A sequence of contiguous bytes in memory, specified by
\begin{description}
\item[buf]
Initial address
\item[len]
Number of bytes
\end{description}
\item[constant stride buffer]
A sequence of blocks equally spaced and equally sized blocks, specified by
\begin{description}
\item[buf]
Initial address
\item[numblk]
Number of blocks
\item[lenblk]
Number of bytes in each block
\item[stride]
Number of bytes between the start of each block
\end{description}
Note that a constant stride buffer becomes a contiguous buffer when
{\tt stride = lenblk}.
\item[general scatter gather]
A sequence of constant stride buffers, specified by a {\bf data\_vector}  of
the form {\tt (number\_of\_items, buf1, numblk1, lenblk1, stride1, ... bufn,
numblkn, lenblkn, striden)}.
\end{description}

\discuss{
Since Fortran 77 does not have a pointer type, an MPI
library that is strictly Fortran 77 compliant would need a different send
routine for each possible type of the variable {\tt buf}.   This is not very
practical.  I suggest to ignore the issue and rely on the fact that Fortran 77
compilers and linkers are very unlikely to do type checking across separately
compiled modules and are passing routine parameters by reference.  The C binding
can use pointers, and the Fortran 90 binding can use overloaded subroutines (for
basic types).

Data vectors are more of a problem, since we now need pointers as components
of the data vector.  The Posix Fortran 77 Language Interface IEEE standard
does not provide a general enough mechanism for that purpose.
We might restrict the use of data vectors to C.  (Of course, sophisticated
programmers would be able to call C routines from Fortran, and nonstandard
solutions might also be provided.)  Or, we might require that all buffer
addresses are integer displacements with respect to the first address, in which
case all entries are integer.

Is it acceptable to have a (small) fixed upper bound on the length of data
vectors?
}

\paragraph*{Typed Buffers}

\missing{Data buffers for typed messages.}

\subsection{Receive Criteria}

The selection of a message by a receive operation is done
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.

\discuss{
The DONTCARE value can be a fixed value (e.g. -1), and/or a named
constant.

It might be useful to have the option to require exact size match of incoming
message and receive buffer.  Some would also like to see truncation supported.
}

\subsection{Communication Handles}

One can consider (most) 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.). A handle 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 handle, 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., a handle 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 handles are freed at program termination,
by default).

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{Handle Creation}

A handle for a send operation is created by a call to {\bf MPI\_INIT\_SEND},
followed by a set of calls that set the various parameters associated with the
handle.  The handle cannot be used until all parameters have been set.
A call to {\bf MPI\_INIT\_RECV} is similarly used for creating a handle for a
receive operation.   Handle creation is a local operation that need not involve
communication with a remote process.

{\bf handle = MPI\_INIT\_SEND (dest, tag, context)}   \\
Create a send handle.  All three parameters must be specified.

{\bf handle = MPI\_INIT\_RECV (source, tag, context)}   \\
Create a send handle.  DONTCARE values may be used for the first two
parameters.

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

\discuss{
An alternative design, proposed by Gropp and Lusk, is to have each
newly created handle associated with default parameters that can be later
modified.  In their proposal, too, all modifications must occur before the first
use.}

\subsubsection{Buffer specification}

The {\bf MPI\_BUFFER} function associates a buffer with a handle.

{\bf MPI\_BUFFER(handle, buftype, params)}\\
\begin{tabbing}
{\bf buftype} \ \ \ \ \ \ \ \ \ \ \ \= {\bf params}  \\
CONTIGUOUS  \> buf, len \\
STRIDED  \> buf, numblk, lenblk, stride \\
GENERAL  \> data\_vector
\end{tabbing}

See Section~\ref{subsec:buffers} for a description of these buffer types and
parameters.

The {\tt buftype} parameter is an integer, with named constants provided
for the three values.

The {\tt params} parameter list consists of an address (pointer) for {\tt buf},
and a one-dimensional array of integers to specify the remaining values.  See
Section~\ref{subsec:buffers} for a discussion of data vectors.

\missing{typed buffers}

\discuss{
Some may want specific values for {\tt buftype}, e.g.
CONTIGUOUS =0, STRIDED=1, GENERAL=2.
}

\subsubsection{Start Mode}

The {\bf MPI\_START\_MODE} function selects a mode for starting a communication
operation.

{\bf MPI\_START\_MODE(mode)}

The mode parameter is an integer, with named constants provided for its two
values.

There are two modes:
\begin{description}
\item[REGULAR]
The operation may start whether or not a matching communication operation has
been posted.
\item[READY]
The operation my start only if a matching communication operation has been
posted.
\end{description}

Thus, a {\bf ready send} can start only if a matching receive is already posted;
otherwise the operation is erroneous and its outcome is undefined.
A {\bf ready receive} can start only if a matching send is already posted;
otherwise the operation is erroneous and its outcome is undefined.

\discuss{
May want to fix the values, e.g., REGULAR=0 and READY=1.

We discussed only ready send, not ready receive.  Ready send is useful when
message passing is implemented in a ``push'' style, where the sender moves the
message to the receiver (common case).  Ready receive would be useful when
message passing is implemented in a ``pull'' style,
where the receiver moves the data from the sender.
}

\subsubsection{Completion Mode}
\label{subsec:completion}

The {\bf MPI\_COMPLETE\_MODE} function selects a mode for completing a
communication operation.

{\bf MPI\_COMPLETE\_MODE(mode)}

The mode parameter is an integer, with named constants provided for its two
values.

There are two modes:
\begin{description}
\item[REGULAR]
The operation completes locally, irrespective of the completion of the
matching operation.
\item[SYNCHRONOUS]
The operation completes only if the matching operation completes too.
\end{description}

A regular send can complete as soon as the message has been composed: data has
been copied out of the send buffer and the values used for the envelope have
been stored.   The sender may now update the send buffer.  A regular send can
complete before the matching receive has completed.

A regular receive can complete as soon as the message has been consumed: data is
available in the receive buffer and all values returned by the send complete
operation are available.  The receiver may now access the receive buffer.
A regular receive may complete before the matching send has completed
(It may seem strange, at first blush, that a receive may complete before
the matching send completes.  However, one should keep in mind
that an operation completes only when the {\tt complete} suboperation
terminates. Thus, even though data has been copied out and the message was sent,
a send has not not yet completed if the {\tt send complete} suboperation has
not yet been invoked. Informally, the send (receive) completes only when the
sender (receiver) knows the operation has completed.)

A synchronous communication operation completes only if the matching operation
completes too.  Thus, a synchronous send can complete as soon as the all
operations preceding the completion of the matching receive have terminated.
A synchronous receive may terminate as soon as the message has been consumed
and all operations preceding the completion of the matching send have
terminated.  Informally,  the completion of the matching send and receive
operations are synchronized.

Matching communication operations must have the same completion mode.  I.e.,
either both send and receive are regular or both are synchronous.  A program
where a regular receive matches a synchronous send (or vice versa) is erroneous
and its outcome is undefined.

\discuss{
May want to fix the values, e.g., REGULAR=0 and SYNCHRONOUS=1.
}

\subsubsection{Communication Start}

{\bf MPI\_START(handle)} \\

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.

\discuss{
Some might prefer two distinct functions:
{\bf MPI\_SEND\_START} and {\bf MPI\_RECV\_START}.
}

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

{\bf MPI\_COMPLETE\_SEND ( handle)} \\

A call to {\bf MPI\_COMPLETE\_SEND} returns when the send operation
identified by
{\tt handle} is complete (see Section~\ref{subsec:completion} for a description
of completion criteria).

{\bf MPI\_COMPLETE\_RECV ( handle, len, source, tag)} \\

A call to {\bf MPI\_COMPLETE\_RECV} returns when the receive operation
identified by
{\tt handle} is complete (see Section~\ref{subsec:completion} for a description
of completion criteria).  The call returns the number of bytes received, and the
source and tag of the message received.

{\bf MPI\_CHECK\_SEND ( handle, flag)} \\

A call to {\bf MPI\_CHECK\_SEND} returns {\tt flag=true} if the send
operation identified by {\tt handle} is complete
(see Section~\ref{subsec:completion}
for a description of completion criteria).  It returns {\tt flag=false},
otherwise. A successful return of {\bf MPI\_CHECK\_SEND} has
the same semantics as a return of {\bf MPI\_COMPLETE\_SEND}.

{\bf MPI\_CHECK\_RECV ( handle, flag, len, source, tag)} \\

A call to {\bf MPI\_CHECK\_RECV} returns {\tt flag=true} if the receive
operation identified by
{\tt handle} is complete (see Section~\ref{subsec:completion} for a description
of completion criteria).  In such case the call returns the number of bytes
received, and the source and tag of the message received.  The call returns {\tt
flag=false}, otherwise.  In such case, the return values of {\tt len}, {\tt
source} and {\tt tag} are undefined.

Implementation notes:

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

A call to {\tt MPI\_COMPLETE\_SEND(handle)} has the same semantics as a busy
loop of the form

\begin{verbatim}
repeat
   MPI_CHECK_SEND(handle, flag)
until(flag=true)
\end{verbatim}

and similarly for receives.   The use of a blocking receive operation ({\tt
MPI\_COMPLETE}) 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\_CHECK}) allows the user to
schedule alternative activities within a single thread of execution.

The intended implementation of {\tt MPI\_CHECK} is for that operation
to return as soon as possible.  Note that it is correct, but inefficient, to
implement {\tt MPI\_CHECK} via a call to {\tt MPI\_COMPLETE}, in which case,
{\tt MPI\_CHECK} always returns {\tt true}.

\discuss{
One might use {\tt len=-1} to indicate unsuccessful return of {\tt
MPI\_CHECK\_RECV}
}

\subsection{Blocking Communication}

Blocking send and receive operations combine all four suboperations into one
call.  The operation returns only when the communication completes and no
communication handle persists after the call completed.

We use the following naming convention for such operations:

\[
\left[ \begin{array}{c} - \\ \bf r \end{array} \right]
\left[ \begin{array}{c} - \\ \bf s \end{array} \right]
\left[ \begin{array}{c} \bf send \\ \bf recv \end{array} \right]
\left[ \begin{array}{c} - \\ \bf s \\ \bf g \end{array} \right]
\]

The first letter (void or {\bf r}) indicates the start mode (regular or ready).
The second letter (void or {\bf s}) indicates the completion mode (regular or
synchronous).  The last letter (void, {\bf s} or {\bf g}) indicates the
buffer type (contiguous, strided or general).   The corresponding
12 send and 12 receive operations are listed below.

{\bf MPI\_SEND(buf, len, dest, tag, context)} \\
is
\begin{verbatim}
handle= MPI_INIT_SEND(dest, tag, context)
MPI_BUFFER(handle, CONTIGUOUS, (len))
MPI_START_MODE(handle, REGULAR)
MPI_COMPLETE_MODE(handle, REGULAR)
MPI_START(handle)
MPI_COMPLETE_SEND(handle)
MPI_FREE(handle)
\end{verbatim}

{\bf MPI\_SENDS(buf, numblk, lenblk, stride, dest, tag, context)} \\
is
\begin{verbatim}
handle= MPI_INIT_SEND(dest, tag, context)
MPI_BUFFER(handle, STRIDED, buf, (numblk, lenblk, stride))
MPI_START_MODE(handle, REGULAR)
MPI_COMPLETE_MODE(handle, REGULAR)
MPI_START(handle)
MPI_COMPLETE_SEND(handle)
MPI_FREE(handle)
\end{verbatim}

{\bf MPI\_SENDG(vector, dest, tag, context)} \\
is
\begin{verbatim}
handle= MPI_INIT_SEND(dest, tag, context)
MPI_BUFFER(handle, GENERAL, (vector))
MPI_START_MODE(handle, REGULAR)
MPI_COMPLETE_MODE(handle, REGULAR)
MPI_START(handle)
MPI_COMPLETE_SEND(handle)
MPI_FREE(handle)
\end{verbatim}

{\bf MPI\_SSEND(buf, len, dest, tag, context)} \\
is
\begin{verbatim}
handle= MPI_INIT_SEND(dest, tag, context)
MPI_BUFFER(handle, CONTIGUOUS, (len))
MPI_START_MODE(handle, REGULAR)
MPI_COMPLETE_MODE(handle, SYNCHRONOUS)
MPI_START(handle)
MPI_COMPLETE_SEND(handle)
MPI_FREE(handle)
\end{verbatim}

{\bf MPI\_SSENDS(buf, numblk, lenblk, stride, dest, tag, context)} \\
is
\begin{verbatim}
handle= MPI_INIT_SEND(dest, tag, context)
MPI_BUFFER(handle, STRIDED, buf, (numblk, lenblk, stride))
MPI_START_MODE(handle, REGULAR)
MPI_COMPLETE_MODE(handle, SYNCHRONOUS)
MPI_START(handle)
MPI_COMPLETE_SEND(handle)
MPI_FREE(handle)
\end{verbatim}

{\bf MPI\_SSENDG(vector, dest, tag, context)} \\
is
\begin{verbatim}
handle= MPI_INIT_SEND(dest, tag, context)
MPI_BUFFER(handle, GENERAL, (vector))
MPI_START_MODE(handle, REGULAR)
MPI_COMPLETE_MODE(handle, SYNCHRONOUS)
MPI_START(handle)
MPI_COMPLETE_SEND(handle)
MPI_FREE(handle)
\end{verbatim}

{\bf MPI\_RSEND(buf, len, dest, tag, context)} \\
is
\begin{verbatim}
handle= MPI_INIT_SEND(dest, tag, context)
MPI_BUFFER(handle, CONTIGUOUS, (len))
MPI_START_MODE(handle, READY)
MPI_COMPLETE_MODE(handle, REGULAR)
MPI_START(handle)
MPI_COMPLETE_SEND(handle)
MPI_FREE(handle)
\end{verbatim}

{\bf MPI\_RSENDS(buf, numblk, lenblk, stride, dest, tag, context)} \\
is
\begin{verbatim}
handle= MPI_INIT_SEND(dest, tag, context)
MPI_BUFFER(handle, STRIDED, buf, (numblk, lenblk, stride))
MPI_START_MODE(handle, READY)
MPI_COMPLETE_MODE(handle, REGULAR)
MPI_START(handle)
MPI_COMPLETE_SEND(handle)
MPI_FREE(handle)
\end{verbatim}

{\bf MPI\_RSENDG(vector, dest, tag, context)} \\
is
\begin{verbatim}
handle= MPI_INIT_SEND(dest, tag, context)
MPI_BUFFER(handle, GENERAL, (vector))
MPI_START_MODE(handle, READY)
MPI_COMPLETE_MODE(handle, REGULAR)
MPI_START(handle)
MPI_COMPLETE_SEND(handle)
MPI_FREE(handle)
\end{verbatim}

{\bf MPI\_RSSEND(buf, len, dest, tag, context)} \\
is
\begin{verbatim}
handle= MPI_INIT_SEND(dest, tag, context)
MPI_BUFFER(handle, CONTIGUOUS, (len))
MPI_START_MODE(handle, READY)
MPI_COMPLETE_MODE(handle, SYNCHRONOUS)
MPI_START(handle)
MPI_COMPLETE_SEND(handle)
MPI_FREE(handle)
\end{verbatim}

{\bf MPI\_RSSENDS(buf, numblk, lenblk, stride, dest, tag, context)} \\
is
\begin{verbatim}
handle= MPI_INIT_SEND(dest, tag, context)
MPI_BUFFER(handle, STRIDED, buf, (numblk, lenblk, stride))
MPI_START_MODE(handle, READY)
MPI_COMPLETE_MODE(handle, SYNCHRONOUS)
MPI_START(handle)
MPI_COMPLETE_SEND(handle)
MPI_FREE(handle)
\end{verbatim}

{\bf MPI\_RSSENDG(vector, dest, tag, context)} \\
is
\begin{verbatim}
handle= MPI_INIT_SEND(dest, tag, context)
MPI_BUFFER(handle, GENERAL, (vector))
MPI_START_MODE(handle, READY)
MPI_COMPLETE_MODE(handle, SYNCHRONOUS)
MPI_START(handle)
MPI_COMPLETE_SEND(handle)
MPI_FREE(handle)
\end{verbatim}

{\bf MPI\_RECV(buf, len, source, tag, context)} \\
is
\begin{verbatim}
handle= MPI_INIT_RECV(source, tag, context)
MPI_BUFFER(handle, CONTIGUOUS, (len))
MPI_START_MODE(handle, REGULAR)
MPI_COMPLETE_MODE(handle, REGULAR)
MPI_START(handle)
MPI_COMPLETE_SEND(handle,len,source,tag)
MPI_FREE(handle)
\end{verbatim}

{\bf MPI\_RECVS(buf, numblk, lenblk, stride, len, source, tag, context)} \\
is
\begin{verbatim}
handle= MPI_INIT_RECV(source, tag, context)
MPI_BUFFER(handle, STRIDED, buf, (numblk, lenblk, stride))
MPI_START_MODE(handle, REGULAR)
MPI_COMPLETE_MODE(handle, REGULAR)
MPI_START(handle)
MPI_COMPLETE_RECV(handle, len, source, tag)
MPI_FREE(handle)
\end{verbatim}

{\bf MPI\_RECVG(vector, len, source, tag, context)} \\
is
\begin{verbatim}
handle= MPI_INIT_RECV(source, tag, context)
MPI_BUFFER(handle, GENERAL, (vector))
MPI_START_MODE(handle, REGULAR)
MPI_COMPLETE_MODE(handle, REGULAR)
MPI_START(handle)
MPI_COMPLETE_RECV(handle, len, source, tag)
MPI_FREE(handle)
\end{verbatim}

{\bf MPI\_SRECV(buf, len, source, tag, context)} \\
is
\begin{verbatim}
handle= MPI_INIT_RECV(source, tag, context)
MPI_BUFFER(handle, CONTIGUOUS, (len))
MPI_START_MODE(handle, REGULAR)
MPI_COMPLETE_MODE(handle, SYNCHRONEOUS)
MPI_START(handle)
MPI_COMPLETE_RECV(handle, len, source, tag)
MPI_FREE(handle)
\end{verbatim}

{\bf MPI\_SRECVS(buf, numblk, lenblk, stride, len, source, tag, context)} \\
is
\begin{verbatim}
handle= MPI_INIT_RECV(source, tag, context)
MPI_BUFFER(handle, STRIDED, buf, (numblk, lenblk, stride))
MPI_START_MODE(handle, REGULAR)
MPI_COMPLETE_MODE(handle, SYNCHRONOUS)
MPI_START(handle)
MPI_COMPLETE_RECV(handle, len, source, tag)
MPI_FREE(handle)
\end{verbatim}

{\bf MPI\_SRECVG(vector, len, source, tag, context)} \\
is
\begin{verbatim}
handle= MPI_INIT_RECV(source, tag, context)
MPI_BUFFER(handle, GENERAL, (vector))
MPI_START_MODE(handle, REGULAR)
MPI_COMPLETE_MODE(handle, SYNCHRONEOUS)
MPI_START(handle)
MPI_COMPLETE_RECV(handle, len, source, tag)
MPI_FREE(handle)
\end{verbatim}

{\bf MPI\_RRECV(buf, len, source, tag, context)} \\
is
\begin{verbatim}
handle= MPI_INIT_RECV(source, tag, context)
MPI_BUFFER(handle, CONTIGUOUS, (len))
MPI_START_MODE(handle, READY)
MPI_COMPLETE_MODE(handle, REGULAR)
MPI_START(handle)
MPI_COMPLETE_RECV(handle, len, source, tag)
MPI_FREE(handle)
\end{verbatim}

{\bf MPI\_RRECVS(buf, numblk, lenblk, stride, len, source, tag, context)} \\
is
\begin{verbatim}
handle= MPI_INIT_RECV(source, tag, context)
MPI_BUFFER(handle, STRIDED, buf, (numblk, lenblk, stride))
MPI_START_MODE(handle, READY)
MPI_COMPLETE_MODE(handle, REGULAR)
MPI_START(handle)
MPI_COMPLETE_RECV(handle)
MPI_FREE(handle)
\end{verbatim}

{\bf MPI\_RRECVG(vector, len, source, tag, context)} \\
is
\begin{verbatim}
handle= MPI_INIT_RECV(source, tag, context)
MPI_BUFFER(handle, GENERAL, (vector))
MPI_START_MODE(handle, READY)
MPI_COMPLETE_MODE(handle, REGULAR)
MPI_START(handle)
MPI_COMPLETE_RECV(handle, len, soure, tag)
MPI_FREE(handle)
\end{verbatim}

{\bf MPI\_RSRECV(buf, len, source, tag, context)} \\
is
\begin{verbatim}
handle= MPI_INIT_RECV(source, tag, context)
MPI_BUFFER(handle, CONTIGUOUS, (len))
MPI_START_MODE(handle, READY)
MPI_COMPLETE_MODE(handle, SYNCHRONOUS)
MPI_START(handle)
MPI_COMPLETE_RECV(handle, len, source, tag)
MPI_FREE(handle)
\end{verbatim}

{\bf MPI\_RSRECVS(buf, numblk, lenblk, stride, len, source, tag, context)} \\
is
\begin{verbatim}
handle= MPI_INIT_RECV(source, tag, context)
MPI_BUFFER(handle, STRIDED, buf, (numblk, lenblk, stride))
MPI_START_MODE(handle, READY)
MPI_COMPLETE_MODE(handle, SYNCHRONEOUS)
MPI_START(handle)
MPI_COMPLETE_RECV(handle, len, source, tag)
MPI_FREE(handle)
\end{verbatim}

{\bf MPI\_RSRECVG(vector, len, source, tag, context)} \\
is
\begin{verbatim}
handle= MPI_INIT_RECV(source, tag, context)
MPI_BUFFER(handle, GENERAL, (vector))
MPI_START_MODE(handle, READY)
MPI_COMPLETE_MODE(handle, SYNCHRONOUS)
MPI_START(handle)
MPI_COMPLETE_RECV(handle, len, source, tag)
MPI_FREE(handle)
\end{verbatim}

Note that all receive calls return the actual length, tag and source of the
received message.  This, the {\tt source}  and {\tt tag} parameters are INOUT.
The {\tt len} parameter is INOUT for contiguous receive buffers, OUT for strided
and general receive buffers.

{\bf Implementation note:}

While these 24 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.

\discuss{

Not all 24 functions are equally important (ready-synchronous is somewhat
esoteric).  We can decide to organize the functins so that the most important
are in a ``core subset''.  But (i) users will use whatever you provide, and will
find uses for what you believed to be useless; (ii) there is a virtue in
being systematic -- no need to remember what works and what does not; (iii) what
is not important can be implemented using multiple calls to the basic functions.

The need for an additional {\tt len} parameter for strided and general receives
is somewhat annoying.  Suggestions?
}

\subsection{Nonblocking Communication}

Nonblocking send and receive operations combine the first two
suboperations ({\tt INIT} and {\tt START}) into
one call, and the last two suboperations ({\tt COMPLETE} or {\tt CHECK} and {\tt
FREE}) into another suboperation.  Thus a nonblocking send or receive consists
of two suboperations:  One that starts the communication, and one that
completes the operation and free any associated resources.  No communication
handle persists after these two suboperations are executed.

\subsubsection{Initiation}

We use the following naming convention for the first suboperation of a
nonblocking communication:

\[
\left[ \begin{array}{c} - \\ \bf r \end{array} \right]
\left[ \begin{array}{c} - \\ \bf s \end{array} \right]
\left[ \begin{array}{c} \bf isend \\ \bf irecv \end{array} \right]
\left[ \begin{array}{c} - \\ \bf s \\ \bf g \end{array} \right]
\]

The first letter (void or {\bf r}) indicates the start mode (regular or ready).
The second letter (void or {\bf s}) indicates the completion mode (regular or
synchronous).  The last letter (void, {\bf s} or {\bf g}) indicates the
buffer type (contiguous, strided or general).   The corresponding
12 send and 12 receive operations are listed below.  The letter {\bf i}
in {\bf isend}
and {\bf irecv} indicates that the operation is ``immediate'' and that the
call may return before the operation is completed.  We thus have 12 immediate
send operations and 12 immediate receive operations.

{\bf MPI\_ISEND(buf, len, dest, tag, context)} \\
is
\begin{verbatim}
handle= MPI_INIT_ISEND(dest, tag, context)
MPI_BUFFER(handle, CONTIGUOUS, (len))
MPI_START_MODE(handle, REGULAR)
MPI_COMPLETE_MODE(handle, REGULAR)
MPI_START(handle)
\end{verbatim}

{\bf MPI\_ISENDS(buf, numblk, lenblk, stride, dest, tag, context)} \\
is
\begin{verbatim}
handle= MPI_INIT_SEND(dest, tag, context)
MPI_BUFFER(handle, STRIDED, buf, (numblk, lenblk, stride))
MPI_START_MODE(handle, REGULAR)
MPI_COMPLETE_MODE(handle, REGULAR)
MPI_START(handle)
\end{verbatim}

{\bf MPI\_ISENDG(vector, dest, tag, context)} \\
is
\begin{verbatim}
handle= MPI_INIT_SEND(dest, tag, context)
MPI_BUFFER(handle, GENERAL, (vector))
MPI_START_MODE(handle, REGULAR)
MPI_COMPLETE_MODE(handle, REGULAR)
MPI_START(handle)
\end{verbatim}

{\bf MPI\_SISEND(buf, len, dest, tag, context)} \\
is
\begin{verbatim}
handle= MPI_INIT_SEND(dest, tag, context)
MPI_BUFFER(handle, CONTIGUOUS, (len))
MPI_START_MODE(handle, REGULAR)
MPI_COMPLETE_MODE(handle, SYNCHRONOUS)
MPI_START(handle)
\end{verbatim}

{\bf MPI\_SISENDS(buf, numblk, lenblk, stride, dest, tag, context)} \\
is
\begin{verbatim}
handle= MPI_INIT_SEND(dest, tag, context)
MPI_BUFFER(handle, STRIDED, buf, (numblk, lenblk, stride))
MPI_START_MODE(handle, REGULAR)
MPI_COMPLETE_MODE(handle, SYNCHRONOUS)
MPI_START(handle)
\end{verbatim}

{\bf MPI\_SISENDG(vector, dest, tag, context)} \\
is
\begin{verbatim}
handle= MPI_INIT_SEND(dest, tag, context)
MPI_BUFFER(handle, GENERAL, (vector))
MPI_START_MODE(handle, REGULAR)
MPI_COMPLETE_MODE(handle, SYNCHRONEOUS)
MPI_START(handle)
\end{verbatim}

{\bf MPI\_RISEND(buf, len, dest, tag, context)} \\
is
\begin{verbatim}
handle= MPI_INIT_SEND(dest, tag, context)
MPI_BUFFER(handle, CONTIGUOUS, (len))
MPI_START_MODE(handle, READY)
MPI_COMPLETE_MODE(handle, REGULAR)
MPI_START(handle)
\end{verbatim}

{\bf MPI\_RISENDS(buf, numblk, lenblk, stride, dest, tag, context)} \\
is
\begin{verbatim}
handle= MPI_INIT_SEND(dest, tag, context)
MPI_BUFFER(handle, STRIDED, buf, (numblk, lenblk, stride))
MPI_START_MODE(handle, READY)
MPI_COMPLETE_MODE(handle, REGULAR)
MPI_START(handle)
\end{verbatim}

{\bf MPI\_RISENDG(vector, dest, tag, context)} \\
is
\begin{verbatim}
handle= MPI_INIT_SEND(dest, tag, context)
MPI_BUFFER(handle, GENERAL, (vector))
MPI_START_MODE(handle, READY)
MPI_COMPLETE_MODE(handle, REGULAR)
MPI_START(handle)
\end{verbatim}

{\bf MPI\_RSISEND(buf, len, dest, tag, context)} \\
is
\begin{verbatim}
handle= MPI_INIT_SEND(dest, tag, context)
MPI_BUFFER(handle, CONTIGUOUS, (len))
MPI_START_MODE(handle, READY)
MPI_COMPLETE_MODE(handle, SYNCHRONEOUS)
MPI_START(handle)
\end{verbatim}

{\bf MPI\_RSISENDS(buf, numblk, lenblk, stride, dest, tag, context)} \\
is
\begin{verbatim}
handle= MPI_INIT_SEND(dest, tag, context)
MPI_BUFFER(handle, STRIDED, buf, (numblk, lenblk, stride))
MPI_START_MODE(handle, READY)
MPI_COMPLETE_MODE(handle, SYNCHRONOUS)
MPI_START(handle)
\end{verbatim}

{\bf MPI\_RSISENDG(vector, dest, tag, context)} \\
is
\begin{verbatim}
handle= MPI_INIT_SEND(dest, tag, context)
MPI_BUFFER(handle, GENERAL, (vector))
MPI_START_MODE(handle, READY)
MPI_COMPLETE_MODE(handle, SYNCHRONOUS)
MPI_START(handle)
\end{verbatim}

{\bf MPI\_IRECV(buf, len, source, tag, context)} \\
is
\begin{verbatim}
handle= MPI_INIT_RECV(source, tag, context)
MPI_BUFFER(handle, CONTIGUOUS, (len))
MPI_START_MODE(handle, REGULAR)
MPI_COMPLETE_MODE(handle, REGULAR)
MPI_START(handle)
\end{verbatim}

{\bf MPI\_IRECVS(buf, numblk, lenblk, stride, len, source, tag, context)} \\
is
\begin{verbatim}
handle= MPI_INIT_RECV(source, tag, context)
MPI_BUFFER(handle, STRIDED, buf, (numblk, lenblk, stride))
MPI_START_MODE(handle, REGULAR)
MPI_COMPLETE_MODE(handle, REGULAR)
MPI_START(handle)
\end{verbatim}

{\bf MPI\_IRECVG(vector, len, source, tag, context)} \\
is
\begin{verbatim}
handle= MPI_INIT_RECV(source, tag, context)
MPI_BUFFER(handle, GENERAL, (vector))
MPI_START_MODE(handle, REGULAR)
MPI_COMPLETE_MODE(handle, REGULAR)
MPI_START(handle)
\end{verbatim}

{\bf MPI\_SIRECV(buf, len, source, tag, context)} \\
is
\begin{verbatim}
handle= MPI_INIT_RECV(source, tag, context)
MPI_BUFFER(handle, CONTIGUOUS, (len))
MPI_START_MODE(handle, REGULAR)
MPI_COMPLETE_MODE(handle, SYNCHRONOUS)
MPI_START(handle)
\end{verbatim}

{\bf MPI\_SIRECVS(buf, numblk, lenblk, stride, len, source, tag, context)} \\
is
\begin{verbatim}
handle= MPI_INIT_RECV(source, tag, context)
MPI_BUFFER(handle, STRIDED, buf, (numblk, lenblk, stride))
MPI_START_MODE(handle, REGULAR)
MPI_COMPLETE_MODE(handle, SYNCHRONOUS)
MPI_START(handle)
\end{verbatim}

{\bf MPI\_SIRECVG(vector, len, source, tag, context)} \\
is
\begin{verbatim}
handle= MPI_INIT_RECV(source, tag, context)
MPI_BUFFER(handle, GENERAL, (vector))
MPI_START_MODE(handle, REGULAR)
MPI_COMPLETE_MODE(handle, SYNCHRONOUS)
MPI_START(handle)
\end{verbatim}

{\bf MPI\_RIRECV(buf, len, source, tag, context)} \\
is
\begin{verbatim}
handle= MPI_INIT_RECV(source, tag, context)
MPI_BUFFER(handle, CONTIGUOUS, (len))
MPI_START_MODE(handle, READY)
MPI_COMPLETE_MODE(handle, REGULAR)
MPI_START(handle)
\end{verbatim}

{\bf MPI\_RIRECVS(buf, numblk, lenblk, stride, len, source, tag, context)} \\
is
\begin{verbatim}
handle= MPI_INIT_RECV(source, tag, context)
MPI_BUFFER(handle, STRIDED, buf, (numblk, lenblk, stride))
MPI_START_MODE(handle, READY)
MPI_COMPLETE_MODE(handle, REGULAR)
MPI_START(handle)
\end{verbatim}

{\bf MPI\_RIRECVG(vector, len, source, tag, context)} \\
is
\begin{verbatim}
handle= MPI_INIT_RECV(source, tag, context)
MPI_BUFFER(handle, GENERAL, (vector))
MPI_START_MODE(handle, READY)
MPI_COMPLETE_MODE(handle, REGULAR)
MPI_START(handle)
\end{verbatim}

{\bf MPI\_RSIRECV(buf, len, source, tag, context)} \\
is
\begin{verbatim}
handle= MPI_INIT_RECV(source, tag, context)
MPI_BUFFER(handle, CONTIGUOUS, (len))
MPI_START_MODE(handle, READY)
MPI_COMPLETE_MODE(handle, SYNCHRONOUS)
MPI_START(handle)
\end{verbatim}

{\bf MPI\_RSIRECVS(buf, numblk, lenblk, stride, len, source, tag, context)} \\
is
\begin{verbatim}
handle= MPI_INIT_RECV(source, tag, context)
MPI_BUFFER(handle, STRIDED, buf, (numblk, lenblk, stride))
MPI_START_MODE(handle, READY)
MPI_COMPLETE_MODE(handle, SYNCHRONOUS)
MPI_START(handle)
\end{verbatim}

{\bf MPI\_RSIRECVG(vector, len, source, tag, context)} \\
is
\begin{verbatim}
handle= MPI_INIT_RECV(source, tag, context)
MPI_BUFFER(handle, GENERAL, (vector))
MPI_START_MODE(handle, READY)
MPI_COMPLETE_MODE(handle, SYNCHRONOUS)
MPI_START(handle)
\end{verbatim}

\subsubsection{Completion}

A communication operation can be completed in two ways:  (i) By a call to {\tt
MPI\_WAIT}.  Such call returns when the corresponding operation has completed.
(ii) by a call to {\tt MPI\_STATUS}.  Such call returns successfully if the
communication operation has completed; it may also return unsuccessfully if the
operation has not completed.  See Section~\ref{subsec:complete_ops} for a
discussion of the two completion operation types.

{\bf MPI\_WAIT\_SEND(handle)} \\
is
\begin{verbatim}
MPI_COMPLETE_SEND(handle)
MPI_FREE(handle)
\end{verbatim}

{\bf MPI\_WAIT\_RECV(handle, len, source, type)} \\
is
\begin{verbatim}
MPI_COMPLETE_RECV(handle, len, source, type)
MPI_FREE(handle)
\end{verbatim}

{\bf MPI\_STATUS\_SEND(handle, flag)} \\
is
\begin{verbatim}
MPI_CHECK_SEND(handle, flag)
if (flag) MPI_FREE(handle)
\end{verbatim}

{\bf MPI\_STATUS\_RECV(handle, len, source, type)} \\
is
\begin{verbatim}
MPI_CHECK_RECV(handle, flag, len, source, type)
if (flag) MPI_FREE(handle)
\end{verbatim}

\paragraph*{Multiple Receives}

It is convenient to be able to wait for any successful receive in a set, rather
than having to wait for specific message.

{\bf MPI\_WAITANY\_RECV ( list\_of\_handles, index, len, source, tag)}
\\ {\bf list\_of\_handles} is an array containing $(\rm n,
handle_1 , ... , handle_n)$.

Blocks until one of the operations associated with
handles in the array has completed.  Returns the index of that handle in the
array, and the length,  source and tag of the received message.

{\bf MPI\_WAITANY\_RECV ( list\_of\_handles, index, len, source, tag} \\
is
\begin{verbatim}
   {MPI_WAIT_RECV (handle[1], len, source, tag); index = 1} ||
   ...                                                      ||
   {MPI_WAIT_RECV (handle[n], len, source, tag); index = n}
\end{verbatim}

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

\discuss{

An alternative definition of {\tt WAITANY} is to require that the first
available message in the list is received.  I.e.

{\bf MPI\_WAITANY\_RECV ( list\_of\_handles, index, len, source, tag)} \\
is \\
{\tt
for(index=1; i$<=$n; i++) \{  \\
\ \ \ MPI\_STATUS\_RECV (handle[index], flag, len, source, tag); \\
\ \ \ if(flag) break; \\
\ \ \ \}
}

A difference would occur in the case where two receives in the list match the
same message; in the original definition any of the two may succeed, whereas
in the amended definition only the first one can succeed.   This additional
determinism, may, on the other hand, restrict concurrency in the implementation
of {\tt WAITANY}.

It would be nice to have a WAITALL that waits for the completion of all
operations listed in the list\_of\_handles.  The most useful option might be,
in fact, ``wait for the completion of ALL pending operations in the current
context'', which could be specified by a ``wildcard'' list\_of\_handles
(e.g., a length zero list).
}

\paragraph*{Probe}

It is convenient for a receiver to be able to check for pending messages that
can be received, before executing a receive operation.  This, for example, would
allow the receiver to allocate a receive buffer of the right size, when the size
of incoming messages is not known ahead of time.

The {\bf PROBE} call specifies an envelope pattern.  It returns a handle to
an available message with an envelope that matches the pattern, and that does
not match any pending receive.  It also returns the actual values
of {\tt len} {\tt source} and {\tt tag}.  The message is now ``locked'' and can
be received only by an operation that uses the handle returned.   If there is no
matching message, then {\tt probe} returns with a NULL handle.

{\bf MPI\_PROBE(len, source, tag, context, handle)} \\
If there is a matching message that is not matched by a previously posted
nonblocking receive, returns message length, the actual values of source and
tag, and a handle that must be used to receive
the message.  Otherwise, returns a handle with value {\bf NULL} (NULL is a
named constant).

{\bf MPI\_PRECV ( buf, len, handle)}   \\
Nonblocking receive of probed message into a contiguous buffer.

{\bf MPI\_PRECVS ( buf, numblk, lenblk, stride, handle)} \\
Nonblocking receive of probed message into a fixed stride buffer.

{\bf MPI\_PRECVG ( datavector,  handle)} \\
Nonblocking receive of probed message into a buffer specified by a data
vector.

\discuss{
May want a specific value for NULL, e.g., NULL=0

May need to return more than length, for typed messages.
}

\subsection{Correctness}

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

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 handles.  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
Each process can create at least one communication handle.  I.e., if a
process executes an {\tt MPI\_INIT\_SEND} or {\tt MPI\_INIT\_RECV} operation,
and has no other active handle, then the operation eventually succeeds.
It is highly desirable to have generous bounds on the number of
concurrently active communication handles 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 handle.
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\_SEND} 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\_RECV} 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 ids 1 and 2)

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

IF (GETID() == 1) {
   MPI_SEND(buf=sendbuf, len=1000, dest=2, tag=0);
   MPI_RECV(buf=recvbuf, len=1000, source=2, tag=0);
   }
ELSE \* (GETID() == 2) *\  {
   MPI_RECV(buf=recvbuf, len=1000, source=1, tag=0);
   MPI_SEND(buf=sendbuf, len=1000, dest=1, type=0);
   }
\end{verbatim}

The following program is erroneous, and should always fail.

\begin{verbatim}

IF (GETID() == 1) {
   MPI_SSEND(buf=sendbuf, len=1000, dest=2, tag=0);
   MPI_SRECV(buf=recvbuf, len=1000, source=2, tag=0);
   }
ELSE  \* (GETID() == 2) *\ {
   MPI_SSEND(buf=sendbuf, len=1000, dest=1, tag=0);
   MPI_SRECV(buf=recvbuf, len=1000, source=1, tag=0);
   }
\end{verbatim}

The send operation of the 1st process can complete only if the matching receive
of the second processor is executed; the send operation of the second processor
can complete only if the matching receive of the first processor is executed.
This program will deadlock.

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

\begin{verbatim}

IF (GETID() == 1) THEN {
   MPI_SEND(buf=sendbuf, len=1000000, dest=2, tag=0);
   MPI_RECV(buf=recvbuf, len=1000000, source=2, tag=0);
   }
ELSE \* (GETID() == 2) *\ {
   MPI_SEND(buf=sendbuf, len=1000000, dest=1, tag=0);
   MPI_RECV(buf=recvbuf, len=1000000, source=1, tag=0);
   }
\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 1 MgB 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.

\subsection{Error Handling}

\subsubsection{Communication Errors}

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 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.

The other errors can be divided in two classes:
\begin{description}
\item[resource errors]
Errors that occur in an unsafe programs because of limitations on the resources
of the communication subsystem, but would not occur if these subsystem had
unbounded resources (buffer overflow, no available handles, etc.)
\item[program errors]
Errors that result in an erroneous program that will always fail.
(send with no matching receive, send to nonexistent destination, etc.)
\end{description}

Program errors always result in an exception, if detected.  MPI will
provide two mechanisms for handling resource errors:  In {\em system mode} each
MPI call may return with a return code that indicates that a resource error was
detected; no exception occur, and the program may recover in normal execution
mode.  In {\em user mode} a detected resource error causes an exception.

\discuss{
Program errors cannot always be distinguished from resource errors.  Have to
decide how to handle doubtful cases in system mode.

Need to change the syntax so that all return values (error code excepted) are
returned via parameters.

It's reasonable to restrict system mode to C and C++ bindings.
}
\end{document}