Subject: MPI-CONTEXT: PLEASE README - Proposal VI - LaTeX

From: L J Clarke <[email-masked]>
Date: Mon, 22 Mar 93 12:19:43 GMT

----------------------------------------------------------------------
\documentstyle{report}

\begin{document}
\title{Proposal VI\\MPI  Context Subcommittee}
\author{Lyndon~J~Clarke}
\date{March 1993}
\maketitle
%======================================================================%
% BEGIN "Proposal VI"
% Written by Lyndon J. Clarke
% March 1993
%

\newcommand{\LabelNote}[1]{\label{vi:note:#1}}
\newcommand{\SeeReferNote}[1]{{\bf See~Note~\ref{vi:note:#1}.}}

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

\chapter{Proposal VI}

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

\section{Introduction}

This chapter proposes that communication contexts and process groupings
within MPI appear as related concepts.  In particular process groupings
appear as ``frames'' which are used in the creation of communication
contexts.  Communications contexts retain a reference to, and inherit
properties of, their process grouping frames.  This reflects the
observation that an invocation of a module in a parallel program
typically operates within one or more groups of processes, and as such
any communication contexts associated with invocations of modules also
bind certain semantics of process groupings. 

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 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 for only
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 notes assumes knowledge of the proposal text and are therefore best
examined after familiarisation with that 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
text of the proposal. 

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

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

\section{Detailed Proposal}
\LabelSection{proposal}

This section presents the detailed proposal, discussing 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 MPI does not distinguish such threads.

\subsubsection*{Process Descriptor}

Each process is described by a {\it process descriptor\/} which is
expressed as an integer type in the host language and has an opaque
value which is process local.  
\SeeReferNote{integer:descriptors}
\SeeReferNote{process:identifiers}
\SeeReferNote{descriptor:cache}

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

\subsubsection*{Process Creation and Destruction}

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

\subsubsection*{Descriptor Transmission}

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

%[Tony]
% Then why allow it to be passed?
%
%%[Lyndon]
%% Since it is an integer one cannot prevent the user from passing it.
%% The discussion notes should help answer why is is an integer. More
%% here. 
%% We'd like (gd,rank) and (NULL,pd) to be suppliable to point-to-point.
%% Because rank will be an integer, then pd must also be an integer,
%% so I write that all descriptors are integers for consistency beteen
%% the different descriptors.
%%

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.  {\tt MPI\_PD\_TYPE}. 

MPI provides a process descriptor registry service.  The operations
which this service upports are: register descriptor by name; deregister
descriptor; lookup descriptor identifier by name and validate, blocking
the caller until the name has been registered. 
\SeeReferNote{registry:check}
Use of this service is not mandated. 
Programs which can conveniently be expressed without using the service
can ignore it without penalty. 

%[Tony]
% I don't get all of this.  Why?
%
%%[Lyndon]
%% I don't understand what you don't get. A registry service is just
%% an easier (nonscalable, okay) way for concurrent entities to hook up
%% with one another, rather than having some common ancestor send descriptors
%% around in messages.
%% In fact I don't really need a group or process registry service, as mentioned
%% in the discussion section (yes, I know, not well presented), but
%% I do need a context registry service, and I'm being consistent
%% between different kinds of descriptors again. 
%% Suggestive syntax for a registry service is pretty boring, so
%% I skipped it.
%%

Note that receipt of a process descriptor in the fashions described
above may have a persistent effect on the implementation of MPI at the
receiver, and in particular may reserve state.  MPI will provide a
procedure which invalidates a valid descriptor, allowing the
implementation to free reserved state.
For example,  {\tt mpi\_invalidate\_pd(pd)}. The user is not allowed
to invalidate the process descriptor of the calling process.
\SeeReferNote{process:coherency}

%[Tony]
% I do not understand the usefulness or formal need for all this
% validation and invalidation of process identifiers.  Why, where
% did it come from, what does it get us?  How can this be related
% to anything I have seen before?
%
%%[Lyndon]
%% Acquisition of a descriptor requires an allocator, and consumes
%% resource. In such cases it is good practice to provide a 
%% deallocator which frees resource. 
%%

% [Tony] 
% I understand the idea here, but not all the details.  Can this
% be justified/exemplified/simplified?
%
%%[Lyndon]
%% Unless I am missing the additional point in this comment, I can't
%% see the problem. Probably poor presentation of Proposal I++ :-)
%%

\subsubsection*{Descriptor Attributes}

This proposal makes no statements regarding processor 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. 
\SeeReferNote{dynamic:groups} The canonical representation of a grouping
reflects the process ordering and is a one-to-one map from $Z_N$ to the
descriptor of the $N$ processes composing the grouping. 

The structure of a process grouping is defined by a process grouping
topology and this proposal makes no further statements regarding such
structures. 

%[Tony]
% It is not obvious to me that we want to enforce topology at this
% juncture.  However, we could register topology information in
% the extensible structure strategy of Proposal V.
%
%%[Lyndon]
%% I am deliberately making weak statements about topology while
%% acknolwedging the the process topology subcommittee.
%%

\subsubsection*{Group Descriptor}

Each group is identified by a {\it group descriptor\/} which is
expressed as an integer type in the host language and has an opaque
value which is process local.  
\SeeReferNote{integer:descriptors}
\SeeReferNote{group:identifiers}
\SeeReferNote{descriptor:cache}

The initialisation of 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 process grouping until the termination of MPI services.
\SeeReferNote{group:blobs}
MPI provides a procedure which returns the
descriptor of the home group of the calling process.  
For example, {\tt gd = mpi\_home\_gd()}.  
\SeeReferNote{own:group}

\subsubsection*{Group Creation and Deletion}

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

MPI provides a procedure which allows users to dynamically create one
group by explicit definition of its membership as a list of process
descriptors.  For example, {\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}. 

%[Tony]
% loosely synchronous
%
%%[Lyndon]
%% Do we mean the same thing? the constructors require each member
%% if the object under construction to participate in the construction,
%% and return a descriptor for the constructed operation. Therefore
%% no member can terminate construction before all other members have
%% commenced, at least.
%%

%[Rik] 
% Why such strong synchronization?!
% If this has the same synchronization properties as creation,
% then it won't return until all members have made the call.
% But that means you actually have to sync everybody, which
% implies 2 log(P) messages.  Isn't it enough to just require
% a loosely synchronous call, and use a counting strategy>
%

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

MPI provides additional procedure which allow users to construct process
groupings which have a process grouping topology. 

\subsubsection*{Descriptor Transmission}

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

%[Tony]
% Then why allow it to be passed?
%
%%[Lyndon]
%% Since it is an integer one cannot prevent the user from passing it.
%% The discussion notes should help answer why is is an integer. More
%% here. 
%% We'd like (gd,rank) and (NULL,pd) to be suppliable to point-to-point.
%% Because rank will be an integer, then pd must also be an integer,
%% so I write that all descriptors are integers for consistency beteen
%% the different descriptors.
%%

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.  {\tt MPI\_GD\_TYPE}. 

MPI provides a group descriptor registry service.  The operations
which this service upports are: register descriptor by name; deregister
descriptor; lookup descriptor identifier by name and validate, blocking
the caller until the name has been registered.  
\SeeReferNote{registry:check} 
Use of this service is
not mandated.  Programs which can conveniently be expressed without
using the service can ignore it without penalty. 

%[Tony]
% I don't get all of this.  Why?
%
%%[Lyndon]
%% I don't understand what you don't get. A registry service is just
%% an easier (nonscalable, okay) way for concurrent entities to hook up
%% with one another, rather than having some common ancestor send descriptors
%% around in messages.
%% In fact I don't really need a group or process registry service, as mentioned
%% in the discussion section (yes, I know, not well presented), but
%% I do need a context registry service, and I'm being consistent
%% between different kinds of descriptors again. 
%% Suggestive syntax for a registry service is pretty boring, so
%% I skipped it.
%%

Note that receipt of a group descriptor in the fashions described
above may have a persistent effect on the implementation of MPI at the
receiver, and in particular may reserve state.  MPI will provide a
procedure which invalidates a valid descriptor, allowing the
implementation to free reserved state.
For example, {\tt mpi\_invalidate\_gd(gd)}.  The user is not allowed to
invalidate the own group descriptor of the process or the group
descriptor of any group created by the calling process. 
\SeeReferNote{group:coherency}

%[Tony]
% I do not understand the usefulness or formal need for all this
% validation and invalidation of process identifiers.  Why, where
% did it come from, what does it get us?  How can this be related
% to anything I have seen before?
%
%%[Lyndon]
%% Acquisition of a descriptor requires an allocator, and consumes
%% resource. In such cases it is good practice to provide a 
%% deallocator which frees resource. 
%%

% [Tony] 
% I understand the idea here, but not all the details.  Can this
% be justified/exemplified/simplified?
%
%%[Lyndon]
%% Unless I am missing the additional point in this comment, I can't
%% see the problem. Probably poor presentation of Proposal I++ :-)
%%

\subsubsection*{Descriptor Attributes}

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

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, {\tt size = mpi\_group\_size(gd)}. 

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, {\tt pd = mpi\_group\_pd(gd, rank)}. 

\SeeReferNote{pd:to:rank}

MPI provides additional procedures which allow users to determine the
process grouping topology attributes. 

%[Tony] It is not obvious to me that we want to enforce topology at this
% juncture.  However, we could register topology information in
% the extensible structure strategy of Proposal V.
%
%%[Lyndon]
%% I am deliberately making weak statements about topology while
%% acknolwedging the the process topology subcommittee.
%%

\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 is used as a frame for multiple contexts. 

\subsubsection*{Context Descriptor}

Each context is identified by a {\it context descriptor\/} which is
expressed as an integer type in the host language and has an opaque
value which is process local.  
\SeeReferNote{integer:descriptors}
\SeeReferNote{context:identifiers}
\SeeReferNote{descriptor:cache}

The creation of 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 its own
context until MPI process grouping deletion.  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, {\tt cd = mpi\_own\_cd(gd)}.
\SeeReferNote{own:context}

\subsubsection*{Context Creation and Deletion}

MPI provides a procedure which allows users to dynamically 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, {\tt cd = mpi\_context\_create(gd)}.
This procedure is called by and synchronises all members of {\tt gd}.
\SeeReferNote{dynamic:contexts}

%[Tony]
% loosely synchronous
%
%%[Lyndon]
%% Do we mean the same thing? the constructors require each member
%% if the object under construction to participate in the construction,
%% and return a descriptor for the constructed operation. Therefore
%% no member can terminate construction before all other members have
%% commenced, at least
%%

MPI provides a procedure which allows users to destroy created contexts.
This procedure accepts a valid context descriptor which was created
by the calling process and deletes that context identifier.
For example, {\tt mpi\_context\_delete(cd)}.
This procedure is called by and synchronises all members of the 
frame of {\tt cd}.

\subsubsection*{Descriptor Transmission}

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

%[Tony]
% Then why allow it to be passed?
%
%%[Lyndon]
%% Since it is an integer one cannot prevent the user from passing it.
%% The discussion notes should help answer why is is an integer. More
%% here. 
%% We'd like (gd,rank) and (NULL,pd) to be suppliable to point-to-point.
%% Because rank will be an integer, then pd must also be an integer,
%% so I write that all descriptors are integers for consistency beteen
%% the different descriptors.
%%

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.  {\tt MPI\_CD\_TYPE}. 

%[Tony]
% I don't get all of this.  Why?
%
%%[Lyndon]
%% I don't understand what you don't get. A registry service is just
%% an easier (nonscalable, okay) way for concurrent entities to hook up
%% with one another, rather than having some common ancestor send descriptors
%% around in messages.
%% In fact I don't really need a group or process registry service, as mentioned
%% in the discussion section (yes, I know, not well presented), but
%% I do need a context registry service, and I'm being consistent
%% between different kinds of descriptors again. 
%% Suggestive syntax for a registry service is pretty boring, so
%% I skipped it.
%%

MPI provides a context descriptor registry service.  The operations
which this service upports are: register descriptor by name; deregister
descriptor; lookup descriptor identifier by name and validate, blocking
the caller until the name has been registered. 
\SeeReferNote{registry:check} 
Use of this service is not mandated. 
Programs which can conveniently be expressed without using the service
can ignore it without penalty. 

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

%[Tony]
% I do not understand the usefulness or formal need for all this
% validation and invalidation of process identifiers.  Why, where
% did it come from, what does it get us?  How can this be related
% to anything I have seen before?
%
%%[Lyndon]
%% Acquisition of a descriptor requires an allocator, and consumes
%% resource. In such cases it is good practice to provide a 
%% deallocator which frees resource. 
%%

% [Tony] 
% I understand the idea here, but not all the details.  Can this
% be justified/exemplified/simplified?
%
%%[Lyndon]
%% Unless I am missing the additional point in this comment, I can't
%% see the problem. Probably poor presentation of Proposal I++ :-)
%%

\subsubsection*{Descriptor Attributes}

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

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

This proposal recommends three forms for MPI point-to-point message
addressing and selection: null context; closed context; open context. 
It is further recommended that messages communicated in each form are
distinguished such that a Send operation of form X cannot match with a
receive operation of form Y, which requires that the 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 section
of MPI. 

\subsubsection*{Null Context Form}

The {\it null context\/} form contains no message context.
\SeeReferNote{null:context}

Message selection and addressing are expressed by {\tt (pd, tag)} where:
{\tt pd} is a process descriptor; {\tt tag} is a message tag.  

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

Receive can wildcard on {\tt pd} by supplying the value of a named
constant process descirptor, e.g.  {\tt MPI\_PD\_WILD}.  This proposal
makes no statment 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.
\SeeReferNote{closed:context}

Message selection and addressing are expressed by {\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. 

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

Receive cannot wildcard on {\tt cd}.  Receive can wildcard on {\tt rank}
by supplying the value of a named constant integer,
e.g.  {\tt MPI\_RANK\_WILD}.  This proposal makes no statment 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.
\SeeReferNote{open:context}

Message selection and addressing are expressed by {\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. 

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}.  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 {\tt (rcd, rank)} pair in Send (Receive) is
sufficient to determine the process descriptor of the receiver (sender). 

Receive cannot wildcard on {\tt lcd}.  Receive can wildcard on {\tt rcd}
by supplying the value of a named constant context descriptor, e.g. 
{\tt MPI\_CD\_WILD}, in which case Receive {\it must\/} also wildcard on
{\tt rank} as there is insufficient information to determine the process
descriptor of the sender.  Receive can wildcard on {\tt rank} by
supplying the value of a named constant integer, e.g.  {\tt
MPI\_RANK\_WILD}.  This proposal makes no statment 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 section of MPI by defining a further orthogonal
axis (as in the multi-level proposal of Gropp \& Lusk) which deals
with the form.  This is at the expense of multiplying the number of
Send and Receive procedures by a factor of three, and some difficulty
in details of the current point-to-point working document 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 each have advantages and disadvantages. 

\paragraph*{Option i:} The framework of the open context form is adopted and
extended.

We introduce the {\it null\/} descriptor, the value of which is defined
by a named constant, e.g.  {\tt MPI\_NULL}.  

The null context form is expressed as {\tt (MPI\_NULL, MPI\_NULL, pd,
tag)}, which is a little clumsy.  The closed context form is expressed
as {\tt (MPI\_NULL, cd, rank, tag)}, which is marginally inconvenient. 
The open context form is expressed as {\tt (lcd, rcd, rank, tag}), which
is of course natural. 

\paragraph*{Option ii:} The framework of the closed context form is 
adopted and extended.

We introduce the {\it null\/} descriptor, the value of which is defined
by a named constant, e.g.  {\tt MPI\_NULL}.  

The null context form is expressed as {\tt (MPI\_NULL, pd, tag)}, which
is marginally inconvenient.  The closed context form is expressed as
{\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 {\tt
(lcd, rcd)} pair at the expense of introducing some trickery.  We can
define a mechanism which ``globs'' together these two fields onto in an
identifier which Send and Receive can distinguish from a context
identifier and treat as the shorthand notation.  Then we should also
define a mechanism by which a receiver which has completed a Receive
with wildcard on {\tt rcd} is able to determine the valid context
descriptor of the sender.  This is a inconvenient.

%[Tony]
% I dislike this intensely.  There should be a group-pair data
% structure.  Group is never a pair of sub-groups.  It is a
% bad idea.    This is all to get around changing syntax, no?
%
%% [Lyndon]
%% I dislike this also. Of course it is all to get around extending
%% the syntax, it stinks of that.
%%

\paragraph*{Option iii:} The framework of the null context form is adopted
and extended.

The null context form is expressed as {\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 clumsy. 

%[Tony] 
% I dislike this intensely.  There should be a group-pair data
% structure.  Group is never a pair of sub-groups.  It is a
% bad idea.    This is all to get around changing syntax, no?
%
%% [Lyndon]
%% I dislike this also. Of course it is all to get around extending
%% the syntax, it stinks of that.
%%

\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 and
frame in which they are to operate. 

MPI does plan to describe symmetric collective communication operations. 
It is not possible to determine whether the proposal is sufficient to
allow implementation of the collective communication section of MPI in
terms of the point-to-point section of MPI without loss of generality,
since the collective operations are not yet defined. 

%[Tony] Check, but it is desirable that they be so writable, so we will
% have to watch.
%

Assymetric collective communication operations, especially those in
which the 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 ``glob'' form) which identify the contexts and frames in
which they are to operate. 

MPI does not plan to describe assymetric collective communication
operations.  Such operations are expressive when writing programs beyond
the SPMD model and comprise communicative funtionally distinct process
groupings.  This proposal recommends that such operations should be
considered in some reincarnation of MPI. 

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

% [Tony] 
% So, I gather that a set of groups is passable to a collcomm,
% and a pair is passable to a pt2pt.  That is neat, but it should
% still be a separate data structure, with separate calls than
% the intra-group version (at least for the pt2pt calls).
%
%% [Lyndon]
%% Currently, I am only thinking of passing either singlets or duplets 
%% to point-to-point and collective. 
%% I was trying to avoid separate - extra - calls to point-to-point
%% because that is already very large and there is a swell of concern
%% about the size thereof.
%%

%----------------------------------------------------------------------%
% 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 arguments for and against the MIMD model annex, and to some
extent explores the consquences of these arguments for MPI in a wider
sense. 

\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 a stricly SIMD fashion. 

The material describing processes in \ReferSection{processes} is
simplified:

\begin{itemize}

\item
processes have identical instruction blocks and different data blocks;

\item
process descriptor transmission and registry become redundant (Note,
however, that they are anyway redundant as context descriptor
transmission and registry coupled with context descriptor attribute
query and group descriptor attribute query is capable of providing
access to all process descriptors);

\item
dynamic process models are not considered.

\end{itemize}

The material describing process groupings in \ReferSection{groupings} is
simplified:

\begin{itemize}

\item
group descriptor transmission and registry become redundant (Note,
however, that they are anyway redundant as context descriptor
transmission and registry coupled with context descriptor attribute
query capable of providing access to all group descriptors.);

\item
the own process grouping explicitly becomes a group containing all
processes.

\end{itemize}

The material describing communication contexts in \ReferSection{contexts}
is simplified:

\begin{itemize}

\item
context descriptor transmission and registry become unnecessary.

\end{itemize}

The material describing point-to-point communication in
\ReferSection{point2point} is simplified:

\begin{itemize}

\item
the open context form becomes redundant;

\item
uniform integration ``Option i'' is deleted, and ``Option ii'' loses
``globs'' thus becoming simple enough that ``Option iii'' need not be
further considered. 

\end{itemize}

The material describing collective communication in 
\ReferSection{collective} is simplified:

\begin{itemize}

\item

there is no possibility of collective communication operations spanning
more than context.

\end{itemize}

\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
MPI are not suited to fine grained function driven or data driven
programming. The annex is intended to provide expresive power for
the ``MSPMD'' model, which is now described.

One of the simplest MIMD models is the ``host-node'' model, familiar in
EXPRESS and 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 vice versa!). 

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 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 computating. 
The debate is whether or not message passing approaches such as MPI
(which I simply refer to as MPI) should provide for this model. 

The negative argument is that such SPMD 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 parallel
prgrams. 

The positive argument is that communications between SPMD modules
requires 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 comparable with
the argument for MPI versus parallel compilation. 

\subsection{Notes}
\LabelSection{notes}

\begin{enumerate}

\item\LabelNote{integer:descriptors}
Descriptors are a plentiful but bounded resource.
They are expressed as integers for two reasons.  Firstly, this
expression facilitates uniform binding to ANSI~C and Fortran~77. 
Secondly, there is a later convenience in ensuring that process
descriptors in particular are expressed in integers, and I made all the
descriptors are integers for consistency.  In practice the descriptor
could be an index into a table of objects description structures or
pointers to such structures. 

\item\LabelNote{descriptor:cache}
It is possible to allow the user to save user defined attributes in
descriptors, as Littlefield has suggested. Such attributes should
not be communicated in either descriptor transmission or
the descriptor registry.

\item\LabelNote{process:identifiers}
The process descriptor is not a global unique process identifier but
must reference such an identifier.  The use of descriptors hides such
identifiers in order that they may be implementation dependent, and
enables more efficient access to additional process information in
implementations.  For example, the process identifier of a receiver may
not be sufficient to route a message to the receiver, and this
information can be referenced from the process descriptor. 

\item\LabelNote{group:identifiers}
The group descriptor is not a global unique group identifier but must
reference such an identifier.  The use of descriptors hides such
identifiers in order that they may be implementation dependeent, and
enables more efficient access to additional group information in
implementations.  For example, the size of the group and the map from
member ranks to process descriptors can be referenced from the group
descriptor. 

\item\LabelNote{context:identifiers}
The context descriptor is not a global unique context identifier but
must reference such an identifier.  The use of descriptors hides such
identifiers in order that they may be implementation dependent, and
enables more efficient access to additional context information in
implementations.  For example, the group descriptor of the frame can be
referenced from the context descriptor. 

\item\LabelNote{dynamic:processes}
The proposal does not prevent a process model which allows dynamic
creation and termination of processes however it does not favour an
asynchronous process creation model in which singleton processes are
created and terminated in an unstructured fashion.  The proposal does
favour a model in which blobs of processes are created (and terminated)
in a concerted fashion, and in which each group 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 worloads. 
The author suggests that concerted blob expand and contract operations
are most suitable for this purpose than asynchronous spawn/kill operations.

\item\LabelNote{registry:check}
There should probably also be a registry operation which checks whether
a name has been registered without the possibility of blocking the
calling process indefinitely.  The same registry could be used for
process, group and context descriptors. 

\item\LabelNote{process:coherency}
In the static process model it is assumed that processes are created in
concert, and that termination of one process implies termination of all
processes. In this case there is no coherency problem associated with
processes and process descriptors. In a dynamic process model there is
a coherency problem which processes and process descriptors since
a process can retain the descriptor of a process which has been
deleted. The proposal expects the user to ensure coherent usage.

\item\LabelNote{dynamic:groups}
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 author suggests concerted
group expand and contract operations are more generally useful than
asynchronous join/leave operations.

\item\LabelNote{group:blobs}
MPI has discussed the concept of the ``all'' group which contains all
processes.  The ``own'' group concept is intended to be 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 (which is a singleton).  There is a sense in
which a blob has a locally SPMD view.

\item\LabelNote{own:group}
This procedure looks like a process descriptor attribute query. 

\item\LabelNote{group:coherency}
Dynamic processes introduce a group coherency problem as a group
descriptor can contain the process descriptor of a process which has
been deleted.  Dynamic processes potentially introduce a group coherency
problem as a group descriptor can contain the process descriptor of a
process which has been deleted.  Group transmission introduces a group
and group descriptor coherenncy problem since a process can retain a
group descriptor of a group which has been identified group.  The
proposal expects the user to ensure coherent usage. 

\item\LabelNote{pd:to:rank}
The proposal did not include a function to convert a {\tt (gd, pd)} pair
into a rank.  It is suggested that this inverse map is allowed to be
arbitrarily slow. 

\item\LabelNote{dynamic:contexts}
Marc Snir has described a method by which global unique group
identifiers can be generated without use of shared global data.  The
description of context creation anticipates a similar method for global
unique context identifier generation.  However the synchronisation
requirement of this method makes it unnecessary for context creation. 
Synchronisation at creation of context within a process grouping frame
implies that all processes within the frame perform the same context
creations in the same sequence.  Therefore the combination of global
unique frame identifier and context creation sequence number provides a
global unique context identifier without communication. 

\item\LabelNote{own:context}
This procedure looks like a group descriptor attribute query.

\item\LabelNote{context:coherency}
The retention of a reference to a group descriptor by a context
introduces the potential for a context and context descriptor coherency
problem, as a context could contain a reference to the group descriptor
of a group which has been deleted.  This could be circumvented by
demanding that all such contexts are deleted before a group is deleted. 
Context descriptor transmission introduces a coherency problem since a
process can retain the descriptor of a context which has been deleted. 
The proposal expects the user to ensure coherent usage. 

\item\LabelNote{null:context}
This is somewhat like and PARMACS and PVM~3.  It is general purpose,
but not particularly expressive.  It does not provide facilities for
writers of parallel libraries.

\item\LabelNote{open:context}
This is somewhat like ZIPCODE and VENUS.  It is expressive in certain
SPMD programs where noncommunicative data driven parallel computations
can be performed concurrently. It provides facilities for writers of
SPMD like parallel libraries.

\item\LabelNote{closed:context}
This is somewhat like CHIMP and PVM~2.  It is expressive in certain
MIMD programs where communicative data driven parallel computations
can be performed concurrently. It provides facilities for MSPMD like
parallel libraries.

\end{enumerate}

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

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

\section{Conclusion}

This chapter has presented and discussed a proposal for communication
contexts within MPI.  In the proposal process groupings appeared as
frames for the creation of communication contexts, and communication
contexts retained certain properties of the frames used in their
creation. 

The author strongly recommends this proposal to the committee.

%
% 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 
         \--------------------------------------------------------/