Subject: A suggestion for a multi-level MPI

From: Rusty Lusk <[email-masked]>
Date: Tue, 09 Feb 93 01:02:54 CST

Last week Tom Henderson asked for more detail about the multiple-level
proposal, so we wrote up a slightly more detailed explanation of the idea,
with some examples, which is appended at the end of this note.

It is partly subsumed by Marc Snir's posting of a thoroughly worked out
point-to-point proposal, which has a lot in common with what we described as
Levels 1 and 2.  A few notes:

In Level 1, we use a very minimal set of required parameters in the "init"
calls, so that more of the parameters can be reset inside a loop without
acquiring a new handle.  

We really think that Levels 3 and 4 (the simpler levels, where there are fewer
options and parameters) are necessary in order to provide a simple interface
for basic users.

We didn't change the way heterogeneity is handled, but Tom Henderson's
suggestion (that the datatypes *always* be specified, perhaps with a BYTES type
for the "raw" datatype) is a quite sensible one.

Here is a medium-sized description of what we mean by a "multi-level"
standard.  The specific routines and their parameters are not as important as
the idea that complexity can be managed in this way.

----------------------------------------------------------------------

\documentstyle[11pt]{article}
\textwidth=6.0in
\textheight=9.0in
\hoffset=-0.5in
\voffset=-1.0in
\parskip=.1in
\def\explicitspace{\hbox{\vrule height 2pt width .5pt 
                   \vbox to 8pt{\vfil\hrule height .5pt width 6pt}%
                   \vrule height 2pt width .5pt}}

\begin{document}
\title{\Large \bf A Proposal for a Multi-Level 
                  Message-Passing Interface Standard}
\author{
        {\it William D. Gropp and Ewing L. Lusk} \\
        Argonne National Laboratory \\
        Argonne, IL 60439 \\
        [email-masked] \\
        [email-masked] 
}

\date{}
\maketitle
\begin{center}
  {\large \it DRAFT}
\end{center}

\section{Introduction}
\label{sec:introduction}

In \cite{gropp-lusk:mpi1} we described the organization of a library of
routines that could be used to implement a standard set of message-passing
functions.  We used the library to rapidly implement most of the routines
described in \cite{dongarra-hempel-hey-walker:october-draft}.  The
implementation testbed was not originally offered as a counterproposal to the
routines described in \cite{dongarra-hempel-hey-walker:october-draft} since no
real discussion had taken place in the MPI Committee yet, but it did contain
many capabilities we believed would ultimately be desired.  It was constructed
in a way that offered a wide range of capabilities with a minimum of
complexity in syntax.  Basically, it consisted of a large number of separate
routines whose names were orthogonally organized along a set of axes
corresponding to synchronization type, buffer structure, high-performance
mode, and heterogeneity specification.  See \cite{gropp-lusk:mpi1} for
details.

At the MPI meeting in January, it became apparent that 

\begin{itemize}
\item Many of the committee members were uncomfortable with having a large
  number of routines.
\item A very wide range of capabilities and options was nonetheless desired.
\item A very wide range of users was to be targeted, from experienced users
  requiring access to high-performance operations to beginning users requiring
  simplicity in both syntax and semantics.
\item While discussion of precise syntax was deferred, it might be useful to
  suggest one, in order that everyone could see what the ultimate standard
  might look like.
\end{itemize}

We added a further consideration of our own:

\begin{itemize}
\item The standard needs a way to expand in order to add functionality or
  options that have not been envisioned yet, without becoming incompatible
  with itself.
\item An implementation would have to be extremely adaptable if it was
  expected to be able to track the discussions of the MPI Committee.

\end{itemize}

