Subject: Proposal VI, First Revision, LaTeX

From: L J Clarke <[email-masked]>
Date: Tue, 23 Mar 93 18:43:04 GMT

Here is LaTeX for the revision of Proposal VI.  Please see my reply to
Jim of today for an idea of what is changed. 

I apologise that this is one hour later then I had previously announced.

PostScript follows.

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

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
% LYNDON                                                             %
% REMBER TO MERGE IN THE COMMENTS FROM THE PREVIOUS REVISION OF THIS %
% DOCUMENT. OH, AND TO GET BETTER SET UP FOR TRANSFER TO LAPTOP!     %
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\documentstyle{report}

\begin{document}
\title{MPI Context Subcommittee\\Proposal VI\\First Revision}
\author{Lyndon~J~Clarke}
\date{March 23, 1993}
\maketitle
%======================================================================%
% BEGIN "Proposal VI"
% Lyndon J. Clarke
% March 1993
%
\chapter{Proposal VI}

\newcommand{\LabelNote}[1]{\label{vi:note:#1}}
\newcommand{\ReferNote}[1]{Note~\ref{vi:note:#1}}

\newcommand{\LabelSection}[1]{\label{vi:sect:#1}}
\newcommand{\ReferSection}[1]{Section~\ref{vi:sect:#1}}

%----------------------------------------------------------------------%
% BEGIN "Introduction"
%

\section{Introduction}\LabelSection{introduction}

This chapter proposes that communication contexts and process
groupings within {\sc mpi} appear as loosely coupled concepts. One or
more communication contexts may be associated with each process
grouping, and each communication context inherits properties of the
associated process grouping.  This reflects the observations that
invocations of modules in a parallel program typically operate within
process groupings, and that there may be multiple modules operating
within each process grouping.

The proposal provides process identified communication, communications
which are limited in scope to single contexts, and communications
which have scope spanning pairs of contexts.  The proposal makes no
statements regarding message tags.  It is assumed that these will be a
bit string expressed as an integer in the host language.

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

The detailed proposal is presented in \ReferSection{proposal}, which
refers the reader to a set of discussion notes in
\ReferSection{notes}.  The note assumes forward knowledge of the
proposal text and are therefore best examined after familiarisation
with the proposal text.  Aspects of the proposal are discussed in
section
\ReferSection{discussion}, and it is also recommended that this material
be read after familiarisation with the proposal text. 

%
% END "Introduction"
%----------------------------------------------------------------------%

%----------------------------------------------------------------------%
% BEGIN "Detailed Proposal"
%

\section{Detailed Proposal}\LabelSection{proposal}

This section presents the detailed proposal, describing, in order of
appearance: processes; process groupings; communication contexts;
point-to-point communication; collective communication.

\subsection{Processes}\LabelSection{processes}

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

\subsubsection*{Process Descriptor}

Each process is described by a {\it process descriptor\/} (or {\it
handle}) which is expressed as an integer type in the host language
and has an opaque value which is process local.  See
\ReferNote{descriptor}.

The initialisation of {\sc mpi} services will assign to each process
an {\it own\/} process descriptor.  Each process retains its own
process descriptor until the termination of {\sc mpi} services.  {\sc
mpi} provides a procedure which returns the own descriptor of the
calling process.  For example, \mbox{\tt pd = mpi\_own\_process()}.

\subsubsection*{Process Creation \&  Destruction}

This proposal makes no statements regarding creation and destruction
of processes. See \ReferNote{processes:dynamic}.

\subsubsection*{Descriptor Transmission}

Since a descriptor is an integer type in the host language the value
may be transmitted in a message as an integer.  The recipient of the
descriptor value can make no defined use of the value in the {\sc mpi}
operations described in this proposal --- the descriptor is {\it
invalid}.

{\sc mpi} provides a mechanism whereby the user can transmit a valid
process descriptor in a message such that the received descriptor is
valid.  This is integrated with the capability to transmit typed
messages.  It is suggested that a notional data type should be
introduced for this purpose, e.g.  \mbox{\tt MPI\_PD\_TYPE}.  See
\ReferNote{descriptor:transmission}.

{\sc mpi} provides a process descriptor registry service.  Use of this
service is not mandated.  Programs which can conveniently be expressed
without using the service can ignore it without penalty.  See
\ReferNote{descriptor:registry}.

Note that receipt of a valid process descriptor may have a persistent
effect on the implementation of {\sc mpi} at the receiver, and in
particular may reserve state.  {\sc mpi} will provide a procedure
which frees (or invalidates) a valid descriptor, allowing the
implementation to free reserved state.  For example, \mbox{\tt
mpi\_free\_pd(pd)}.  The user is not allowed to free the process
descriptor of the calling process.  See
\ReferNote{descriptor:deallocation}. 

See \ReferNote{coherency}.

\subsubsection*{Descriptor Attributes}

This proposal makes no statements regarding process descriptor
attributes.

\subsection{Process Groupings}\LabelSection{groupings}

This proposal views a process grouping as an ordered collection of
(references to) distinct processes, the membership and ordering of
which does not change over the lifetime of the grouping.  See
\ReferNote{groupings:dynamic}. The canonical representation of a grouping
reflects the process ordering and is a one-to-one map from $Z_N$ to
descriptors of the $N$ processes composing the grouping. 

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

\subsubsection*{Group Descriptor}

Each group is identified by a {\it group descriptor\/} (or {\it
handle\/}) which is expressed as an integer type in the host language
and has an opaque value which is process local.  See
\ReferNote{descriptor}.

The initialisation of {\sc mpi} services will assign to each process
an {\it own\/} group descriptor for a process grouping of which the
process is a member.  Each process retains its own group descriptor
and membership of the own process grouping until the termination of
{\sc mpi} services.  See
\ReferNote{grouping:blobs}.  {\sc mpi} provides a procedure which accepts a
valid process descriptor and returns the own group descriptor of the
identified process.  For example, \mbox{\tt gd = mpi\_own\_group(pd)}. 
See \ReferNote{grouping:own}. 

\subsubsection*{Group Creation and Deletion}

{\sc mpi} provides facilities which allow users to dynamically create
and delete process groupings in addition to the own grouping(s).  The
procedures described here generate groups which are static in
membership.

{\sc mpi} provides a procedure which allows users to create one or
more groups which are subsets of existing groups.  For example,
\mbox{\tt gdb = mpi\_group\_partition(gda, key)} creates one or more new
groups {\tt gdb} which are distinct subsets of an existing group {\tt
gda} according to the supplied values of {\tt key}.  This procedure
is called by and synchronises all members of {\tt gda}.

{\sc mpi} provides a procedure which allows users to create a group by
permutation of an existing group.  For example, \mbox{\tt gdb =
mpi\_group\_permutation(gda, rank)} creates one new group with the
same membership as {\tt gda} with a permutation of process ranking,
and returns the created group descriptor in {\tt gdb}.  This procedure
is called by and synchronises all members of {\tt gda}.

{\sc mpi} provides a procedure which allows users to create a group by
explicit definition of its membership as a list of process
descriptors.  For example, \mbox{\tt gd =
mpi\_group\_definition(listofpd)} creates one new group {\tt gd} with
membership and ordering described by the process descriptor list {\tt
listofpd}.  This procedure is called by and synchronises all processes
identified in {\tt listofpd}.

{\sc mpi} provides a procedure which allows users to delete user
created groups.  This procedure accepts the descriptor of a group
which was created by the calling process and deletes the identified
group.  For example, \mbox{\tt mpi\_group\_deletion(gd)} deletes an
existing group {\tt gd}.  This procedure is called by and synchronises
all members of {\tt gd}.

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

\subsubsection*{Descriptor Transmission}

Since a descriptor is an integer type in the host language the value
may be transmitted in a message as an integer.  The recipient of the
descriptor can make no defined use of the value in the {\sc mpi}
operations described in this proposal --- the descriptor is {\it
invalid}.  See \ReferNote{descriptor}.

{\sc mpi} provides a mechanism whereby the user can transmit a valid
group descriptor in a message such that the received descriptor is
valid.  This is integrated with the capability to transmit typed
messages.  It is suggested that a notional data type should be
introduced for this purpose, e.g.  \mbox{\tt MPI\_GD\_TYPE}.  See
\ReferNote{descriptor:transmission}.

{\sc mpi} provides a group descriptor registry service.  Use of this
service is not mandated.  Programs which can conveniently be expressed
without using the service can ignore it without penalty.  See
\ReferNote{descriptor:registry}.

Note that receipt of a valid group descriptor may have a persistent
effect on the implementation of {\sc mpi} at the receiver, and in
particular may reserve state.  {\sc mpi} will provide a procedure
which frees (or invalidates) a valid descriptor, allowing the
implementation to free reserved state.  For example, \mbox{\tt
mpi\_free\_gd(gd)}.  The user is not allowed to free the own group
descriptor of the calling process or the group descriptor of any group
created by the calling process.  See
\ReferNote{descriptor:deallocation}.

See \ReferNote{coherency}.

\subsubsection*{Descriptor Attributes}

{\sc mpi} provides a procedure which accepts a valid group descriptor
and returns the rank of the calling process within the identified
group.  For example, \mbox{\tt rank = mpi\_group\_rank(gd)}.

{\sc mpi} provides a procedure which accepts a valid group descriptor
and returns the number of members, or {\it size}, of the identified
group.  For example, \mbox{\tt size = mpi\_group\_size(gd)}.

{\sc mpi} provides a procedure which accepts a valid group descriptor
and process order number, or {\it rank}, and returns the valid
descriptor of the process to which the supplied rank maps within the
identified group.  For example, \mbox{\tt pd = mpi\_group\_pd(gd,
rank)}.

See \ReferNote{inverse:map}.

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

\subsection{Communication Contexts}\LabelSection{contexts}

This proposal views a communication context as a uniquely identified
reference to exactly one process grouping, which is a field in a
message envelope and may therefore be used to distinguish messages.
The context inherits the referenced process grouping as a ``frame''.
Each process grouping may be used as a frame for multiple contexts.

\subsubsection*{Context Descriptor}

Each context is identified by a {\it context descriptor\/} (or {\it
handle}) which is expressed as an integer type in the host language
and has an opaque value which is process local.  See
\ReferNote{descriptor}.

The creation of {\sc mpi} process groupings allocates an {\it own\/}
context which inherits the created grouping as a frame and can be
thought of as a property of the created grouping.  The grouping
retains the descriptor of its own context until {\sc mpi} process
grouping deletion.  {\sc mpi} provides a procedure which accepts a
valid group descriptor and returns the context descriptor of the own
context of the identified group.  For example,
\mbox{\tt cd = mpi\_own\_context(gd)}. See \ReferNote{context:own}.

\subsubsection*{Context Creation and Deletion}

{\sc mpi} provides facilities which allows user to dynamically create
and delete contexts in addition to the own contexts associated with
process groupings. See \ReferNote{grouping:deletion}.

{\sc mpi} provides a procedure which allows users to create contexts.
This procedure accepts a valid descriptor of a group of which the
calling process is a member, and returns a context descriptor which
references the identified group.  For example, \mbox{\tt cd =
mpi\_context\_creation(gd)}.  This procedure is called by and
synchronises all members of {\tt gd}.

{\sc mpi} provides a procedure which allows users to delete user
created contexts.  This procedure accepts a valid context descriptor
which was created by the calling process and deletes the identified
context.  For example, \mbox{\tt mpi\_context\_deletion(cd)}.  This
procedure is called by and synchronises all members of the frame of
{\tt cd}.

See \ReferNote{context:creation:deletion}

\subsubsection*{Descriptor Transmission}

Since a descriptor is an integer type in the host language the value
may be transmitted in a message as an integer.  The recipient of the
descriptor can make no defined use of the value in the {\sc mpi}
operations described in this proposal --- the descriptor is {\it
invalid}.  See \ReferNote{descriptor}.

MPI provides a mechanism whereby the user can transmit a valid context
descriptor in a message such that the received descriptor is valid.
This is integrated with the capability to transmit typed messages.  It
is suggested that a notional data type should be introduced for this
purpose, e.g.  \mbox{\tt MPI\_CD\_TYPE}.  See
\ReferNote{descriptor:transmission}.

{\sc mpi} provides a context descriptor registry service.  Use of this
service is not mandated.  Programs which can conveniently be expressed
without using the service can ignore it without penalty.  See
\ReferNote{descriptor:registry}. 

Note that receipt of a valid context descriptor may have a persistent
effect on the implementation of {\sc mpi} at the receiver, and in
particular may reserve state.  {\sc mpi} will provide a procedure
which frees (or invalidates) invalidates a valid descriptor, allowing
the implementation to free reserved state.  For example, \mbox{\tt
mpi\_free\_cd(cd)}.  The user is not allowed to free the own context
descriptor of any group or the context descriptor of any context
created by the calling process.

See \ReferNote{coherency}.

\subsubsection*{Descriptor Attributes}

{\sc mpi} provides a procedure which allows users to determine the
process grouping which is the frame of a context.  For example,
\mbox{\tt gd = mpi\_context\_group(cd)}.

\subsection{Point-to-Point Communication}\LabelSection{point2point}

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

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

\subsubsection*{Null Context Form}

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

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

{\tt Receive} can wildcard on {\tt pd} by supplying the value of a
named constant process descriptor, e.g.  {\tt MPI\_PD\_WILD}.  See
\ReferNote{descriptor:wildcard}.  This proposal makes no statement about
the provision for wildcard on {\tt tag}. 

\subsubsection*{Closed Context Form}

The {\it closed context\/} form permits communication between members
of the same context.  Message selection and addressing are expressed
by \mbox{\tt (cd, rank, tag)} where: {\tt cd} is a context descriptor;
{\tt rank} is a process rank in the frame of {\tt cd}; {\tt tag} is a
message tag.

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

{\tt Receive} cannot wildcard on {\tt cd}.  {\tt Receive} can wildcard
on {\tt rank} by supplying the value of a named constant integer, e.g.
{\tt MPI\_RANK\_WILD}.  See \ReferNote{rank:wildcard}.  This proposal
makes no statement about the provision for wildcard on {\tt tag}.

\subsubsection*{Open Context Form}

The {\it open context\/} form permits communication between members of
any two contexts.  Message selection and addressing are expressed by
\mbox{\tt (lcd, rcd, rank, tag)} where: {\tt lcd} is a ``local''
context descriptor; {\tt rcd} is a ``remote'' context descriptor; {\tt
rank} is a process rank in the frame of {\tt rcd}; {\tt tag} is a
message tag.

{\tt Send} supplies the context descriptor for the sender in {\tt
lcd}, the context descriptor for the receiver in {\tt rcd}, and the
{\tt rank} of the receiver in the frame of {\tt rcd}.  {\tt Receive}
supplies the context descriptor for the receiver in {\tt lcd}, the
context descriptor for the sender in {\tt rcd}, and the {\tt rank} of
the sender receiver in the frame of {\tt rcd}.  The \mbox{\tt (rcd,
rank)} pair in {\tt Send} ({\tt Receive}) is sufficient to determine
the process descriptor of the receiver (sender).

{\tt Receive} cannot wildcard on {\tt lcd} which is the open context
form analog of there being no wildcard on {\tt cd} in the closed
context form.  Receive can wildcard on {\tt rcd} by supplying the
value of a named constant context descriptor, e.g.  {\tt
MPI\_CD\_WILD} (See \ReferNote{descriptor:wildcard}), in which case
{\tt Receive} {\it must\/} also wildcard on {\tt rank} as there is
insufficient information to determine the process descriptor of the
sender.  {\tt Receive} can wildcard on {\tt rank} by supplying the
value of a named constant integer, e.g.  {\tt MPI\_RANK\_WILD}.  See
\ReferNote{rank:wildcard}.  This proposal makes no statement about the
provision for wildcard on {\tt tag}. 

\subsubsection*{Uniform Integration}

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

There are various approaches to unification of the syntactic
frameworks which may simplify integration.  Three options are now
described, each based on retention and extension of the framework of
one form.  These options represent different compromises between the
three forms.

\paragraph*{Option i: Open Context Framework}

The framework of the open context form is adopted and extended.

Introduce the {\it null\/} descriptor, the value of which is defined
by a named constant, e.g.  {\tt MPI\_NULL}.  See
\ReferNote{descriptor:null}.  The null context form is expressed as
\mbox{\tt (MPI\_NULL, MPI\_NULL, pd, tag)}, which is a little clumsy. 
The closed context form is expressed as \mbox{\tt (MPI\_NULL, cd,
rank, tag)}, which is marginally inconvenient.  The open context form
is expressed as \mbox{\tt (lcd, rcd, rank, tag}), which is of course
natural.

\paragraph*{Option ii: Closed Context Framework}

The framework of the closed context form is adopted and extended.

Introduce the {\it null\/} descriptor, the value of which is defined
by a named constant, e.g.  {\tt MPI\_NULL}.  See
\ReferNote{descriptor:null}.  The null context form is expressed as
\mbox{\tt (MPI\_NULL, pd, tag)}, which is marginally inconvenient.  The
closed context form is expressed as \mbox{\tt (cd, rank, tag)}, which is
of course natural.  Expression of the open context form requires a
little more work. 

We can use the {\tt cd} field as ``shorthand notation'' for the
\mbox{\tt (lcd, rcd)} pair at the expense of introducing some trickery. 
We define a ``context duplet descriptor'' which is formally composed
of two references to contexts, and provide a procedure which
constructs such a descriptor given two context descriptors.  Both {\tt
Send} and {\tt Receive} will accept a duplet descriptor in {\tt cd},
are able to distinguish the duplet descriptor from a singlet
descriptor, and treat the duplet as shorthand notation.  We should
also define a mechanism by which a receiver which has completed a {\tt
Receive} with wildcard on {\tt rcd} is able to determine the valid
singlet descriptor of the sender, which just adds one further enquiry
procedure to the point-to-point chapter(?). This option is a little
inconvenient but does have some useful properties for collective
communications.  It is conjectured that this option is the best choice
for {\sc mpi}.

\paragraph*{Option iii: Null Context Framework}

The framework of the null context form is adopted and extended. 

The null context form is expressed as \mbox{\tt (pd, tag)}, which is
of course natural.  Expression of the open and closed context forms
requires a little more work.

We can use the {\tt pd} field as ``shorthand notation'' for {\tt (cd,
rank)} and {\tt (lcd, rcd, rank)} by continuation of the trickery used
in the previous option.  This is rather clumsy.

\subsection{Collective Communication}\LabelSection{collective}

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

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

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

{\sc mpi} does not plan to describe asymmetric collective
communication operations.  Such operations are expressive when writing
programs beyond the SPMD model, which are composed of communicative
functionally distinct process groupings.  This proposal recommends that
such operations should be considered in some reincarnation of {\sc
mpi}.

%
% END "Proposal"
%----------------------------------------------------------------------%

%----------------------------------------------------------------------%
% BEGIN "Discussion & Notes"
%

\section{Discussion \& Notes}

This section comprises a discussion of certain aspects of this
proposal followed by the notes referenced in the detailed proposal.

\subsection{Discussion}\LabelSection{discussion}

We can dissect the proposal into two parts: an SPMD model core; an
MIMD model annex.  In this discussion the dissection is exposed and
the conceptual foundation of each part is described.  The discussion
also presents brief arguments for and against the MIMD model annex.

\subsubsection*{SPMD model core}

The SPMD model core provides noncommunicative process groupings and
communication contexts for writers of SPMD parallel libraries.  It is
intended to provide expressive power beyond the ``SPIMD'' model (in
which process execute in an SIMD fashion).

The material describing processes in \ReferSection{processes} is
simplified: processes have identical instruction blocks and different
data blocks; process descriptor transmission and registry become
redundant; dynamic process models are not considered.

The material describing process groupings in \ReferSection{groupings}
is simplified: group descriptor transmission and registry become
redundant; the own process grouping explicitly becomes a single group
containing all processes.

The material describing communication contexts in
\ReferSection{contexts} is simplified: context descriptor transmission
and registry become unnecessary. 

The material describing point-to-point communication in
\ReferSection{point2point} is simplified: the open context form becomes
redundant; uniform integration ``Option i'' is deleted, and ``Option
ii'' loses duplet descriptors, becoming simple enough that ``Option
iii'' need not be further considered.

The material describing collective communication in
\ReferSection{collective} is simplified: there is no possibility of
collective communication operations spanning more than one context. 

\subsubsection*{MIMD model annex}

The MIMD model annex extends and modifies the SPMD model core to
provide expressive power for MIMD programs which combine (coarse
grain) function and data driven parallelism.  The MIMD model annex is
not intended to provide expressive power to fine grained function
driven parallel programs --- it is conjectured that message passing
approaches such as {\sc mpi} are not suited to fine grained parallel
programming.  The annex is intended to provide expressive power for the
``MSPMD'' model, which is now described.

One of the simplest MIMD models is the ``host-node'' model, familiar
in {\sc express} and {\sc parmacs}, containing two functional groups:
one node group (SPMD like) ; one host group (a singleton).

The ``parallel client-server'' model, in which each of the $n$ clients
is composed of parallel processes, and in which the server may also be
composed of parallel processes, contains $1+n$ functional groups: $n$
client groups (SPMD like); one server group (singleton, SPMD like).
The ``host-node'' model is a case of this model in which the host can
be viewed as a singleton client and the nodes can be viewed as an SPMD
like server (or the host as a singleton server and the nodes as an
SPMD like client).

The ``parallel module graph'' model, in which each module within the
graph may be composed of parallel processes (singleton, SPMD like),
contains any number of functional groups with arbitrarily complex
relations.  The ``parallel client-server model'' is a case of this
model in which the module graph only contains arcs joining the server
to each client.

The MIMD model annex is intended to provide expressive power for the
``parallel module graph'' model, which I refer to as the MPSMD model.
This model requires support at some level as commercial and modular
applications are increasingly moving in to parallel computing.  The
debate is whether or not message passing approaches such as {\sc mpi}
(which I simply refer to as MPI) should provide for this model.

The negative argument is that such SPMD like modules should be
controlled and communicate with one another as ``parallel processes''
at the distributed operating system level.  The argument has some
appeal as the world of distributed operating systems must deal with
difficult issues such as process control and coherency.  Avoidance of
duplication in MPI allows MPI to focus on provision of a smaller set
of facilities with greater emphasis on maximum performance for data
driven SPMD like parallel programs.

The positive argument is that communications between such SPMD like
modules require high performance and MPI can provide such performance
with tuned semantics which expect the user to deal with coherency
issues.  There is also the argument that MPI is able to deal with this
in a shorter time than development (and standardisation) procedures
for distributed operating systems.  The latter argument is somewhat
comparable with the argument for message passing versus parallel
compilation.

\subsection{Notes}\LabelSection{notes}

\begin{enumerate}

\item\LabelNote{descriptor}
{\bf Descriptors:} Descriptors are assumed to be a plentiful but
bounded resource.  They are opaque references to objects of undefined
size and structure.  They are not global unique identifiers however
they must reference such identifiers, and they protect the user from
the form of such identifiers allowing them to be implementation
dependent.  The proposal expresses descriptors as integer types in the
host language (in practice we might expect descriptors to be indices
into tables of structures, or tables of pointers to structures, or
indeed pointers to structures themselves).  This expression
facilitates uniform binding to ANSI~C and Fortran~77.

The context descriptor must at least reference: the global unique
context identifier; the group descriptor of the frame.  The group
descriptor must at least reference: the global unique group
identifier; the own context descriptor; the rank space to process
descriptor map of the group (including the size of the group); the
process rank.  The process descriptor must at least reference; the
global unique process identifier; the group descriptor of the own
group.

The proposal text distinguishes process, group and context identifiers
more strongly than is strictly necessary.  There is potential advantage
in the concept of a unified descriptor which can be used to reference
either kind of actual descriptor.  For example descriptor unification
goes some way toward cleaning up the duplet, descriptors described in
``Option ii'' of section \ReferSection{point2point}.  Definition in
this fashion requires the referenced object to contain a class
identifier (which in this proposal could be as little as 3 bits wide)
This suggestion is explored in some of the notes below.

Rik Littlefield has suggested descriptors could be used to ``cache''
per object user information, as appears in {\sc zipcode}.  This
descriptor capability could be seriously useful for example in context
or group specific implementations of collective communications.  The
suggestion both requires and deserves more work.

There were additional motivations for expressing process descriptors
as integers in the proposal.  Firstly, the author anticipated ``Option
ii'' of \ReferSection{point2point}.  Secondly, it is observed that
definition of process descriptors can be weakened such that they may
be implemented as global unique process identifiers, expressed as
integers, should this infer advantage.  {[\it I wish I had realised
the second point before the first!]}

The consequence of allowing process descriptors to be implemented as
process identifiers is explored in some of the notes below.  Please
also note that this would exclude process descriptors from the
``caching'' capability mentioned above.  These ideas suggest an
alternate proposal, containing global unique process identifiers
expressed as integers, and context and group descriptors as opaque
references of yet unspecified language binding (i.e., perhaps not an
integer).  This suggestion is also explored in some of the notes
below.

\item\LabelNote{processes:dynamic} 
{\bf Dynamic Processes:} The proposal does not prevent a process model
which allows dynamic creation and deletion of processes however it
does not favour an asynchronous process model in which singleton
processes are created and deleted in an arbitrary fashion.  The
proposal does favour a model in which blobs of processes are created
(and deleted) in a concerted fashion, and in which each blob so
created is assigned a different own process grouping.  This model does
not take into account the potential desire to expand or contract an
existing blob of processes in order to take into account (presumably
slowly) time varying workloads.  It is conjectured that concerted blob
expand and contract operations are more suitable for this purpose than
asynchronous singleton spawn and kill operations.

\item\LabelNote{descriptor:transmission}
{\bf Descriptor transmission:} In the spirit of descriptor unification
(See \ReferNote{descriptor}) the three {\tt MPI\_?D\_TYPE} names can
be collapsed into something like {\tt MPI\_DESC\_TYPE}.

If process descriptors are replaced by global unique process
identifiers (See \ReferNote{descriptor}) then no special measures are
required for transmission thereof.

If group and context descriptors are expressed as opaque objects of
yet unspecified type then, in ANSI~C at least, it will be possible to
prevent nonsemantic transmission thereof.

\item\LabelNote{descriptor:registry}
{\bf Descriptor registry:} The registry service is just a simpler way
for concurrent objects to identify and establish communications with
one another.  The operations of interest, expressed in the spirit of
descriptor unification (See \ReferNote{descriptor}), are: registration
of descriptor by name, e.g.  \mbox{\tt mpi\_register(name,desc)};
deregistration, e.g \mbox{\tt mpi\_deregister(desc)}; and lookup by
name, e.g. \mbox{\tt mpi\_lookup(name, \&desc, wait)} where {\tt wait}
controls whether the lookup waits for the name to be registered.

If process descriptors are replaced by global unique process
identifiers (See \ReferNote{descriptor}) then perhaps process
identifier registry is not so important.

The MIMD model does not actually required process descriptor or group
descriptor registry to be visible to the user since context descriptor
registry and context descriptor attribute determination gives access
to all groups and thus group descriptor attribute determination gives
access to all processes.  The proposal was written to handle
descriptors consistently.

\item\LabelNote{descriptor:deallocation}
{\bf Descriptor deallocation:} In the spirit of descriptor unification
(See \ReferNote{descriptor}) the three \mbox{\tt mpi\_?d\_free(?d)}
can be collapsed into something like \mbox{\tt mpi\_desc\_free(desc)}.

The receipt of a descriptor in descriptor transmission and registry is
an allocator, hence provision of the deallocator. Perhaps there should
be an explicit allocator which the user must call in order to receive
a descriptor, and can deallocate when no longer required.

If process descriptors are replaced by global unique process
identifiers (See \ReferNote{descriptor}) then process identifier
deallocation is moot.

\item\LabelNote{coherency}
{\bf Coherency:} The proposal admits incoherency as descriptors may be
received in transmission or registry.  The SPMD core contains no
incoherency.  The inclusion of dynamic process creation and deletion
admits incoherency since processes can retain descriptors of processes
which have been deleted.  The inclusion of grouping descriptor
transmission and registry admits incoherency since processes can
retain descriptors of groupings which have been deleted.  The
inclusion of dynamic groupings admits incoherency since processes can
retain descriptors of groupings of which the rank to process map has
changed.  The inclusion of context descriptor transmission and
registry admits incoherency since processes can retain descriptors of
contexts which have been deleted.  The proposal expects the user to
ensure coherent usage.  It is conjectured that this is acceptable
provided that the user is not also expected to implement process fault
tolerance.

\item\LabelNote{groupings:dynamic}
{\bf Dynamic groupings:} Process groupings are dynamic in the sense
that they can be created at any time, and static in the sense that the
membership is constant over the lifetime of the process grouping.  The
proposal specifies static groupings however the loose separation of
communication contexts from process groupings simplifies extension to
dynamic groupings as contexts stretch or shrink according to the
changes in their frames.  It is conjectured that concerted grouping
expand and contract operations are more suitable than asynchronous
singleton join and leave operations.

\item\LabelNote{grouping:blobs}
{\bf Process blobs:} {\sc mpi} has discussed the concept of the
``all'' group which contains all processes.  The ``own'' group concept
is a generalisation of the ``all'' group concept which is expressive
for programs including and beyond the SPMD model.  Processes are
created in ``blobs'', where each member of a blob is a member of the
same own process grouping, and different blobs have different own
process groupings.  An SPMD program is a single blob.  A host-node
program composes two blobs, the node blob and the host blob (a
singleton).  There is a sense in which a blob is SPMD like.

\item\LabelNote{grouping:own}
{\bf \mbox{\tt mpi\_own\_group(pd)}:} This procedure looks like a case
of process descriptor attribute determination. If process descriptors
are allowed to be implemented as global unique process identifiers, or
are replaced, this procedure should accept no arguments and return the
own group descriptor of the calling process.

\item\LabelNote{inverse:map}
{\bf Inverse map:} The proposal did not include a function to convert
\mbox{\tt (gd, pd)} pair into a rank.  It is suggested that this
inverse map is allowed to be ``slow'', i.e.  could be a linear search
over members of the group, but probably should be included for
completeness.  It can be used as a membership predicate.

\item\LabelNote{context:own}
{\bf \mbox{\tt mpi\_own\_context(gd)}:} This procedure looks like a
case of group descriptor attribute determination.

\item\LabelNote{grouping:deletion}
{\bf Grouping Deletion:} The process grouping deletion operation
should probably be defined to fail when there are user created
contexts with that frame which have not themselves been deleted.  This
just requires a reference count in the group descriptor static
attribute store.

\item\LabelNote{context:creation:deletion}
{\bf Context Creation \& Deletion:} Marc Snir has described a method
by which global unique group identifiers can be generated without use
of shared global data.  The proposal states that context creation and
deletion operations synchronise the processes within the frame of the
context, anticipating use of this method for generation of context
identifiers. However, the synchronisation requires that context
creation and deletion calls within a frame are performed in the
identical sequence by all members of the frame.  The global unique
group identifier and context creator reference count are then
sufficient to generate a global unique context identifier without
communication or synchronisation.  Should context creation and
deletion therefore not synchronise the frame?

There may be advantage in defining context creation and deletion such
that a number of contexts are created or deleted simultaneously,
depending on how heavy we expect context management to be in
implementations of {\sc mpi}.

\item\LabelNote{descriptor:wildcard}
{\bf Descriptor wildcard:} In the spirit of descriptor unification 
(See \ReferNote{descriptor}) the three named constants {\tt MPI\_?D\_WILD} 
can be collapsed into something like {\tt MPI\_DESC\_WILD}.

If process descriptors are replaced with global unique process
identifiers then perhaps the wildcard process identifier value can be
the same as the wildcard tag value, and the same named constant.

\item\LabelNote{context:form}
{\bf Context forms:} The null form is like PVM~3.  It is general
purpose, but not particularly expressive.  It does not provide
facilities for writers of parallel libraries. It has the potential to
provide maximum performance.

The closed form is like {\sc zipcode}.  It is expressive in
SPMD programs where noncommunicative distinct data driven parallel
computations can be performed concurrently.  It provides facilities
for writers of SPMD like parallel libraries.

The open form is like {\sc chimp}.  It is expressive in MIMD programs
where communicative data driven parallel computations can be performed
concurrently.  It provides facilities for MIMD like parallel
libraries.

\item\LabelNote{rank:wildcard}
{\bf Rank wildcard:} Since rank is an integer like message tag,
perhaps they should have the same wildcard value, and the same named
constant.

\item\LabelNote{descriptor:null}
{\bf {\tt MPI\_NULL}:} I am following the spirit of context
unification (See \ReferNote{descriptor}) in the proposal text here.
There may be advantage in defining the value of the null descriptor to
be the ANSI~C constant {\tt NULL}, or even defining the value to be
exactly zero (every rule having a useful exception).

\end{enumerate}

%
% END "Discussion & Notes"
%----------------------------------------------------------------------%

%----------------------------------------------------------------------%
% BEGIN "Conclusion"
%

\section{Conclusion}\LabelSection{conclusion}

This chapter has presented and discussed a proposal for communication
contexts within {\sc mpi}.  In the proposal process groupings appeared
as frames (or templates) for the construction of communication
contexts, and communication contexts retained certain properties of
the frames used in their construction.

%
% END "Conclusion"
%----------------------------------------------------------------------%

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

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

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