Subject: Proposal V, LaTeX

From: L J Clarke <[email-masked]>
Date: Fri, 19 Mar 93 12:37:29 GMT

LaTeX-ified Proposal V of Rik. PostScript to follow.

----------------------------------------------------------------------
\documentstyle{report}
\begin{document}
\title{``Proposal V'' for MPI Communication Context Subcommittee}
\author{Rik~Littlefield}
\date{March 1993}
\maketitle
%======================================================================%
% BEGIN "Proposal V"
% Rik Littlefield
% March 1993
%
\chapter{Proposal V}

\section{Summary}

\begin{itemize}

\item
    Group ID's have local scope, not global.  Groups are
    represented by descriptors of indefinite size and opaque
    structure, managed by MPI.  Group descriptors can be
    passed between processes by MPI routines that translate
    them as necessary.  

    (This satisfies the same needs as global group ID's, but
    its performance implications are easier to understand and
    control.)

\item
    Arbitrary process-local info can be cached in group
    descriptors.

    (This allows collective operations to run quickly after
    the first execution in each group, without complicating
    the calling sequences.)

\item
    There are restrictions that permit groups to be layered
    on top of pt-pt.

\item
    Pt-pt communications use only TID, context, and tag, and
    are specified to be fast.

\item
    Group control operations (forming, disbanding, and
    translating between rank and TID) are NOT specified to be
    fast.

\end{itemize}

\section{Detailed Proposal}

\begin{itemize}

\item
  Pt-pt uses only ``TID'', ``context'', and ``message tag''.  TID's, 
  contexts, and message tags have global scope; they can be
  copied between processes as integers.  TID's and contexts are 
  opaque; their values are managed by MPI.  Message tags are
  controlled entirely by the application.

\item
  Pt-pt communication is specified to be fast in all cases.
  (E.g., MPI must initialize all processes such that any
  required translation of the TID is faster than the fastest
  pt-pt communication call.)