The present draft is a reflection of these considerations.  It is still
incomplete (as are the committee's discussions) but is offered in the hope
that it might be useful.  It focuses primarily on the point-to-point
operations.

\section{The Basic Idea:  Orthogonality of Function}
\label{sec:orthogonality}

The MPI committee has discussed a large number of options for point-to-point
message passing.  The fact that there could be as many as a thousand different
``send'' routines has become a joke, and some believe that the scope of
MPI way have to restricted in order that it not become unwieldy.

This problem has at least two solutions, and we explore each of them here.
What makes the porblem tractable is that the options that are being discussed
are {\it orthogonal\/}; that is, choice of one value of an option does not
determine what value another opetion must have.  For example, whether a send
is blocking or nonblocking is completely independent of whether the message
consists of contiguous memory or not.  This orthogonality can be exploited to
make the interface simple to specify, implement, and use, while at the same
time not sacrificing flexibility.

The first way is to set the options with a ``universal'' {\tt
set\_option(handle,option,value)} routine.  There will be a small number of
allowed values for {\tt option}, and for most of these, a small number of
values for {\tt value}.  (This is the approach taken in Level I, below.)

The second way is to absorb the options and their values into the routine
names.  This leads to a large {\em number\/} of routines, but their names can
be made predictable and descriptive, so that they are easy to understand and
use.  (This is the approach taken in Level II, below.)

The principal organizing idea of this library is that it proposes multiple
sets of routines, roughly grouped by complexity level, {\it all of which are
proposed for simultaneous inclusion as part of the MPI Standard}.  That is,
although it is possible to implement some of the higher-level routines in
terms of the lower ones, either by combining short sequences of low-level
calls or by supplying specific values for parameters, it is strongly suggested
here that all levels be adopted together.  This is the way to attain a set of
routines that, taken altogether, offers complete flexibility for the advanced
user while not imposing any unnecessary complexity in either syntax or
semantics on the beginner.  The relationships among the levels remain
extremely useful for defining the semantics of the higher-level routines in
terms of the lower level ones, which have simpler semantics.

We now describe the four ``levels'' of MPI routines.  For expository purposes,
we describe them in what might be considered an unnatural order:
\begin{description}
\item[Level IV] The highest level, consisting of only four routines, suitable
  for beginning users.
\item[Level I] The lowest level, giving complete access to all of the
  facilities offered by the MPI Standard.  The actual number of routines is
  small.
\item[Level III] A middle level, required in order to write programs that
  are more efficient and portable than those expressible with Level IV.  This
  is the approximate level of most current message-passing systems.
\item[Level II] A level between I and III, chosen for convenience of use
  without giving up the features of Level I and possible added efficiency in
  the implementation.  It corresponds roughly to the set of routines described
  in \cite{gropp-lusk:mpi1}.
\end{description}

It is to be emphasized that this layered structure is for ease of definition
and convenience of use, and does not imply a layered structure for the
implementation, which could result in suboptimal efficiency.  Likewise, it is
not suggested here that a user would have to pick one of the layers and stick
with it.  In all cases where it makes sense,  the layers should be
interoperable;  that is, routines from all layers may appear in the same
program. 

\section{The Point-to-point MPI routines}
\label{sec:pt-to-pt}

Note on syntax: we have to pick {\em some\/} syntax in order to write these
down clearly.  We leave the selection of an elegant, expressive, complete,
intuitive syntax and appropriate language bindings to the further discussions
of the MPI Committee.

\subsection{Level IV:  The Four-function Interface}
\label{sec:four-func}

A large number of parallel algorithms can be expressed in terms of four
simple functions.  In the quest for simplicity, it is useful to see how far
the standard might be able to go.  It appears to us that the following set of
routines represents a minimum.  (Strictly speaking, only two of these belong
in this point-to-point section, but it is not worth separating this tiny set
of routines into parts.)

\begin{verbatim}
   MPI_numpids()    returns the number of active process ID's
   MPI_mypid()      returns the id of the calling process
   MPI_send(dest,tag,buffer,length)
                    sends the contiguous set of length bytes addressed by
                    buffer to process dest and tags the message with tag.
                    The buffer is available for reuse when this returns.
   MPI_recv(dest,tag,buffer,length)
                    waits for a message from process dest with tag tag and
                    puts in buffer, truncating it to length if necessary
                    for it to fit into buffer.
\end{verbatim}

More precise definitions of these can be made once we have defined the lower
levels.  Basically, the point-to-point component consists of an asynchronous
send that blocks only until the buffer can be reused, and a blocking receive
that waits for the arrival of a message.

\subsection{Level I:  Access to complete functionality in a small number of
routines}
\label{sec:level1}

The above trivial interface is enough to specify a parallel program, and in
many cases, is actually sufficient.  The only reason for adding more
point-to-point routines is to improve efficiency, portability, and convenience.
Before defining what perhaps will be the most commonly-used layer for most
programmers (Level III), we go down to Level I, where all of the MPI
capabilities will be exposed.  We can then describe the intermediate layers
more easily, in terms of the lowest one.

The idea here is to fully exploit for the lowest level two ideas that
were discussed favorably at the January meeting:

\begin{itemize}
\item separation of the ``setup'' part of an operation from the
  ``initiate'' part.  This idea is described in detail in \cite{snir:notes}.
\item the use of a control structure (either in system space or user space) to
  hold the parameters for an operation that has been ``set up'', but  is not
  complete.  (It may or may not have been initiated.)  This structure serves as
  the ``handle'' for the operation.  Its precise format depends on the MPI
  implementation, and it is accessed by the user only through MPI routines.
\end{itemize}

\begin{verbatim}
   handle = MPI_init_send(dest,tag)
   handle = MPI_init_recv()
            MPI_mod_send(handle,option,value)
            MPI_mod_recv(handle,option,value)
            MPI_do_send(handle) 
            MPI_do_recv(handle)
            MPI_free(handle)
\end{verbatim}

The idea is that the ``init'' routines return a handle that is usable {\em as
is\/}, because it selects a reasonable set of defaults, but that can be
modified before the operations is actually initiated.  If the {\tt do\_send}
or {\tt do\_recv} operations are issued without any intervening calls to {\tt
mod} routines, then the default behavior occurs, which we will have to decide
on.  However a wide range of options can be set by the {\tt MPI\_mod\_send}
and {\tt MPI\_mod\_recv} routines.

Although we are not intending to specify an implementation, it will perhaps
clarify things to envision how this might work.  The {\tt init} routines will
allocate a block of storage (or, alternatively, deal with a block a storage
allocated by the user).  The ``do'' routines will take their parameters from
this control block.  The control block will be immediately usable, since the
minimal parameters will be specified on the ``init'' call.  (A send doesn't
make sense without a destination and a tag, so they are its parameters.  A
receive need specify no filtering by tag or sender, and could receive a
message of 0 bytes, requiring no buffer, hence the {\tt recv\_init} has no
parameters.)

The {\tt MPI\_mod\_send} and {\tt MPI\_mod\_recv} are used to modify the
default parameters set up by the {\tt MPI\_init\_send} and {\tt
MPI\_init\_recv} routines.  The parameters to the {\tt MPI\_mod} routines are
as follows:
\begin{description}
\item[handle] the value returned by a previous {\tt MPI\_init\_send} or {\tt MPI\_init\_recv}.
\item[option] one of a collection of symbolic constants specifying the
  parameter being set.
\item[value] one of a collection of symbolic constants or integers or
  addresses, depending on the option.
\end{description}

One suggestion for a set of options and their allowed values might be:
\begin{verbatim}
  option      value
  -------     -------
  BUFTYPE  -  one of CONTIG, STRIDED, VEC, HVEC
  BLOCKING -  one of NONE, LOCAL, GLOBAL
  TRANSLAT -  one of NONE, XDR
  PROTOCOL -  one of PLAIN, RCVRRDY

  BUFADD   -  address of buffer, or NULL
  BUFLEN   -  integer lengh of buffer
  DATATYPE -  one of INT, FLOAT, DOUBLE, LONGINT, BYTES, CHAR
  TAG      -  integer or (on receive) ANY
  BUFVEC   -  address of structure describing the buffer data, or NULL
  SOURCE   -  (on receive) integer process id, or ANY
\end{verbatim}
The {\tt MPI\_init\_send(dest,tag)} could reasonably set the following
defaults, in addition to setting the {\tt dest} and {\tt tag} fields in the
control block:
\begin{verbatim}
  BUFTYPE = CONTIG
  BLOCKING = LOCAL
  TRANSLAT = NONE
  PROTOCOL = PLAIN

  BUFADD = NULL
  BUFLEN = 0
  DATATYPE = BYTES
  BUFVEC = NULL
\end{verbatim}
The {\tt MPI\_init\_recv()} could set the same default values, together with 
{\tt SOURCE = ANY} and {\tt TAG = ANY}.  (In a real proposed standard, these
symbolic constants should have an MPI prefix, in order to prevent the
name-space pollution problem, but here we leave them off for simplicity.)

The large number of routines listed in \cite{gropp-lusk:mpi1}, some of which
will reappear in Level II, have in Level IV been absorbed into parameter
values of the {\tt MPI\_mod\_send} and {\tt MPI\_mod\_recv} routines, in
particular the first four values of {\tt option}.  The advantages of this
approach are:
\begin{itemize}
\item a small number of routines at the lowest level
\item extensibility: new options, even implementation-specific ones, can be
  handled by adding more options without adding more routines.
\end{itemize}
The disadvantage is that to send a message requires a sequence of subroutine
calls, adding both program complexity and a moderate amount of overhead to
each operation.  It is this problem that is addressed by level II.

\subsection{Level III: A Medium-Level Interface}
\label{sec:level3}

In this section we describe a level that is designed to provide access to a
sufficient set of MPI routines that efficient, portable programs may be
written in it, without accessing all of the flexibility of the complete MPI
interface.  This level will, however, support both blocking and non-blocking
sends and receives as well as messages between machines from different
vendors.  By imposing a few restrictions on what can be done at this level,
however, we can reduce the number of routines and shorten parameter lists,
thus reducing complexity.  A possible set of restrictions for this level might
be:
\begin{itemize}
\item No noncontiguous buffer structures
\item No mixed datatypes in messages destined for heterogeneous processors
\item No ``rendezvous'' send
\item No ``receiver-ready'' messages
\end{itemize}
Programmers who need more functionality than is offered at this level can use
the routines in levels I or II.  The set of Level III routines, given the
above restrictions, looks like

\[
    \left[ \begin{array}{c}
            n \\ b
           \end{array}
    \right]
    \left[ \begin{array}{c}
            send \\ recv
           \end{array}
    \right]
    \left[ \begin{array}{c}
             \explicitspace \\ h
           \end{array}
    \right],
\]

\noindent
together with the {\tt wait} and {\tt status} routines.  The first column
specifies whether the opertion is to block or not, and the last column
specifies whether the message is to be translated for transmission to a
machine with a different data representation.

That is, the above diagram ellustrates the way the names are to made up.
Since in this case the list is relatively short, we can also list them:
\begin{verbatim}
bsend(tag,dest,bufadd,buflen)
nsend(tag,dest,bufadd,buflen)
bsendh(tag,dest,bufadd,datatype,numitems)
nsendh(tag,dest,bufadd,datatype,numitems)
brecv(tag,dest,bufadd,buflen)
nrecv(tag,dest,bufadd,buflen)
brecvh(tag,dest,bufadd,datatype,numitems)
nrecvh(tag,dest,bufadd,datatype,numitems)
\end{verbatim}

\subsection{Level II:  Flexibility and Efficiency in a large number of
routines}
\label{sec:level2}

For Level II, we use only the naming schematic, since the list becomes rather
long.  The first column represents the choice of buffer structure ({\tt
BUFTYPE} in Level I).  The second column specifies the blocking option ({\tt
BLOCKING}).  Then whether it is a send or receive, then the {\tt TRANSLAT}
option, and finally the receiver-ready protocol ({\tt PROTOCOL = RCVRRDY}).

\[  \left[ \begin{array}{c}
            c \\ s \\ g
           \end{array}
    \right]
    \left[ \begin{array}{c}
            n \\ b \\ s
           \end{array}
    \right]
    \left[ \begin{array}{c}
            send \\ recv
           \end{array}
    \right]
    \left[ \begin{array}{c}
             \explicitspace \\ h
           \end{array}
    \right]
    \left[ \begin{array}{c}
             \explicitspace \\ rr
           \end{array}
    \right],
\]

\noindent
See \cite{gropp-lusk:mpi1} for details.

\section{Examples of the Multi-Level Approach}
\label{sec:examples}

Before giving the details, we give three examples of how certain operations
would be expressed at teach of the levels.  Note that some operations are not
available at the higher levels. The point is that simple operations should be
simple to express while more sophisticated ones may be more complicated.

\paragraph{Example 1.}  A blocking send of a contiguous stream of
uninterpreted bytes.

At Level IV (the four-function level) nothing but the basic parameters needs
to specified, since this is the only type of send operation.
\begin{verbatim}
  MPI_send(dest,tag,buf,len)
\end{verbatim}
At Level III, where both blocking and non-blocking sends are possible, we
need to specify that this is a blocking send.  We choose to incorporate the
specification into the routine name.
\begin{verbatim}
  MPI_sendb(dest,tag,buf,len)
\end{verbatim}
At Level II, noncontiguous buffers are allowed, so we need to specify that the
buffer is contiguous, which we again do with the name.
\begin{verbatim}
  MPI_csendb(dest,tag,buf,len)
\end{verbatim}
At Level I, we need to set up the operation first, then modify the default
parameters of the operation before actually initiating it.
\begin{verbatim}
  handle = MPI_init_send(dest,tag)
  MPI_mod_send(handle,BUFADD,buf)
  MPI_mod_send(handle,BUFLEN,len)
  MPI_mod_send(handle,BLOCKING,LOCAL)
  MPI_do_send(handle)
  MPI_send_wait(handle)
  MPI_send_free(handle)
\end{verbatim}

\paragraph{Example 2.}  A non-blocking receive of data that is all of the same
type into a contiguous buffer, with translation for receipt from a process on
a machine with a possibly different data representation.

At Level IV, this operation is impossible to express.

At Level III, the specification that is it is non-blocking and heterogeneous
is encoded in the name, which specifies a routine that expects a datatype and
number of items, rather than a length.
\begin{verbatim}
  handle = MPI_nrecvh(source,tag,buf,datatype,numvals)
\end{verbatim}
At Level II, we must also specify that the buffer is contiguous.
\begin{verbatim}
  handle = MPI_cnrecvh(source,tag,buf,datatype,numvals)
\end{verbatim}
At Level I, we set up the operation and then modify its parameters.
\begin{verbatim}
  handle = MPI_init_recv()
  MPI_mod_recv(handle,SOURCE,source)
  MPI_mod_recv(handle,TAG,tag)
  MPI_mod_recv(handle,BUFADD,buf)
  MPI_mod_recv(handle,BUFTYPE,CONTIG)
  MPI_mod_recv(handle,TRANSLATE,XDR)
  MPI_mod_recv(handle,DATATYPE,datatype)
  MPI_mod_recv(handle,NUMVALS,numvals)
  MPI_do_recv(handle)
  MPI_recv_status(handle)
\end{verbatim}

\paragraph{Example 3.}  A non-blocking send of non-contiguous, mixed
heterogeneous data, with the assumption that the receiver has already issued
his receive.

At Levels IV and III, this is impossible to express.

At Level II, most of the options are encoded in the name.
\begin{verbatim}
  MPI_gsendhrr(dest,tag,...)
\end{verbatim}
At Level I, we use the same basic routines to set the options.
\begin{verbatim}
  handle = MPI_init_send(dest,tag)
  MPI_mod(handle,BUFTYPE,HVEC)
  (Build vector describing data locations, types, and numbers of items in
    each clump.)
  MPI_mod_send(handle,HVECADD,vec)
  MPI_mod_send(handle,TRANSLATE,XDR)
  MPI_mod_send(handle,RECVRRDY,TRUE)
  MPI_do_send(handle)
\end{verbatim}

\paragraph{Example 4.}  Set up a channel from one process to another, and then
use it for repeated send operations of different data.

This operation cannot be specified at Levels II, III, or IV.

At Level I, it can be specified in the following way.
\begin{verbatim}
  handle = MPI_init_send(dest,tag)
  begin loop
    MPI_mod_send(handle,BUFADD,buf)
    MPI_mod_send(handle,BUFLEN,len)
    MPI_do_send(handle)
  end loop
\end{verbatim}

\section{Collective Communication}
\label{sec:collective}

The idea of a separate setup routine, together with multiple levels to
accomodate both and basic operations as well as more elaborate ones, should
prove useful for collective operations as well.  We will try to extend the
point-to-point operations to collective operations in as natural a way as
possible. 

\bibliographystyle{plain}

\begin{thebibliography}{1}

\bibitem{dongarra-hempel-hey-walker:october-draft}
J.~Dongarra, R.~Hempel, T.~Hey, and D.~Walker.
\newblock A proposal for a message passing interface standard.
\newblock (circulated before November meeting).

\bibitem{gropp-lusk:mpi1}
Bill Gropp and Rusty Lusk.
\newblock A test implementation of the {MPI} draft message-passing interface
  standard.
\newblock Technical Report ANL--92--47, Argonne National Laboratory, December
  1992.
\newblock (circulated at January meeting).

\bibitem{snir:notes}
Marc Snir.
\newblock Message-passing interface--outline.
\newblock (circulated at January meeting).

\end{thebibliography}

\end{document}