Subject: my comments on Lyndon's Proposal I

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

%****
%**** Below are my comments on Lyndon's Proposal I.  In the next paragraph
%**** I note that we are actually converging to less than N proposals, though
%**** I have not seen Lyndon's new II proposal yet.  Does  it exist now?
%****
%**** To achieve a reasonable presentation at Dallas, we can have multiple
%**** proposals still on table (I think this a fair, well-thought-out
%**** approach, but if we can condense some, let's do it).
%**** 
%****
%**** After reading V, making my comments, and making my comments
%**** in addition to Lyndon's comments, I am convinced we can
%**** advance proposal V into something that is acceptable in the
%**** III/IV mold, without a further III/IV proposal.  Rik's
%**** dropping of the static context concept has simplified our
%**** group's efforts considerably, and I cannot disambiguate my
%**** III/IV proposal from Proposal V, given the Lyndon and Tony
%**** provisos and suggested improvements.  This is not a wimp out
%**** on my part.  I do not see benefit of advancing something that
%**** will look 90% like Proposal V at this point, and 97% like it
%**** if the Lyndon/Tony comments obtain in it (which they would if
%**** I wrote it now).  
%**** I would prefer that we hone Proposal V.  If Rik wants to keep
%**** his style, then I propose that Proposal III/IV become exactly
%**** what I just said, a reworking of V + comments.
%**** However, I think this will cause an unnecessary delay and
%**** digression just to achieve details.  Instead, we might pull
%**** such choices into Proposal V at this time (server vs. no server).
%**** to make what is common in our "approaches" more obvious.
%**** - Tony
%****
%**** (PS, Lyndon: Rik/Tony/Lyndon are authors of whole paper, because
%****  we are all working on this, and because one of us (ie, me) will
%****  make the final document cohesive, create a unified style, format,
%****  set of meanings.  This is the nature of collaboration.  I do
%****  not propose to include our other co-conspirators on such a document's
%****  list of authors, as there has been minimal input from them.  I
%****  Think that Rusty/Bill and Rik/Tony/Lyndon are operating equivalently.)
\documentstyle{report}
\begin{document}
\title{``Proposal'' I for MPI Communication Context Subcommittee}
\author{Lyndon~J~Clarke}
\date{March 1993}
\maketitle
%======================================================================%
% BEGIN "Proposal I"
% Lyndon J. Clarke
% March 1993
%
\chapter{Proposal I}

\section{Introduction}

This chapter proposes that ordered groups are used to provide
communication contexts, and that communication contexts do not appear
independently of process groupings.  The proposal reflects the
observation that an instance of a module in a parallel program typically
operates within a group of processes, and as such any communication
contexts associated with an instance of a module also bind the semantics
of process groups. 

This chapter makes a basic proposal which provides intra-group
communication but does not provide inter-group communication, and an
extended proposal which also provides inter-group communication.  The
proposals say nothing about use of message tags.  It is assumed that
these will be a bit string, expressed as an integer in the host langauge
(i.e.  ANSI C or Fortran~77, in the first instacnce.

These proposals should be viewed as a collection of recommendations to
other subcommittees within MPI, primarily the collective communications
subcommittee, the point-to-point communications subcommittee and the
process topologies subcommittee.  Concrete syntax is given in the style
of the C language for purposes of discussion only, and should be viewed
as an example of possible syntax as detailed syntax of described
operations is the responsibility of the language bindings subcommittee

%----------------------------------------------------------------------%
% BEGIN "Basic Proposal"
%

\subsection{Basic Proposal}

The main features of the basic proposal are:

\begin{itemize}

\item 
Process identifiers and group identifiers have opaque values expressed
as an integer type in the base language.  Semantics for passing process
identifiers in a message are defined, whereas semantics for passing
group identifiers in a message are not defined.

\item 
Group creation and destruction are concerted, synchronous, actions on
the part of the membership of the group concerned. 
%****
%**** loosely synchronous
%****
\item
Groups are {\it static\/} in that no provision is made for modification
of the membership of a group over the lifetime of the group.  Dynamic
group operations such as {\it resize\/} can be effected by destruction
of the existing group and creation of a new resized group.
%**** Why not by making an off-spring, instead of destructively!!!
\item
Group creation is effected by four means: explicit definition of the
membership of a group; partition of an existing group into one or more
distinct subgroups; identical duplication of an existing group;
topological duplication of an existing group. 

\item
Point-to-point communication provides for intra-group communication,
and makes no provision for inter-group communication.

\item
Collective communication provides for operations which are concerted
actions on the part of members of one group, and makes no provision for
operations which are concerted actions on the part of members of
multiple groups. 

\end{itemize}

\subsubsection{Process and Group Identifiers}

A {\it process identifier\/} is an opaque reference to an object which
is a single process.  A process identifier is expressed as an integer in
the host language and has a value defined by the system.  The only
meaningful host language operations on process identifiers are
assignment ({\tt =}), equality ({\tt ==}) and inequality ({\tt !=}).  

Each process has exactly one process identifier.  MPI should provide a
procedure which allows the user to determine the process identifier of
the calling process.  For example, {\tt mypid = mpi\_mypid()}. 

The identifier of the {\it null process\/}, defined to be a process
which cannot exist, is defined as a named constant and shall be referred
to as {\tt MPI\_PID\_NULL} in this proposal.  With the single exception
of the identifier of the null process, the value of a process identifier
is {\it process local\/}, meaning that if two processes A and B know the
identifier of a process P then the relationship between the values
of the identifiers known to A and B is undefined.

The user can pass the value of a process identifier in a message, since
it is an integer type in the host language, however the recipient of the
value cannot make defined use of that value in the MPI operations
described below --- the received process identifier is {\it invalid\/}. 
MPI will provide a mechanism which allows a process identifier to be
passed in a message in such a manner that the received identifier is
valid.  It is proposed that this shall be integrated with the buffer
descriptor mechanism (proposed by Bill Gropp and Rusty Lusk), by
addition of a procedure which places a logical reference to a process
identifier into the buffer descriptor, e.g.  {\tt mpi\_bd\_pid(bd,
\&pid)}.  Transmission of a process identifier using this mechanism
returns to the recipient a process identifier which is valid for use in
the MPI operations described below.  This transmission may side effect
state in the implementation of MPI at the recipient, and in particular
may reserve state at the recipient. 

MPI will provide a procedure which invalidates a process identifier,
allowing the implementation of MPI to recover reserved state, e.g.  {\tt
mpi\_pid\_invalidate(pid)}.  This is an error if {\tt pid} is {\tt
MPI\_PID\_NULL}, or if {\tt pid} is the identifier of the calling
process. 

It is further proposed that MPI provide a process identifier registry
service.  This service allows any process to register its own process
identifer by name, and deregister its process identifier.  The service
allows any process to determine whether a name has been registered
without blocking the calling process, and to map that name into a
valid process identifier with the possibility of blocking the calling
process.  Use of this service is not mandated, and components of
programs which do not require this service are not expected to make
use thereof.
%**** I don't get all of this.  Why?
%****
A {\it group identifier\/} is an opaque reference to an object which
is a group of processes. A group identifier is expressed as an integer in
the host language and has a value defined by the system.  The only
meaningful host language operations on group identifiers are
assignment ({\tt =}), equality ({\tt ==}) and inequality ({\tt !=}).  

The identifier of the {\it null group\/}, defined to be a group which
cannot exist, is defined as a named constant and shall be referred to as
{\tt MPI\_GID\_NULL} in this proposal.  With the single exception of the
identifier of the null group, the value of a group identifier is {\it
process local\/}, meaning that if two processes A and B know the
identifier of a group G then the relationship between the values of the
identifiers known to A and B is undefined. 

The user can pass the value of a group identifier in a message, since it
is an integer type in the host language, however the recipient of the
value cannot make defined use of that value in the MPI operations
described below --- the identifier is {\tt invalid\/}.  MPI will not
provide a mechanism which allows a group identifier to be passed in a
message in such a manner that the received identifier is valid. 
%**** Then why allow it to be passed?
%****
The canonical representation of a group is an array of distinct process
identifiers, although it may be possible to use hashing functions with
lower space complexity and marginally higher time complexity.  A group
is {\it static\/}, in that it's membership may not change over the
lifetime of the group. 

There is a well defined {\it size\/} of a group, and MPI will provide a
procedure which allows the user to determine the size of a group.  For
example, {\tt size = mpi\_grp\_size(gid)}.  This procedure is an error
if {\tt gid} is {\tt MPI\_GID\_NULL}. 

There is a well defined {\it rank\/} of a process within the group, i.e. 
the position in the representational array at which the process
identifier is held.  MPI will provide a procedure which allows the user
to determine the rank of the calling process within a group.  For
example, {\tt mpi\_grp\_myrank(gid)} returns the rank of the calling
process within the group referred to by {\tt gid}.  This procedure is an
error if {\tt gid} is {\tt MPI\_GID\_NULL}. 

MPI should provide a procedure to determine the member rank of a process
within a group given the group identifier and a valid process
identifier, e.g.  {\tt rank = mpi\_grp\_rank(gid,pid)}.  This procedure
may ``fail'' if the process identified by {\tt pid} is not a member of
the group identifier by {\tt gid}, and can be used to determine whether
a given process is a member of a given group.  This procedure is an
error if {\tt gid} is {\tt MPI\_GID\_NULL}. 
%****
%**** Why an error, why not just fail?
%****
MPI should provide a procedure to determine the process identifier of a
group member given the group identifier and member rank, e.g.  {\tt pid
= mpi\_pid(gid,rank)}.  This procedure should validate the returned
process identifier.  This procedure is an error if {\tt gid} is {\tt
MPI\_GID\_NULL}. 

\subsubsection{Group Creation and Destruction}

MPI will provide four methods for creation of groups, and a procedure
to destroy an existing group. 

A group may be created by explicit definition of the pids of the members
of the group.  For example, {\tt gid = mpi\_grp\_definition(npids,pids)}
where {\tt gid} is the identifier of the newly created group, {\tt
npids} is the number of processes in the new group, and {\tt pids} is an
array containing the (valid) process identifiers of the processes in the
group.  This procedure must be called my all members of the group, and
does not return until all members have made the call. 

A group may be created by identical duplication of an existing group. 
For example, {\tt gidb = mpi\_grp\_duplication(gida)} where {\tt gidb}
is the group identifier of the newly created group and {\tt gida} is the
identifier of an existing group. The created group inherits all properties
of the source group, including any topological properties. This operation
has the same synchronisation properties as creation of group by
definition.
%**** 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.
%****
A group may be created by topological duplication of an existing group. 
Details of topological groups are under consideration within the process
topologies subcommittee and will not be further discussed here.  A group
created by topological duplication inherits the size of the source
group, and also inherits the membership list of the source group
although the list may be ordered differently in the created group. 
These operations have the same synchronisation properties as creation of
group by identical duplication.  Where groups have additional
topological attributes MPI should also provide procedures which allow
the user to determine such attributes. 

One or more groups may be created by partition of an existing group into
distinct subgroups by key.  For example, {\tt gidb =
mpi\_grp\_partition(gida, key)} where {\tt gidb} is the group identifier
of the newly created group corresponding to the given {\tt key} and {\tt
gida} is the group identifier of the group which is being partitioned
according to the {\tt key} values supplied.  MPI should define a named
constant which is a {\it null\/} {\tt key} value, for example {\tt
MPI\_KEY\_NULL}, in order that members of the parent group can choose
not to become members of any child group, and in which case the
procedure should return {\tt MPI\_GID\_NULL}.  Groups created by
partition share the same ordering of process member ranks as the parent
group.  This operation synchronises the members of the parent group, and
therefore implicitly synchronises the members of the created group(s). 

A group may be destroyed, e.g. {\tt mpi\_grp\_deletion(gid)}, which
destroys the group identified by {\tt gid}.  This operation synchronises
the group members, and invalidates the group identifier. 

\subsubsection{Point-to-point communication}

There are arguments either way for point-to-point routines which accept
a {\tt (gid, rank)} pair, and for routines which accept a {\tt pid}. 
This proposal supports and seperates both approaches to addressing and
selection within the same syntax, avoiding the introduction of sets of
procedures to handle each case. 

In order to provide expressive power to intra-group communication,
point-to-point communication should accept a {\tt (gid, rank)} pair,
where {\tt gid} is a valid group identifier and {\tt rank} is a member
rank within the group identified by {\tt gid}.  In message addressing
the sender specifies the {\tt rank} and {\tt gid} of the receiver. In
message selection the receiver specifies the {\tt rank} and {\tt gid}
of the receiver.  The sender and receiver must both specify the same
{\tt gid} in order for a match to occur.  The {\tt gid} field is not
allowed to take a {\it wildcard\/} value in message selection.  The
{\tt rank} field is allowed to take a {\it wildcard\/} value in
message selection, e.g.  {\tt MPI\_RANK\_WILD}, which will match with
any rank.  One is encouraged to visualise a seperate message queue or
port at each process for each group of which that process is a member
(and indeed this may be an advantageous implementation feature).
%**** But not a required feature of an implementation!

In order to accommodate process identifier based addressing and
selection into the same syntax, this proposal advocates that
point-to-point communication should also accept the null group ({\tt gid
= MPI\_GID\_NULL}), in which case the {\tt rank} is interpreted as a
valid {\tt pid}.  The {\tt pid} is allowed to take a {\it wildcard\/}
value in message selection, e.g.  {\tt MPI\_PID\_WILD}.  The
point-to-point section should provide a procedure which allows a
recipient to recover the process identifier of the sender.  The
discussion of matching above extends to this case, and one is also
encouraged to visualise a separate message queue or port for messages
referred to by {\tt MPI\_GID\_NULL}. 

In the case of process identified wildcard receive, the process
identifier recovered by the receiver may be unknown to the receiver.  It
is proposed that an implicit validation of the process identifier must
be performed by the MPI implementation, in order that the recipient is
returned a valid process identifier, else the returned identifier is of
little or no use to the recipient. 
%****
%**** 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?
%****
\subsubsection{Collective communication}

Collective communication operations within MPI should be restricted to
the scope of a single group.  It will be sufficient for these procedures
to accept a group identifier, and possibly a message tag in order to
distinguish multiple outstanding operations within the same group. 
These procedures must not accept {\tt MPI\_GID\_NULL}. 
%**** Why not, but do nothing...

It is not possible to determine whether this is strategy allows all of
the MPI collective communication routines to be written in terms of MPI
point-to-point routines without loss of generality, since the set of
collective communication routines is not yet determined.  This proposal
takes the view that it is the responsibility of the collective
communications subcommittee to determine whether such a goal is
desirable, and if so to describe procedures which comply with this goal. 
%**** Check, but it is desirable that they be so writable, so we will
%**** have to watch.

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

%----------------------------------------------------------------------%
% BEGIN "Extended Proposal"
%

\subsection{Extended Proposal}

The main additional features of the extended proposal are:

\begin{itemize}

\item 
Semantics for passing a group identifier in a message are defined,
and a group registry is introduced. 

\item
Point-to-point communication is extended to allow inter-group
communication without syntactic intrusion on intra-group communication. 

\item
Collective communication operations involving a concerted action on the
part of members of two or more groups is suggested.

\end{itemize}

\subsubsection{Process and Group Identifiers}

The extended proposal says nothing more about process identifiers than
the basic proposal. 

The extended proposal defines a mechanism by which a group identifier
may be passed in a message in such a manner that the received
identifier is valid, and the mechanism should be analagous to that
which allows process identifiers to be transmitted.  It is proposed
that this shall be integrated with the buffer descriptor mechanism
(proposed by Bill Gropp and Rusty Lusk), by addition of a procedure
which places a logical reference to a group identifier into the buffer
descriptor, e.g.  {\tt mpi\_bd\_gid(bd, \&gid)}.  Transmission of a
group identifier using this mechanism returns to the recipient a group
identifier which is valid for use in the MPI operations described
above and below, and as further qualified below.  This transmission
may side effect state in the implementation of MPI at the recipient,
and in particular may reserve state at the recipient.

MPI will provide a procedure which invalidates a group identifier,
allowing the implementation of MPI to recover reserved state, e.g.  {\tt
mpi\_invalidate\_gid(gid)}.  This is an error if {\tt gid} is {\tt
MPI\_GID\_NULL}, or if {\tt gid} is the identifier of a group of which
the calling process is a member. 
%**** I understand the idea here, but not all the details.  Can this
%**** be justified/exemplified/simplified?
%****
It is further proposed that MPI provide a group identifier registry
service.  This service allows any group  to register its own group
identifer by name, and deregister its group identifier.  The service
allows any group to determine whether a name has been registered
without blocking the calling group, and to map that name into a
validated group identifier with the possibility of blocking the
calling group. The group registry procedures should synchronise
the calling group, permitting more efficient implementations than
asynchronous operations.

The definition of a valid group identifier is extended to include all
groups of which the process is a member and all those which are
validated by one of the above mechanisms.  The small suite of procedures
which map between process identifiers, group identifiers and member
ranks are defined to work with valid group and process identifiers. 

\subsubsection{Point-to-point communication}

The point-to-point communication syntax and semantics described in the
basic proposal do not extend directly to the case of inter-group
communication.  The reason is quite simple --- the sender and receiver
do not supply the same group since the group of the sender and the group
of the receiver are different. 

The basic approach is to express point-to-point communication in terms
of a triplet {\tt (localGroup, remoteGroup, remoteRank)}.  In this
notation the sender specifies the sender group identifier, then the
receiver group identifier and finally the receiver rank.  The receiver
specifies the receiver group identifier, then the sender group
identifier, and finally the sender rank.  The {\tt localGroup} field may
not take a wildcard value, corresponding directly to the rule that the
group in the basic proposal may not take a wildcard value.  The {\tt
remoteGroup} field may take a wildcard value, e.g.  {\tt
MPI\_GID\_WILD}, which matches with any group.  The {\tt remoteRank} may
also take a wildcard value, as in the basic proposal.  The
point-to-point section should provide procedures which allow a message
recipient to recover the group and rank of the sender. 

In the case of {\tt remoteGroup} wildcard receive, the group identifier
recovered by the receiver may be unknown to the receiver.  It is
proposed that an implicit validation of the group identifier must be
performed by the MPI implementation, in order that the recipient is
returned a valid group identifier, else the returned identifier is of
little or no use to the recipient.

In order to accomodate inter-group addressing and selection into the
framework of the basic proposal, the extended proposal suggests a
careful redefinition of the {\tt gid} discussed in the basic proposal. 
With careful presentation this redefinition need not intrude
conceptually on the basic proposal, although I shall give a less careful
description here, suggestive of two different flavours of presentation. 
In the basic proposal, the {\tt gid} was formally a reference to a
group.  In the extended proposal the {\tt gid} is formally composed of
references to two groups, and can be thought of as a shorthand notation
for {\tt (localGroup, remoteGroup)}. 
%**** 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?
The identifier of the null group, a {\it null\/} identifier, is a valid
identifier which is formally composed of a pair of references to the
null group, and may be used in the fashion described in the basic
proposal. 

The group creation functions provide a symmetric, or {\it unary\/},
identifier formally composed of two references to the same group.  This
group is {\it local\/} since the process in question is a member of the
group.  An identifier which composes a pair of references to a local
group is logically identical to a group identifier as implied in the
basic proposal, and may be used for point-to-point and collective
communications in an identical fashion. 

The group identifier transmission and registry lookup procedures also
provide a symmetric, or {\it unary\/}, identifier which again is
composed of a pair of references to the same group.  This group is
{\it remote\/} when the process is not a member of the group, or is
local when the process is a member of the group.  An identifier which
composes a pair of references to a remote group is logically identical
to the identifier a remote group as implied above, and is not valid
for either point-to-point or collective communications.

Inter-group communication is effected by use of assymetric, or {\it
binary} identifiers, composed of references to two different groups, the
first of which is local and the second of which is either local or
remote.  Such identifiers are constructed by the use of a ``glob''
operation, which returns an identifier referencing the first operand as
the local field and the second operand as the remote field.  The glob is
defined to be an error unless: both operands are symmetric (unary); the
first operand refers to a local group.  The identifier returned by a
glob is valid for point-to-point communciation and invalid for
collective communication. 

The point-to-point communication section should provide a procedure to
determine the group identifiers object of a completed receive.
Procedures which ``unglob'' an assymetric (binary) group identifier
should be provided, returning the local and remote fields as valid
identifiers.

This can be viewed as a continuation of a generalised approach to
point-to-point communication began in the basic proposal, in which
operation are specified in terms of object identifiers and instance
identifiers where objects are composed of multiple instances.  The
nature of the instance identified, and the semantics of the operation,
are dependent of the nature of the object identified, exploiting some
genericity. 

\begin{center}
\begin{tabular}{lll}
object identifier           & instance identifier       & action \\
\hline
null group identifier       & basic process identifier  & basic communication \\
unary group identifier      & local process rank        & intra-group communication \\
binary group identifier     & remote process rank       & inter-group communication \\
\end{tabular}
\end{center}

\subsubsection{Collective communication}

There are a number of collective communication operations which
logically extend over two or more groups. 

Some examples of two-group collective communications which are common in
the simple host-node programming model are:

\begin{itemize}

\item
{\it Broadcast\/} is an implicitly assymetric operation.  There is
exactly one sender and there are many receivers, each of which receives
an identical message.  The sender is a member of a singleton group G and
the receivers are members of a group H. 

\item
{\it Scatter\/} is an implicitly assymetric operation. There is exactly one
sender and there are may receivers, each of which receives a different
message. The sender is a member of a singleton group G and the receivers
are members of a group H.

\item
There is a variant of {\it gather\/}, which returns the gathered data to
a single process, which is an implicitly assymetric operation.  There is
exactly one receiver and there are many senders.  The receiver is a
member of a singleton group G and the senders are members of a group H. 

\item
There is a variant of {\it reduce}, which returns the reduced data to a
sinle process, which is an implicitly assymetric operation.  There is
exactly one receiver and there are many senders.  The receiver is a
member of a singleton group G and the senders are members of a group H. 

\end{itemize}

Other patterns arise in ``process'' graphs where each ``process'' is
allowed to be parallel.  For example:

\begin{itemize}

\item
{\it all-to-all\/} communciation in which the senders and receivers are
distinct processes.  The senders are members of a group G and the
receivers are members of a group H.  The two groups G and H need not be
of the same size. 

\end{itemize}

The assymetric (binary) group identifier objects described for
point-to-point communications in this extended proposal are immediately
suitable for each of the two-group collective communication operations
described. 

%
% END "Extended Proposal"
%----------------------------------------------------------------------%
%**** 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).
%****
\section{Conclusion}

This chapter has propose that ordered groups are used to provide
communication contexts, and that communication contexts do not appear
independently of process groupings. The chapter made a basic proposal
which provides intra-group communication but does not provide
inter-group communication, and an extended proposal which also
provides inter-group communication.

The basic proposal provides expressive semantics for the case of
intra-group communication such as arises in program which compose data
driven parallelism, and is closely related to that which was discussed
by Marc Snir at the February meeting in Dallas, and builds on
discussions which have taken place in various subcommittees. The key
additional features are: point-to-point communication can also be
expressed in terms of process identifiers; a process registry service
was added, use of which is optional.

The extended proposal adds expressive semantics for the case of
inter-group communication such as arises in programs which compose
combinations of data and function driven parallelism. This
functionality has been constructed in such a manner that there is no
syntactic or performance intrusion on the content of the basic
proposal, and the additional conceptual content can be presented
seperately from a presentation of intra-group communication.

%
% END "Proposal I"
%======================================================================%
\end{document}
>------------------------------ Cut Here ------------------------------<

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