Subject: Proposal I - LaTeX

From: L J Clarke <[email-masked]>
Date: Sun, 21 Mar 93 19:46:42 GMT

This is LaTeX of Proposal I, credits entirely to Marc Snir, 15 minutes
earlier than previously advertised.  PostScript to follow. 

My sincere apology to everyone who has prepared comments on Proposal
I++.  Some of these comments will carry through to Proposal II, which
will be sent out shortly. 

----------------------------------------------------------------------
\documentstyle{report}
\begin{document}
\title{Proposal I\\MPI Context Subcommittee}
\author{Marc~Snir}
\date{March 1993}
\maketitle
%======================================================================%
% BEGIN "Proposal I"
% Written by Marc Snir
% Edited by Lyndon J. Clarke
% March 1993
%

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

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

\chapter{Proposal I}

{\it Editorial Note: This chapter is the proposal of Marc~Snir which
also appears in the working documents of the point-to-point
subcommittee (March 15) and collective communication subcommittee
(March 16). This is a minor edit of the \LaTeX\ source of the
point-to-point document provided by Marc. The edit was performed by
Lyndon~Clarke.}

\section{Contexts}

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

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

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

Follows examples of possible uses for contexts.

\subsection{Loosely synchronous library call interface}

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

\subsection{Functional decomposition and modular code development}

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

\subsection{Collective communication}

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

\subsection{Lightweight gang scheduling}

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

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

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

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

\section{Context Operations}

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

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

The following operations are available for creating new contexts.

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

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

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

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

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

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

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

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

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

Particular uses of this function are:

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

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

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

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

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

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

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

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

\subsection{Usage note}

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

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

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

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

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

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

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

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

         /--------------------------------------------------------\
    e||) | Lyndon J Clarke    Edinburgh Parallel Computing Centre | e||) 
    c||c | Tel: 031 650 5021  Email: [email-masked]  | c||c 
         \--------------------------------------------------------/

---

From: Tony Skjellum <[email-masked]>
Date: Sun, 21 Mar 93 13:44:53 CST

Lyndon, what about your extensive proposal (that I just scribbled
about endlessly).  Are you shooting that?  Anyway, tell me specifically,
and call whatever new thing Proposal VI, not proposal II' or II.
- Tony