Subject: 2nd draft of Collective Communication proposal

From: [email-masked] (Al Geist)
Date: Tue, 20 Apr 1993 16:18:20 -0400

After studying the latest point-to-point draft by Marc
and the votes from the last meeting, I have revised the
original collective communication draft.

Comments can be directed to the mpi-collcomm committee.
Here is the LaTeX version, a postscript version will follow
in a separate message.

Al
                          -----------------------------
   __o        /\          Al Geist
 _`\<,_    /\/  \         Oak Ridge National Laboratory
(_)/ (_)  /      \        (615) 574-3153   [email-masked]
* * * * * * * * * *       -----------------------------

%     MPI Authors:
% This is MY version of YOUR chapter.  It has a wrapper so that you
% should be able to simply LaTeX this.
%
% Please work from this text so that we are in synch.
%
% --Steve Otto

\documentstyle[twoside,11pt]{report}
\pagestyle{headings}
%\markright{ {\em Draft Document of the MPI Standard,\/ \today} }
\marginparwidth 0pt
\oddsidemargin=.25in
\evensidemargin  .25in
\marginparsep 0pt
\topmargin=-.5in
\textwidth=6.0in
\textheight=9.0in
\parindent=2em

%   ----------------------------------------------------------------------
%   mpi-macs.tex  --- man page macros,
%                discuss, missing, mpifunc macros
%
% ----------------------------------------------------------------------
% a couple of commands from Marc Snir, modified S. Otto

\newlength{\discussSpace}
\setlength{\discussSpace}{.7cm}

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

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

\newlength{\codeSpace}
\setlength{\codeSpace}{.3cm}

\newcommand{\mpifunc}[1]{\vspace{\codeSpace} {\bf #1} \vspace{\codeSpace} }

% -----------------------------------------------------------------------
%  A few commands to help in writing MPI man pages
%
\def\twoc#1#2{
\begin{list}
{\hbox to95pt{#1\hfil}}
{\setlength{\leftmargin}{120pt}
 \setlength{\labelwidth}{95pt}
 \setlength{\labelsep}{0pt}
 \setlength{\partopsep}{0pt}
 \setlength{\parskip}{0pt}
 \setlength{\topsep}{0pt}
}
\item
{#2}
\end{list}
}
\outer\long\def\onec#1{
\begin{list}
{}
{\setlength{\leftmargin}{25pt}
 \setlength{\labelwidth}{0pt}
 \setlength{\labelsep}{0pt}
 \setlength{\partopsep}{0pt}
 \setlength{\parskip}{0pt}
 \setlength{\topsep}{0pt}
}
\item
{#1}
\end{list}
}
\def\manhead#1{\noindent{\bf{#1}}}

\hyphenation{RE-DIS-TRIB-UT-ABLE sub-script mul-ti-ple}

\begin{document}

\setcounter{page}{1}
\pagenumbering{roman}

\title{ {\em D R A F T} \\ Document for a Standard Message-Passing Interface}

\author{Scott Berryman, {\em Yale Univ} \\
James Cownie, {\em Meiko Ltd} \\
Jack Dongarra, {\em Univ. of Tennessee and ORNL} \\
Al Geist, {\em ORNL} \\
Bill Gropp, {\em ANL} \\
Rolf Hempel, {\em GMD} \\
Bob Knighten, {\em Intel} \\
Rusty Lusk, {\em ANL} \\
Steve Otto, {\em Oregon Graduate Inst} \\
Tony Skjellum, {\em Missisippi State Univ} \\
Marc Snir, {\em IBM T. J. Watson} \\
David Walker, {\em ORNL} \\
Steve Zenith, {\em Kuck \& Associates}   } 

\date{April 20, 1993 \\
This work was supported by ARPA and NSF under contract number \#\#\#,
by the National Science Foundation Science and
Technology Center Cooperative Agreement No. CCR-8809615.
}

\maketitle
\hfuzz=5pt
%\tableofcontents

%\begin{abstract}
%We don't have an abstract yet.
%\end{abstract}

\setcounter{page}{1}
\pagenumbering{arabic}

\chapter{Collective Communication}
\label{sec:coll}

\begin{center}
Al Geist \\ Marc Snir
\end{center}

\section{Introduction}

This section is a draft of the current proposal for collective communication.
Collective communication is defined to be communication that involves
a group of processes.  Examples are broadcast and global sum.
A collective operation is executed by having all processes in the group call the
communication routine, with matching parameters.
Routines can (but are not required to) return as soon as their
participation in the collective communication is complete.  The completion
of a call indicates that the caller is now free to access the locations in the
communication buffer, or any other location that can be referenced by the
collective operation.  However, it does not indicate that other processes in
the group have started the operation (unless otherwise indicated in the
description of the operation).   However, the successful completion of
a collective communication call may depend on the execution of a matching call
at all processes in the group.

The syntax and semantics of the collective operations is
defined so as to be consistent with the syntax and semantics of the point to
point operations.

The reader is referred to the point-to-point communication section 
of the current MPI draft for information concerning communication buffers 
and their manipulations. 
The context section describes the formation,
manipulation, and query functions (such as group size) that are
available for groups and group objects.

The collective communication routines are built above the point-to-point
routines.  While vendors may optimize certain collective routines for
their architectures, a complete library of the collective communication
routines can be written entirely using point-to-point communication
functions.  We are using naive implementations of the collective calls in terms
of point to point operations in order to provide an operational definition of
their semantics.

The following communication functions are proposed.
\begin{itemize}
\item
Broadcast from one member to all members of a group.
\item
Barrier across all group members
\item
Gather data from all group members to one member.
\item
Scatter data from one member to all members of a group.
\item
Global operations such as sum, max, min, etc., were the result
is known by all group members and a variation where the result is
known by only one member. The ability to have user defined
global operations.
\item
Simultaneous shift of data around the group, the simplest example
being all members sending their data to (rank+1) with wrap around.
\item
Scan across all members of a group (also called parallel prefix).
\item
Broadcast from all members to all members of a group.
\item
Scatter data from all members to all members of a group
(also called complete exchange or index).
\end{itemize}

To simplify the collective communication interface it is
designed with two layers. The low level routines have all the
generality of, and make use of, the communication buffer routines
of the point-to-point section which allows arbitrarily complex
messages to be constructed. The second level routines are
similar to the upper level point-to-point routines in that they send
only a contiguous buffer.

\section{Group Functions}

A full description of the group formation and manipulation functions
can be found in the context chapter of the MPI document.
Here we describe only those group functions that are used in the
semantic description of the collective communication routines.

An initial group containing all processes is supplied by default in MPI.
MPI provides a procedure that returns the handle to this initial group.
The processes in the inital group each have a unique rank in the group
represented by integers (0, 1, 2, ..., [number-of-processes~-~1].

\mpifunc{MPI\_ALLGROUP(group)} 
Return the descriptor of the inital group containing all processes.
\begin{description}
\item[OUT group] handle to descriptor object of initial group.
\end{description}

\mpifunc{MPI\_RANK(group, rank)} 
Return the rank of the calling process within the specified group.
\begin{description}
\item[IN group] group handle
\item[OUT rank] integer
\end{description}

\mpifunc{MPI\_GSIZE(group, size)} 
Return the number of processes that belong to the specified group.
\begin{description}
\item[IN group] group handle
\item[OUT size] integer
\end{description}

\section{Communication Functions}

The proposed communication functions are divided into two layers.
The lowest level uses the same buffer descriptor objects
available in point-to-point to create noncontiguous, multiple data type
messages. The second level is similar to the block send/receive
point-to-point operations in that it supports only contiguous buffers of data.
For each communication operation, we list these two level of calls together.

\section{Synchronization}

\subsubsection*{Barrier synchronization}

\mpifunc{MPI\_BARRIER( group )} 

MPI\_BARRIER blocks the calling process until all group members have called
it; the call returns at any process only after all group members have
entered the call.
\begin{description}
\item[IN group] group handle
\end{description}

{\tt MPI\_BARRIER( group )}
is
\begin{verbatim}
MPI_CREATE_BUFFER(buffer_handle, MPI_BUFFER, MPI_PERSISTENT);
MPI_GSIZE( group, &size );
MPI_RANK( group, &rank );
if (rank==0)
{
   for (i=1; i < size; i++)
      MPI_RECV(buffer_handle, i, tag, group, return_handle);
   for (i=1; i < size; i++)
      MPI_SEND(buffer_handle, i, tag, group);
}
else
{
   MPI_SEND(buffer_handle, 0, tag, group);
   MPI_RECV(buffer_handle, 0, tag, group, return_handle);
}
MPI_FREE(buffer_handle);
\end{verbatim}

\discuss{ since tag was voted out in the last meeting, a "safe" tag
must be selected to use in the above description }

\section{Data move functions}

\subsubsection*{Broadcast}

\mpifunc{ MPI\_BCAST( buffer\_handle, group, root )} 

{\tt MPI\_BCAST} broadcasts a message from the process with rank {\tt root} to
all other processes
of the group. It is called by all members of group using the same arguments for
{\tt  group, and root}.
On return the contents of the buffer of the process with rank {\tt root}
is contained in buffer of all group members.
\begin{description}
\item[INOUT buffer\_handle]  Handle for buffer where from message is
sent or received.
\item[IN group] group handle
\item[IN root] rank of broadcast root (integer)
\end{description}

\mpifunc{ MPI\_BCASTC( buf, len, group, root )} 

{\tt MPI\_BCASTC} behaves like broadcast, restricted to a block buffer.
It is called by all processes with the same arguments for {\tt len, group}
and {\tt root}.
\begin{description}
\item[INOUT buffer]  Starting address of buffer (choice type)
\item[IN len] Number of words in buffer (integer)
\item[IN group] group handle
\item[in root] rank of broadcast root (integer)
\end{description}

{\tt  MPI\_BCAST( buffer\_handle, group, root )} 
is
\begin{verbatim}
MPI_GSIZE( group, &size );
MPI_RANK( group, &rank );
MPI_IRECV(handle, buffer_handle, root, tag, group, return_handle);
if (rank==root)
   for (i=0; i < size; i++)
      MPI_SEND(buffer_handle, i, tag, group);
MPI_WAIT(handle)
\end{verbatim}

\subsubsection*{Circular shift}

\mpifunc{MPI\_CSHIFT( inbuf, outbuf, group, shift)} 

Process with rank {\tt i} sends the data in its input buffer to
process with rank $\tt (i+ shift) \bmod  group\_size$, who receives the
data in its output buffer. All processes make the call with the same values for
{\tt group}, and {\tt shift}.  The {\tt shift} value can be positive, zero,
or negative.

\begin{description}
\item[IN inbuf] handle to input buffer descriptor
\item[OUT outbuf] handle to output buffer descriptor
\item[IN group] handle to group
\item[IN shift] integer
\end{description}

\mpifunc{MPI\_CSHIFT1( buf, group, shift)} 

Process with rank {\tt i} sends the data in its buffer to
process with rank $\tt (i+ shift) \bmod  group\_size$, who receives the
data in the same buffer. All processes make the call with the same values for
{\tt group}, and {\tt shift}.  The {\tt shift} value can be positive, zero,
or negative.

\begin{description}
\item[INOUT buf] handle to buffer descriptor
\item[IN group] handle to group
\item[IN shift] integer
\end{description}

\mpifunc{MPI\_CSHIFTC( inbuf, outbuf, len, group, shift)} 

Behaves like {\tt MPI\_CSHIFT}, with buffers restricted to be blocks of
numeric units.
All processes make the call with the same values for
{\tt len, group}, and {\tt shift}.
\begin{description}
\item[IN inbuf] initial location of input buffer
\item[OUT outbuf] initial location of output buffer
\item[IN len] number of entries in input (and output) buffers
\item[IN group] handle to group
\item[IN shift] integer
\end{description}

\mpifunc{MPI\_CSHIFTC1( buf, len, group, shift)} 

Behaves like {\tt MPI\_CSHIFT1}, with buffers restricted to be blocks of
numeric units.
All processes make the call with the same values for
{\tt len, group}, and {\tt shift}.
\begin{description}
\item[INOUT buf] initial location of buffer
\item[IN len] number of entries in input (and output) buffers
\item[IN group] handle to group
\item[IN shift] integer
\end{description}

{\tt MPI\_CSHIFT( inbuf, outbuf, group, shift)} 
is
\begin{verbatim}
MPI_GSIZE( group, &size );
MPI_RANK( group, &rank );
MPI_ISEND( handle, inbuf, mod(rank+shift, size), tag, group);
MPI_RECV( outbuf, mod(rank-shift,size), tag, group, return_handle)
MPI_WAIT(handle);
\end{verbatim}

\subsubsection*{End-off shift}

\mpifunc{MPI\_EOSHIFT( inbuf, outbuf, group, shift)} 

Process with rank {\tt i}, $\tt \max( 0, -shift) \le i < min( size, size -
shift)$, sends the data
in its input buffer to process with rank {\tt i+ shift}, who receives the data
in its output buffer.   The output buffer of processes which do not receive
data is left unchanged.   All processes
make the call with the same values for {\tt group}, and {\tt shift}.

\begin{description}
\item[IN inbuf] handle to input buffer descriptor
\item[OUT outbuf] handle to output buffer descriptor
\item[IN group] handle to group
\item[IN shift] integer
\end{description}

\mpifunc{MPI\_EOSHIFT1( buf, group, shift)} 

Process with rank {\tt i}, $\tt \max( 0, -shift) \le i < min( size, size -
shift)$, sends the data
in its buffer to process with rank {\tt i+ shift}, who receives the data
in the same buffer.   The output buffer of processes which do not receive
data is left unchanged.   All processes
make the call with the same values for {\tt group}, and {\tt shift}.

\begin{description}
\item[IN inbuf] handle to input buffer descriptor
\item[OUT outbuf] handle to output buffer descriptor
\item[IN group] handle to group
\item[IN shift] integer
\end{description}

\mpifunc{MPI\_EOSHIFTC( inbuf, outbuf, len, group, shift)} 

Behaves like {\tt MPI\_EOSHIFT}, with buffers restricted to be blocks of
numeric units.
All processes make the call with the same values for
{\tt len, group}, and {\tt shift}.
\begin{description}
\item[IN inbuf] initial location of input buffer
\item[OUT outbuf] initial location of output buffer
\item[IN len] number of entries in input (and output) buffers
\item[IN group] handle to group
\item[IN shift] integer
\end{description}

\mpifunc{MPI\_EOSHIFTC1( buf, len, group, shift)} 

Behaves like {\tt MPI\_EOSHIFT1}, with buffer restricted to be blocks of
numeric units.
All processes make the call with the same values for
{\tt len, group}, and {\tt shift}.
\begin{description}
\item[INOUT buf] initial location of buffer
\item[IN len] number of entries in input (and output) buffers
\item[IN group] handle to group
\item[IN shift] integer
\end{description}

\subsubsection*{Gather}

\mpifunc{MPI\_GATHER( inbuf, outbuf, group, root, return\_status) } 

Each process (including the root process) sends the content of its input
buffer to the root process.  The root process concatenates all the
incoming messages in the order of the senders' rank and places the
results in its output buffer.
It is called by all members of group using the same arguments for
{\tt group}, and {\tt root}.   The input buffer of each process may have
a different length.
\begin{description}
\item[IN inbuf] handle to input buffer descriptor
\item[OUT outbuf] handle to output buffer descriptor -- significant only at root
(choice)
\item[IN group] group handle
\item[IN root] rank of receiving process (integer)
\item[OUT return\_status] return status handle
\end{description}

\mpifunc{MPI\_GATHERC( inbuf, inlen, outbuf, group, root) } 

{\tt MPI\_GATHERC} behaves like {\tt MPI\_GATHER} restricted to block
buffers, and with the additional restriction that all input buffers should
have the same length.   All processes should provided the same values for
{\tt inlen, group}, and {\tt root} .
\begin{description}
\item[IN inbuf] first variable of input buffer (choice)
\item[IN inlen] Number of (word) variables in input buffer (integer)
\item[OUT outbuf] first variable of output buffer -- significant only at
root (choice)
\item[IN group] group handle
\item[IN root] rank of receiving process (integer)
\end{description}

{\tt MPI\_GATHERC( inbuf, inlen, outbuf, tag, group, root) } 
is
\begin{verbatim}
MPI_GSIZE( &size, group);
MPI_RANK( &rank, group);
MPI_ISENDC(handle, inbuf, inlen, root, tag, group);
if (rank==root)
   for (i=0; i < size; i++)
   {
      MPI_RECVC(outbuf, inlen, i, tag, group, return\_status);
      outbuf += inlen;
   }
MPI_WAIT(handle);
\end{verbatim}

\subsubsection*{Scatter}

\mpifunc{MPI\_SCATTER( list\_of\_inbufs, outbuf, group, root, return\_status)} 

The root process sends the content of its {\tt i}-th input buffer
to the process with rank {\tt i}; each process (including the root process)
stores the incoming message in its output buffer.
The routine is called by all members of the group using the same
arguments for {\tt group}, and {\tt root}.
\begin{description}
\item[IN list\_of\_inbufs] list of buffer descriptor handles
\item[OUT outbuf] buffer descriptor handle
\item[IN group] handle
\item[IN root]  rank of sending process (integer)
\item[OUT return\_status] return status handle
\end{description}

{\tt MPI\_SCATTER( list\_of\_inbufs, outbuf, group, root, return\_status)} 
is
\begin{verbatim}
MPI_GSIZE( group, &size );
MPI_RANK( group, &rank );
MPI_IRECV(handle, outbuf, root, tag, group);
if (rank=root)
   for (i=0; i < size; i++)
      MPI_SEND(inbuf[i], i, tag, group);
MPI_WAIT(handle, return\_status);
\end{verbatim}

\mpifunc{MPI\_SCATTERC( inbuf, outbuf, len, group, root)}

{\tt MPI\_SCATTERC} behaves like {\tt MPI\_SCATTER} restricted to block buffers,
and with the additional restriction that all output buffers have the same
length. The input buffer block of the root process is partitioned into
{\tt n} consecutive blocks,
each consisting of {\tt len} words.  The {\tt i}-th block is sent to the
{\tt i}-th process in the group and stored in its output buffer.
The routine is called by all members of the group using the same
arguments for {\tt group, len}, and {\tt root}.
\begin{description}
\item[IN inbuf] first entry in input buffer -- significant only at root
(choice).
\item[OUT outbuf] first entry in output buffer (choice).
\item[IN len]  number of entries to be stored in output buffer (integer)
\item[IN group] handle
\item[IN root]  rank of sending process (integer)
\end{description}

{\tt MPI\_SCATTERC( inbuf, outbuf, outlen, group, root) } 
is
\begin{verbatim}
MPI_GSIZE( &size, group);
MPI_RANK( &rank, group);
MPI_IRECVC( handle, outbuf, outlen, root, tag, group);
if (rank=root)
   for (i=0; i < size; i++)
   {
      MPI_SENDC(inbuf, outlen, i, tag, group, return\_status);
      inbuf += outlen;
   }
MPI_WAIT(handle);
\end{verbatim}

\subsubsection*{All-to-all scatter}

\mpifunc{MPI\_ALLSCATTER( list\_of\_inbufs, outbuf, group, return\_status)} 

Each process in the group sends its {\tt i}-th buffer in its input buffer list
to the process with rank {\tt i} (itself included); each process concatenates
the incoming messages in its output buffer, in the order of the senders' ranks.
The routine is called by all members of the group using the same
arguments for {\tt group}.
\begin{description}
\item[IN list\_of\_inbufs] list of buffer descriptor handles
\item[OUT outbuf] buffer descriptor handle
\item[IN group] handle
\item[OUT return\_status] return status handle
\end{description}

\mpifunc{MPI\_ALLSCATTERC( inbuf, outbuf, len, group)} 

{\tt MPI\_ALLSCATTERC} behaves like {\tt MPI\_ALLSCATTER} restricted to
block buffers,
and with the additional restriction that all blocks sent from one process
to another have
the same length. The input buffer block of each process is partitioned
into {\tt n} consecutive blocks,
each consisting of {\tt len} words.  The {\tt i}-th block is sent to the
{\tt it}-th process in the group.  Each process concatenates the incoming
messages, in the order of the senders' ranks, and store them in its output
buffer. The routine is called by all members of the group using the same
arguments for {\tt group}, and {\tt len}.
\begin{description}
\item[IN inbuf] first entry in input buffer (choice).
root (integer)
\item[OUT outbuf] first entry in output buffer (choice).
\item[IN len]  number of entries sent from each process to each other (integer).
\item[IN group] handle
\end{description}

{\tt MPI\_ALLSCATTERC( inbuf, outbuf, len, group)}  
is
\begin{verbatim}
MPI_GSIZE( group, &size );
MPI_RANK( group, &rank );
for (i=0; i < rank; i++)
   {
    MPI_IRECVC(recv_handles[i], outbuf, len, tag, group);
    outbuf += len;
   }
for (i=0; i < size; i++)
   {
    MPI_ISENDC(send_handle[i], inbuf, len, i, tag, group);
    inbuf += len;
   }
MPI_WAITALL(send_handle);
MPI_WAITALL(recv_handle);
\end{verbatim}

\subsubsection*{All-to-all broadcast}

\mpifunc{MPI\_ALLCAST( inbuf, outbuf, group, return\_status)} 

Each process in the group broadcasts its input buffer
to all processes (including itself);
each process concatenates
the incoming messages in its output buffer, in the order of the senders' ranks.
The routine is called by all members of the group using the same
arguments for {\tt group}.
\begin{description}
\item[IN inbuf] buffer descriptor handle for input buffer
\item[OUT outbuf] buffer descriptor handle for output buffer
\item[IN group] handle
\item[OUT return\_status] return status handle
\end{description}

\mpifunc{MPI\_ALLCASTC( inbuf, outbuf, len, group)} 

{\tt MPI\_ALLCASTC} behaves like {\tt MPI\_ALLCAST} restricted to
block buffers,
and with the additional restriction that all blocks sent from one process
to another have the same length.
The routine is called by all members of the group using the same
arguments for {\tt group}, and {\tt len}.
\begin{description}
\item[IN inbuf] first entry in input buffer (choice).
root (integer)
\item[OUT outbuf] first entry in output buffer (choice).
\item[IN len]  number of entries sent from each process to each other
(including itself).
\item[IN group] group handle
\end{description}

{\tt MPI\_ALLCASTC( inbuf, outbuf, len, group)}  
is
\begin{verbatim}
MPI_GSIZE( group, &size );
MPI_RANK( group, &rank );
for (i=0; i < rank; i++)
   {
    MPI_IRECVC(recv_handles[i], outbuf, len, tag, group);
    outbuf += len;
   }
for (i=0; i < size; i++)
   {
    MPI_ISENDC(send_handle[i], inbuf, len, i, tag, group);
   }
MPI_WAITALL(send_handle);
MPI_WAITALL(recv_handle);
\end{verbatim}

\section{Global Compute Operations}

\subsubsection*{Reduce}

\mpifunc{MPI\_REDUCE( inbuf, outbuf, group, root, op)} 

Combines the values provided in the input buffer of each process in the
group, using the operation {\tt op}, and returns the combined value in
the output buffer of the process with rank {\tt root}.
Each process can provide one value, or a sequence of values, in which case the
combine operation is executed pointwise on each entry of the sequence.
For example, if the operation is {\tt max} and input buffers contains two
floating point numbers, then outbuf(1) $=$ global max(inbuf(1)) and
outbuf(2) $=$ global max(inbuf(2)). All input
buffers should define sequences of equal length of entries of types
that match the type of the operands of {\tt op}.  The
output buffer should define a sequence of the same length of entries of
types that match the type of the result of {\tt op}.
(Note that,
here as for all other communication operations, the type of entries inserted in
a message depend on the information provided by the input buffer descriptor, and
not on the declarations of these variables in the calling program.   The types
of the variables in the calling program need not match the types defined by the
buffer descriptor, but in such case the outcome of a reduce operation may be
implementation dependent.)

The operation
defined by {\tt op} is associative and commutative, and the implementation can
take advantage of associativity and commutativity in order to change
order of evaluation.
The routine is called by all group members using the same arguments
for {\tt group, root} and {\tt op}.
\begin{description}
\item[IN inbuf] handle to input buffer
\item[OUT outbuf] handle to output buffer -- significant only at root
\item[IN group] handle to group
\item[IN root] rank of root process (integer)
\item[IN op] operation (status)
\end{description}

We list below the operations which are supported for Fortran, each with the
corresponding value of the {\tt op} parameter.
\begin{description}
\item[MPI\_IMAX] integer maximum
\item[MPI\_RMAX] real maximum
\item[MPI\_DMAX] double precision real maximum
\item[MPI\_IMIN] integer minimum
\item[MPI\_RMIN] real minimum
\item[MPI\_DMIN] double precision real minimum
\item[MPI\_ISUM] integer sum
\item[MPI\_RSUM] real sum
\item[MPI\_DSUM] double precision real sum
\item[MPI\_CSUM] complex sum
\item[MPI\_DCSUM] double precision complex sum
\item[MPI\_IPROD] integer product
\item[MPI\_RPROD] real product
\item[MPI\_DPROD] double precision real product
\item[MPI\_CPROD] complex product
\item[MPI\_DCPROD] double precision complex product
\item[MPI\_AND] logical and
\item[MPI\_IAND] integer (bit-wise) and
\item[MPI\_OR] logical or
\item[MPI\_IOR] integer (bit-wise) or
\item[MPI\_XOR] logical xor
\item[MPI\_IXOR] integer (bit-wise) xor
\item[MPI\_MAXLOC] rank of process with maximum integer value
\item[MPI\_MAXRLOC] rank of process with maximum real value
\item[MPI\_MAXDLOC] rank of process with maximum double precision real value
\item[MPI\_MINLOC] rank of process with minimum integer value
\item[MPI\_MINRLOC] rank of process with minimum real value
\item[MPI\_MINDLOC] rank of process with minimum double precision real value
\end{description}

\mpifunc{MPI\_REDUCEC( inbuf, outbuf, len, group, root, op)} 

Is same as {\tt MPI\_REDUCE}, restricted to a block buffer.
\begin{description}
\item[IN inbuf] first location in input buffer
\item[OUT outbuf] first location in output buffer -- significant only at root
\item[IN len] number of entries in input and output buffer (integer)
\item[IN group] handle to group
\item[IN root] rank of root process (integer)
\item[IN op] operation (status)
\end{description}

\mpifunc{MPI\_USER\_REDUCE( inbuf, outbuf, group, root, function)} 

Same as the reduce operation function above except that a user
supplied function is used.  {\tt function} is an associative and commutative
function with two arguments.  The types of the two arguments and of the
returned value of the function, and the types of all entries in the
input and output buffers all agree.  The output buffer has the same
length as the input buffer.
\begin{description}
\item[IN inbuf] handle to input buffer
\item[OUT outbuf] handle to output buffer -- significant only at root
\item[IN group] handle to group
\item[IN root] rank of root process (integer)
\item[IN function] user provided function
\end{description}

\mpifunc{MPI\_USER\_REDUCEC( inbuf, outbuf, len, group, root, function)}

Is same as {\tt MPI\_\_USER\_REDUCE}, restricted to a block buffer.
\begin{description}
\item[IN inbuf] first location in input buffer
\item[OUT outbuf] first location in output buffer -- significant only at root
\item[IN len] number of entries in input and output buffer (integer)
\item[IN group] handle to group
\item[IN root] rank of root process (integer)
\item[IN op] operation (status)
\end{description}

\discuss{

Do we also want a version of reduce that broadcasts the result to all processes
in the group?  (This can be achieved by a reduce followed by a broadcast, but a
combined function may be somewhat more efficient.)
These would be respectively:

\mpifunc{MPI\_GOP( inbuf, outbuf, group, op)}

\mpifunc{MPI\_GOPC( inbuf, outbuf, len, group, op)}

\mpifunc{MPI\_USER\_GOP( inbuf, outbuf, group, function)}

\mpifunc{MPI\_USER\_GOPC( inbuf, outbuf, len, group, function)}

Do we want a user provided {\em function} (two IN parameters, one OUT
value), or a user provided procedure that overwrites the second input
(ie. one IN param, one INOUT param, the equivalent of C {\tt a op= b}
type assignment)?  The second choice may allow a
more efficient implementation, without changing the semantics of the
MPI call.

}

\subsubsection*{Scan}

\mpifunc{ MPI\_SCAN( inbuf, outbuf, group, op )} 

MPI\_SCAN is used to perform a parallel prefix with respect to
an associative reduction operation on data distributed across the group.
The operation returns in the output buffer of the process with rank {\tt i} the
reduction of the values in the input buffers of processes with ranks {\tt
0,...,i}.  The type of operations supported and their semantic, and the
constraints on input and output buffers are as for {\tt MPI\_REDUCE}.
\begin{description}
\item[IN inbuf] handle to input buffer
\item[OUT outbuf] handle to output buffer
\item[IN group] handle to group
\item[IN op] operation (status)
\end{description}

\mpifunc{ MPI\_SCANC( inbuf, outbuf, len, group, op )} 
Same as {\tt MPI\_SCAN}, restricted to block buffers.

\begin{description}
\item[IN inbuf] first input buffer element (choice)
\item[OUT outbuf] first output buffer element (choice)
\item[IN len] number of entries in input and output buffer (integer)
\item[IN group] handle to group
\item[IN op] operation (status)
\end{description}

\mpifunc{ MPI\_USER\_SCAN( inbuf, outbuf, group, function )} 

Same as the scan operation function above except that a user
supplied function is used.  {\tt function} is an associative and commutative
function with two arguments.  The types of the two arguments and of the
returned values all agree.
\begin{description}
\item[IN inbuf] handle to input buffer
\item[OUT outbuf] handle to output buffer
\item[IN group] handle to group
\item[IN function] user provided function
\end{description}

\mpifunc{MPI\_USER\_SCANC( inbuf, outbuf, len, group, function)}

Is same as {\tt MPI\_USER\_SCAN}, restricted to a block buffer.
\begin{description}
\item[IN inbuf] first location in input buffer
\item[OUT outbuf] first location in output buffer
\item[IN len] number of entries in input and output buffer (integer)
\item[IN group] handle to group
\item[IN function] user provided function
\end{description}

\discuss{

Do we want scan operations executed by segments? (The HPF definition of prefix
and suffix operation might be handy -- in addition to the scanned vector of
values there is a mask that tells where segments start and end.)
}

\section{Correctness}

\discuss{ This is still very preliminary}

The semantics of the collective communication operations can be derived from
their operational definition in terms of  point-to-point communication.  It is
assumed that messages pertaining to one
operation cannot be confused with messages pertaining to another operation.
Also messages pertaining to two distinct occurrences of the same operation
cannot be confused, if the two occurrences have distinct parameters.
The relevant parameters for this purpose are {\tt group}, {\tt root} 
and {\tt op}.
messages pertaining to another occurrence of the same operation, with different
parameters.   The implementer can, of course, use another, more efficient
implementation, as long as it has the same effect.

\discuss{

This statement does not yet apply to the current, incomplete and
somewhat careless definitions I provided in this draft.

The definition above means that messages pertaining to a collective
communication carry information identifying the operation itself, and the
values of the {\tt group} and,
where relevant, {\tt root} or {\tt op} parameters.
Is this acceptable?

}

A few examples:

\begin{verbatim}
MPI_BCAST(buf, len, group, 0);
MPI_BCAST(buf, len, group, 1);
\end{verbatim}

Two consecutive broadcasts, in the same group, with the same tag, but different
roots.  Since the operations are distinguishable, messages from one broadcast
cannot be confused with messages from the other broadcast; the program is safe
and will execute as expected.

\begin{verbatim}
MPI_BCAST(buf, len, group, 0);
MPI_BCAST(buf, len, group, 0);
\end{verbatim}

Two consecutive broadcasts, in the same group, with the same tag and root.
Since point-to-point communication preserves the order of messages
here, too, messages from one broadcast will not be confused with messages from
the other broadcast; the program is safe and will execute as intended.

\begin{verbatim}
MPI_RANK(&rank, group)
if (rank==0)
  {
   MPI_BCASTC(buf, len, group, 0);
   MPI_SENDC(buf, len, 2, tag, group);
  }
elseif (rank==1)
  {
   MPI_RECVC(buf, len, MPI_DONTCARE, tag, group);
   MPI_BCASTC(buf, len, group, 0);
   MPI_RECVC(buf, len, MPI_DONTCARE, tag, group);
  }
else
  {
   MPI_SENDC(buf, len, 2, tag, group);
   MPI_BCASTC(buf, len, group, 0);
  }
\end{verbatim}

Process zero executes a broadcast followed by a send to process one;
process two executes a send to process one, followed by a broadcast;
and process one executes a receive, a broadcast and a receive.
A possible outcome is for the operations to be matched as illustrated by the
diagram below.

\begin{verbatim}

    0                       1                      2

                / - >  receive            / - send
              /                         /
broadcast   /         broadcast       /   broadcast
           /                        /
  send   -             receive  < -

\end{verbatim}

The reason is that broadcast is not a synchronous operation; the call at a
process may return before the other processes have entered the broadcast.
Thus, the message sent by process zero can arrive to process one before the
message sent by process two, and before the call to broadcast on process one.

\end{document}