\item
  A group is represented by a ``group descriptor'', of indefinite
  size and opaque structure, managed by MPI.  The group
  descriptor can be referenced via a ``process-local group ID'',
  which is typically just a pointer to the group descriptor.
  (Group ID's with global scope do not exist.)

\item
  Group descriptors can be copied between arbitrary
  processes via MPI-provided routines that translate them
  to and from machine- and process-independent form.  A
  process receiving a group descriptor does not become a member
  of the group, but does become able to obtain information about
  the group (e.g., to translate between rank and TID).

\item
  Arbitrary information can be cached in a group descriptor.
  This is, MPI routines are provided that allow any routine to
  augment a group descriptor with arbitrary information,
  identified by a key value, that subsequently can be retrieved
  by any routine having access to the descriptor.  Cached
  information is not visible to other processes and is stripped
  when a group descriptor is sent to another process.  Retrieval
  of cached information is specified to be fast (significantly 
  cheaper than a pt-pt communication call).

\item  
  Group descriptors contain enough information to
  asynchronously translate between (group,rank) and TID for
  any member of the group, by any process holding a descriptor
  for the group.  MPI routines are provided to do these
  translations.  Translation is not specified to be fast.

\item
  At creation, each group is assigned a globally unique
  ``default group context'' which is kept in the group
  descriptor and can be quickly extracted.  This extraction
  is specified to be fast (comparable to a procedure call).

\item
  The default group context can be used for pt-pt
  communication by any module operating within the group, but
  only for exactly paired send/receive with exact match on
  TID, context, and message tag.  Call this the
  ``paired-exact-match constraint''.  This constraint allows
  independent modules to use the same context without
  coordinating their tag values.  (Assumes: tight sequencing
  constraints for both blocking and non-blocking comms in
  pt-pt MPI.)

\item
  A modules that does not meet the paired-exact-match constraint
  must use a different globally unique context value.  An MPI
  routine will exist to generate such a value and broadcast it to
  the group.  The cost of this operation is specified to be
  comparable to that of an efficient broadcast in the group,
  i.e. log(G) pt-pt startup costs for a group of G processes.
  [See Implementation note 1.]
  
\item
  Context values are a plentiful but exhaustible resource.  If
  further use is anticipated, a context may be cached;
  otherwise it should be returned.  (Note: the number of
  available contexts should be several times the number of
  groups that can be formed.)

\item
  When a group disbands, its group descriptor is closed and
  any cached information is released.  (The MPI
  group-disbanding routine does this by calling destructor
  routines that the application provided when the
  information was cached.)  Copies of the group descriptor
  must be explicitly released.  It is an error to make any
  reference to a descriptor of a disbanded group, except to
  release that descriptor.

\item
  All processes that are initially allocated belong to the
  INITIAL group.  (In a static process model, this means all
  processes.)  An MPI routine exists for obtaining a reference to
  the INITIAL group descriptor (i.e., a local group ID for
  INITIAL).

\item
  Groups are formed and disbanded by synchronous calls on all
  participating processes.  In the case of overlapping groups,
  all processes must form and disband groups in the same
  order.  [See Implementation Note 2.]

\item
  All group formation calls are treated as a partitioning of some
  group, INITIAL if none other.  The calls include a reference to
  the descriptor of the group being partitioned, the TID of the
  new group's ``root process'', the number of processes in the
  group, and an integer ``group tag'' provided by the application.
  The group tag must discriminate between overlapping groups that
  may be formed concurrently, say by multiple threads within
  a process.  [See Implementation Note 2.]

\item
  Collective communication routines are called by all members of
  a group in the same order.

\item
  Blocking collective communication routines are passed only a
  reference to the group descriptor.  To communicate, they can
  either use the default group context or internally allocate a
  new context, with or without cacheing.

\item
  Non-blocking collective communication routines are passed a
  reference to the group descriptor, plus a ``data tag'' to
  discriminate between concurrent operations in the same
  group.  (Question: is sequencing enough to do this?)  An
  implementation is allowed but not required to impose
  synchronization of all cooperating processes upon entry to a
  non-blocking collective communication routine.

\end{itemize}

\section{Advantages \& Disadvantages}

\subsection*{Advantages}

\begin{itemize}

\item
  This proposal is implementable with no servers and can be
  layered easily on existing systems.

\item
  Cacheing auxiliary information in group descriptors allows 
  collective operations to run at maximum speed after the first
  execution in each group.  (Assumes that sufficient context
  values are available to permit cacheing.)

\item
  Speed of cached collective operations does not depend on speed
  of group operations such as formation or translation between
  rank and TID.

\item
  Requires explicit translation between (group,rank) and TID,
  which makes pt-pt performance predictable no matter how
  the functionality of groups gets extended.

\item
  Communication both within and between groups seems conceptually
  straightforward.

\end{itemize}

\subsection*{Disadvantages}

\begin{itemize}

\item
  Requires explicit translation between (group,rank) and TID,
  which may be considered awkward.

\item
  Communication between different groups may be considered
  awkward.

\item
  No free-for-all group formation.  A process must know
  something about who its collaborators are going to be
  (minimally, the root of the group).

\item
  Requires explicit coherency of group descriptors, which is not
  convenient -- application must keep track of which processes
  have copies and what to do with them.

\item
  Static group model.  Processes can join and leave
  collaborations only with the cooperation of the other group
  members in forming larger or smaller groups.

\item
  No direct support for identifying the group from which a
  message came.  The sender cannot embed its group ID in its
  message, since group ID's are not globally meaningful.  One
  method to address this problem is to have the sender embed its
  group context as data in the message, then have the receiver
  use that value to select among group descriptors that it had
  already been sent.

\end{itemize}

\section{Comments \& Alternatives}

\begin{itemize}

\item
  The performance of group control functions is explicitly
  unspecified in order to provide performance insurance.  The
  intent is to encourage program designs whose performance won't
  be killed if the functionality of groups is expanded so as to
  be unscalable or require expensive services.

\item
  Adding global group ID's would seriously interfere with
  layering this proposal on pt-pt.  The problem is not generating
  a unique ID, but using it.  If just holding a global group ID
  were to allow a process to asynchronously ask questions about
  the group (like translating between rank and TID), then a group
  information server of some sort would be required, and MPI
  pt-pt does not provide enough capability to construct such a
  beast.

\item
  The restriction that only paired-exact-match modules can run in
  the default group context could be relaxed to something like ``a
  module that violates the paired-exact-match constraint can run
  in the default group context if and only if it is the only
  module to run in that context''.  This seems too error-prone to
  be worth the trouble, since even the standard collective ops
  might be excluded.  (It would also conflict with Implementation
  Note 1.]

\item
  Group formation can be faster when more information is provided
  than just the group tag and root process.  E.g. if all members
  of the group can identify all other members of a P-member
  group, in rank order, then O(log P) time is sufficient; if only
  the root is known, O(P) time may be required.  This aspect
  should be considered by the groups subcommittee in evaluating
  scalability.

\end{itemize}

\section{Implementation Notes}

\begin{enumerate}

\item
   To generate and broadcast a new context value: Generate the
   context value without communication by concatenating a
   locally maintained unique value with the process number in
   some 0..P-1 global ordering scheme.  This assumes that
   context values can be significantly longer than log(P) bits
   for an application involving P processes.  If not, then a
   server may be required, in which case by specification it
   has to be fast (comparable to a pt-pt call).  There is no
   need to generate a new context for the broadcast since it
   can be coded to use the default group context by meeting the
   paired-exact-match constraint.)

\item
   The following is intended only as a sanity check on the claim
   that this proposal can be layered on MPI.  Improvements to
   improve efficiency or to use fewer contexts will be greatly
   appreciated.

   In addition to a default group context, each group descriptor
   contains a ``group partitioning context'' and a ``group
   disbanding context'' that are obtained and broadcast at the
   time the group is created.  In the case of the INITIAL group,
   this is done using paired-exact-match code and any context,
   immediately after initialization of the MPI pt-pt level.  (At
   that time, no application code will have had a chance to issue
   wildcard receives to mess things up.)

   Group partitioning is accomplished using pt-pt messages in the
   partitioning context of the current group (i.e., the one being
   partitioned), with message tag equal to the group tag provided
   by the application.  In the worst (least scalable) case, the
   root of the new group must wildcard the source TID.  (This
   violates the paired-exact-match constraint, which is why group
   formation must happen in a special context.)

   Group disbanding is done with pt-pt messages in the group
   disbanding context.  This keeps group control from being
   messed up no matter how the application uses wildcards.

\end{enumerate}

\section{Examples}

{\bf (To be provided)}

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

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

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