<html><head><meta name="color-scheme" content="light dark"></head><body><pre style="word-wrap: break-word; white-space: pre-wrap;">\chapter{Collective Communication}
\label{sec:coll}
\label{chap:coll}
%Version of 4/27/95

\section{Introduction and Overview}

Collective communication is defined as communication that involves
a group of processes.
The functions of this type provided by \MPI/ are the following:
\begin{itemize}
\item
Barrier synchronization across all group members (Sec. \ref{sec:coll-barrier}).
\item
Broadcast from one member to all members of a group
(Sec. \ref{sec:coll-broadcast}). This is shown in
figure \ref{fig:collcom}.
\item
Gather data from all group members to one member
(Sec. \ref{sec:coll-gather}). This is shown in
figure \ref{fig:collcom}.
\item
Scatter data from one member to all members of a group
(Sec. \ref{sec:coll-scatter}). This is shown in
figure \ref{fig:collcom}.
\item
A variation on Gather where all members of the group receive the result
(Sec. \ref {sec:coll-allcast}). This is shown as ``allgather'' in
figure \ref{fig:collcom}.
\item
Scatter/Gather data from all members to all members of a group
(also called complete exchange or all-to-all) (Sec. \ref{sec:coll-alltoall}).
This is shown as ``alltoall'' in figure \ref{fig:collcom}.
\item
Global reduction operations such as sum, max, min, or user-defined functions,
where the result
is returned to all group members and a variation where the result is
returned to only one member (Sec. \ref{global-reduce}).
\item
A combined reduction and scatter operation (Sec. \ref{sec:coll-reduce-scatter}).
\item
Scan across all members of a group (also called prefix)
(Sec. \ref{sec:coll-scan}).
\end{itemize}

\begin{figure}
\vbox to8truein{
\vfil
\special{psfile=coll-fig1.ps}}
\caption{Collective move functions illustrated
for a group of six processes. In each case, each row of boxes
represents data locations in one process. Thus, in the broadcast,
initially just the first process contains the data $A_0$, but after the
broadcast all processes contain it.}
\label{fig:collcom}
\end{figure}

A collective operation is executed by having all processes in the group
call the communication routine, with matching arguments.
The syntax and semantics of the collective operations are
defined to be consistent with the syntax and semantics of the
point-to-point operations. Thus, general datatypes are allowed
and must match between sending and receiving processes as specified
in Chapter ~\ref{chap:pt2pt}.
One of the key arguments is a communicator that defines the group
of participating processes and provides a context for the operation.
Several collective routines such as broadcast and gather have
a single originating or receiving process. Such processes
are called the {\em root}.
Some arguments in the collective functions are specified as
``significant only at root,'' and are ignored for all
participants except the root.
The reader is referred to Chapter \ref{chap:pt2pt}
for information concerning communication buffers,
general datatypes and type matching rules, and to
Chapter \ref{chap:context} for information on how to define groups and
create communicators.

The type-matching conditions for the collective operations are more
strict than the corresponding conditions between sender and receiver
in point-to-point.  Namely, for collective operations,
the amount of data sent must exactly
match the amount of data specified by the receiver.
Distinct type maps (the layout in memory, see Sec. \ref{sec:pt2pt-datatype})
between sender and receiver are still allowed.

Collective routine calls 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 locations in the
communication buffer.  It does not indicate that other processes in
the group have completed or even
started the operation (unless otherwise indicated in the
description of the operation).
Thus, a collective communication call may, or
may not, have the effect of synchronizing all calling processes.
This statement excludes, of course, the barrier function.

Collective communication calls may use the same
communicators as point-to-point communication; \MPI/ guarantees that
messages generated on behalf of collective communication calls will not
be confused with messages generated by point-to-point communication.
A more detailed discussion of correct use of collective
routines is found in Sec. \ref {coll:correct}.

\begin{rationale}
The equal-data restriction (on type matching) was made so
as to avoid the complexity
of providing a facility analogous to the status
argument of \func{MPI\_RECV} for discovering the amount of data sent.
Some of the collective routines would require an array of status values.

The statements about synchronization are made so as to allow a variety
of implementations of the collective functions.

The collective operations do not accept a message tag argument.
If future revisions of \MPI/ define non-blocking collective functions,
then tags (or a similar mechanism) will need to be added so as
to allow the dis-ambiguation of multiple, pending, collective operations.
\end{rationale}

\begin{users}
It is dangerous to rely on synchronization
side-effects of the collective operations for program correctness.
For example, even though a particular implementation may
provide a broadcast routine
with a side-effect of synchronization, the standard does not require
this, and a program that relies on this will not be portable.

On the other hand, a correct, portable program must allow for the fact
that a collective call {\em may} be synchronizing.  Though one cannot
rely on any synchronization side-effect, one must program so as to allow
it.  These issues are discussed further in Sec. \ref{coll:correct}.
\end{users}

\begin{implementors}
While vendors may write optimized collective routines matched to
their architectures, a complete library of the collective communication
routines can be written entirely using the \MPI/ point-to-point communication
functions and a few auxiliary functions.  If implementing on top of
point-to-point, a hidden, special communicator must be created for the
collective operation so as to avoid interference with any on-going
point-to-point communication at the time of the collective call.  This
is discussed further in Sec. \ref{coll:correct}.
\end{implementors}

\section{Communicator argument}

The key concept of the collective functions is to have a ``group''
of participating processes. The routines do not have a group identifier
as an explicit argument. Instead, there is a communicator argument.
For the purposes of this chapter, a communicator can be thought
of as a group identifier
linked with a context. An inter-communicator, that is, a communicator
that spans two groups, is {\em not} allowed as an argument
to a collective function.

\section{Barrier synchronization}
\label{sec:coll-barrier}

\begin{funcdef}{MPI\_BARRIER( comm )}
\funcarg{\IN}{comm}{communicator (handle)}
\end{funcdef}

\mpibind{MPI\_Barrier(MPI\_Comm~comm )}

\mpifbind{MPI\_BARRIER(COMM, IERROR) \fargs INTEGER COMM, IERROR}


\func{MPI\_BARRIER} blocks the caller until all group members have called
it. The call returns at any process only after all group members have
entered the call.

\section{Broadcast}
\label{sec:coll-broadcast}

\begin{funcdef}{ MPI\_BCAST( buffer, count, datatype, root, comm )}
\funcarg{\INOUT}{ buffer}{starting address of buffer (choice)}
\funcarg{\IN}{ count}{ number of entries in buffer (integer)}
\funcarg{\IN}{ datatype}{ data type of buffer (handle)}
\funcarg{\IN}{ root}{ rank of broadcast root (integer)}
\funcarg{\IN}{ comm}{ communicator (handle)}
\end{funcdef}

\mpibind{MPI\_Bcast(void*~buffer, int~count, MPI\_Datatype~datatype, int~root, MPI\_Comm~comm )}

\mpifbind{ MPI\_BCAST(BUFFER, COUNT, DATATYPE, ROOT, COMM, IERROR) \fargs &lt;type&gt;  BUFFER(*) \\ INTEGER COUNT, DATATYPE, ROOT, COMM, IERROR}


\func{MPI\_BCAST} broadcasts a message from
the process with rank \mpiarg{root} to all processes
of the group, itself included.
It is called by all members of group using the same arguments for
\mpiarg{comm, root}.
On return, the contents of \mpiarg{root}'s communication buffer
has been copied to all processes.

General, derived datatypes are allowed for \mpiarg{datatype}.
The type signature of \mpiarg{count, datatype} on any process must
be equal to the type signature of \mpiarg{count, datatype} at the root.
This implies that the amount of data sent must be equal to the amount received,
pairwise between each process and the root.
\func{MPI\_BCAST} and all other data-movement collective routines
make this restriction.
Distinct type maps between sender and receiver are still allowed.

\subsection{Example using \func{MPI\_BCAST}}

\begin{example} {\rm
\label{coll-exZ}

Broadcast 100 ints from process {\tt 0} to every process in the group.

\begin{verbatim}
    MPI_Comm comm;
    int array[100];
    int root=0;
    ...
    MPI_Bcast( array, 100, MPI_INT, root, comm);
\end{verbatim}
As in many of our example code fragments, we assume that some
of the variables (such as {\tt comm} in the above) have been assigned
appropriate values.
} \end{example}

\section{Gather}
\label{sec:coll-gather}

\begin{funcdef}{MPI\_GATHER( sendbuf, sendcount, sendtype, recvbuf,
recvcount, recvtype, root, comm) }
\funcarg{\IN}{ sendbuf}{ starting address of send buffer (choice)}
\funcarg{\IN}{ sendcount}{ number of elements in send buffer (integer)}
\funcarg{\IN}{ sendtype}{ data type of send buffer elements (handle)}
\funcarg{\OUT}{ recvbuf}{ address of receive buffer (choice,
significant only at root)}
\funcarg{\IN}{ recvcount}{ number of elements for any single receive (integer,
significant only at root)}
\funcarg{\IN}{ recvtype}{ data type of recv buffer elements
(significant only at root) (handle)}
\funcarg{\IN}{ root}{ rank of receiving process (integer)}
\funcarg{\IN}{ comm}{ communicator (handle)}
\end{funcdef}

\mpibind{MPI\_Gather(void*~sendbuf, int~sendcount, MPI\_Datatype~sendtype, void*~recvbuf, int~recvcount, MPI\_Datatype~recvtype, int~root, MPI\_Comm~comm) }

\mpifbind{MPI\_GATHER(SENDBUF, SENDCOUNT, SENDTYPE, RECVBUF, RECVCOUNT, RECVTYPE, ROOT, COMM, IERROR) \fargs &lt;type&gt; SENDBUF(*), RECVBUF(*) \\ INTEGER SENDCOUNT, SENDTYPE, RECVCOUNT, RECVTYPE, ROOT, COMM, IERROR}


Each process (root process included) sends the contents of its send
buffer to the root process.  The root process receives the messages and
stores them in rank order.
The outcome is {\em as if} each of the {\tt n} processes in the group
(including the root process) had executed a call to
\[\tt
MPI\_Send(sendbuf, sendcount, sendtype, root , ...),
\]
and the
root had executed {\tt n} calls to
\[\tt
MPI\_Recv(recvbuf+i\cdot recvcount\cdot extent(recvtype), recvcount, recvtype, i ,...),
\]
where {\tt extent(recvtype)} is the type extent obtained from a call to
{\tt MPI\_Type\_extent()}.

An alternative description is that the {\tt n} messages sent by the
processes in the group are concatenated in rank order, and the
resulting message is received by the root as if by a call to
\mpifunc{MPI\_RECV(recvbuf, recvcount$\cdot$n, recvtype, ...)}.

The receive buffer is ignored for all non-root processes.

General, derived datatypes are allowed for both \mpiarg{sendtype}
and \mpiarg{recvtype}.
The type signature of \mpiarg{sendcount, sendtype} on process {\tt i}
must be equal to the type signature of
\mpiarg{recvcount, recvtype} at the root.
This implies that the amount of data sent must be equal to the
amount of data received, pairwise between each process and the root.
Distinct type maps between sender and receiver are still allowed.

All arguments to the function are significant on process \mpiarg{root},
while on other processes, only arguments \mpiarg{sendbuf, sendcount,
sendtype, root, comm} are significant.
The arguments \mpiarg{root} and \mpiarg{comm}
must have identical values on all processes.

The specification of counts and types
should not cause any location on the root to be written more than
once.  Such a call is erroneous.


Note that the \mpiarg{recvcount} argument at the root indicates
the number of items it receives from {\em each} process, not the total number
of items it receives.

\begin{funcdef}{MPI\_GATHERV( sendbuf, sendcount, sendtype, recvbuf,
recvcounts, displs, recvtype, root, comm) }
\funcarg{\IN}{ sendbuf}{ starting address of send buffer (choice)}
\funcarg{\IN}{ sendcount}{ number of elements in send buffer (integer)}
\funcarg{\IN}{ sendtype}{ data type of send buffer elements (handle)}
\funcarg{\OUT}{ recvbuf}{ address of receive buffer (choice,
significant only at root)}
\funcarg{\IN}{ recvcounts}{ integer array (of length group size)
containing the number of elements that are received from each process
(significant only at root)}
\funcarg{\IN}{ displs}{ integer array (of length group size).  Entry
{\tt i} specifies the displacement relative to \mpiarg{recvbuf} at
which to place the incoming data from process {\tt i} (significant only
at root)}
\funcarg{\IN}{ recvtype}{ data type of recv buffer elements
(significant only at root) (handle)}
\funcarg{\IN}{ root}{ rank of receiving process (integer)}
\funcarg{\IN}{ comm}{ communicator (handle)}
\end{funcdef}

\mpibind{MPI\_Gatherv(void*~sendbuf, int~sendcount, MPI\_Datatype~sendtype, void*~recvbuf, int~*recvcounts, int~*displs, MPI\_Datatype~recvtype, int~root, MPI\_Comm~comm) }

\mpifbind{MPI\_GATHERV(SENDBUF, SENDCOUNT, SENDTYPE, RECVBUF, RECVCOUNTS, DISPLS, RECVTYPE, ROOT, COMM, IERROR) \fargs &lt;type&gt; SENDBUF(*), RECVBUF(*) \\ INTEGER SENDCOUNT, SENDTYPE, RECVCOUNTS(*), DISPLS(*), RECVTYPE, ROOT, COMM, IERROR}


\func{MPI\_GATHERV} extends the functionality of \func{MPI\_GATHER}
by allowing a varying count of data from each process, since
\mpiarg{recvcounts}
is now an array.  It also allows more flexibility as to where the data
is placed on the root, by providing the new argument, \mpiarg{displs}.

The outcome is {\em as if} each process, including the root process,
sends a message to the root,
\[\tt
MPI\_Send(sendbuf, sendcount, sendtype, root, ...),
\]
and the root executes {\tt n} receives,
\[\tt
MPI\_Recv(recvbuf+disp[i]\cdot extent(recvtype), recvcounts[i],
recvtype, i, ...).
\]

Messages are placed in the receive buffer of the root process
in rank order, that is, the data sent from process {\tt j} is
placed in the {\tt j}th portion of the receive buffer \mpiarg{recvbuf}
on process \mpiarg{root}.  The {\tt j}th portion of \mpiarg{recvbuf}
begins at offset \mpiarg{displs[j]} elements (in terms of
\mpiarg{recvtype}) into \mpiarg{recvbuf}.

The receive buffer is ignored for all non-root processes.

The type signature implied by \mpiarg{sendcount, sendtype} on process {\tt i}
must be equal to the type signature implied by \mpiarg{recvcounts[i], recvtype}
at the root.
This implies that the amount of data sent must be equal to the
amount of data received, pairwise between each process and the root.
Distinct type maps between sender and receiver are still allowed,
as illustrated in Example \ref{coll-exD}.

All arguments to the function are significant on process \mpiarg{root},
while on other processes, only arguments \mpiarg{sendbuf, sendcount,
sendtype, root, comm} are significant.
The arguments \mpiarg{root} and \mpiarg{comm}
must have identical values on all processes.

The specification of counts, types, and displacements
should not cause any location on the root to be written more than
once.  Such a call is erroneous.

\subsection{Examples using \func{MPI\_GATHER}, \func{MPI\_GATHERV}}

\begin{example} {\rm
\label{coll-exA}

Gather 100 ints from every process in group to root. See figure
\ref{fig-coll-exA}.

\begin{verbatim}
    MPI_Comm comm;
    int gsize,sendarray[100];
    int root, *rbuf;
    ...
    MPI_Comm_size( comm, &amp;gsize);
    rbuf = (int *)malloc(gsize*100*sizeof(int));
    MPI_Gather( sendarray, 100, MPI_INT, rbuf, 100, MPI_INT, root, comm);
\end{verbatim}
} \end{example}



\begin{example} {\rm
\label{coll-exAa}

Previous example modified -- only the root allocates memory for the
receive buffer.


\begin{verbatim}
    MPI_Comm comm;
    int gsize,sendarray[100];
    int root, myrank, *rbuf;
    ...
    MPI_Comm_rank( comm, myrank);
    if ( myrank == root) {
       MPI_Comm_size( comm, &amp;gsize);
       rbuf = (int *)malloc(gsize*100*sizeof(int));
       }
    MPI_Gather( sendarray, 100, MPI_INT, rbuf, 100, MPI_INT, root, comm);
\end{verbatim}
} \end{example}



\begin{figure}
\centerline{\hbox{
\psfig{figure=mycoll-fig2.ps,width=3.50in}}}
  \small
  \caption{The root process gathers 100 {\tt int}s from each process
  in the group.
  }
  \label{fig-coll-exA}
\end{figure}

\begin{example} {\rm
\label{coll-exB}

Do the same as the previous example, but use a derived datatype.  Note that
the type cannot be the entire set of {\tt gsize*100 int}s since type matching
is defined pairwise between the root and each process in the gather.

\begin{verbatim}
    MPI_Comm comm;
    int gsize,sendarray[100];
    int root, *rbuf;
    MPI_Datatype rtype;
    ...
    MPI_Comm_size( comm, &amp;gsize);
    MPI_Type_contiguous( 100, MPI_INT, &amp;rtype );
    MPI_Type_commit( &amp;rtype );
    rbuf = (int *)malloc(gsize*100*sizeof(int));
    MPI_Gather( sendarray, 100, MPI_INT, rbuf, 1, rtype, root, comm);
\end{verbatim}
} \end{example}

\begin{example} {\rm
\label{coll-exC}

Now have each process send 100 ints to root, but place each set (of 100)
{\em stride} ints apart at receiving end. Use \func{MPI\_GATHERV}
and the \mpiarg{displs}
argument to achieve this effect. Assume $stride \geq 100$.
See figure \ref{fig-coll-exC}.

\begin{verbatim}
    MPI_Comm comm;
    int gsize,sendarray[100];
    int root, *rbuf, stride;
    int *displs,i,*rcounts;

    ...

    MPI_Comm_size( comm, &amp;gsize);
    rbuf = (int *)malloc(gsize*stride*sizeof(int));
    displs = (int *)malloc(gsize*sizeof(int));
    rcounts = (int *)malloc(gsize*sizeof(int));
    for (i=0; i&lt;gsize; ++i) {
        displs[i] = i*stride;
        rcounts[i] = 100;
    }
    MPI_Gatherv( sendarray, 100, MPI_INT, rbuf, rcounts, displs, MPI_INT,
                                                               root, comm);
\end{verbatim}

Note that the program is erroneous if $stride &lt; 100$.
} \end{example}

\begin{figure}
\centerline{\hbox{
\psfig{figure=mycoll-fig3.ps,width=3.50in}}}
  \small
  \caption{The root process gathers 100 {\tt int}s from each process
  in the group, each set is placed {\tt stride} ints apart.
  }
  \label{fig-coll-exC}
\end{figure}

\begin{example} {\rm
\label{coll-exD}

Same as Example \ref{coll-exC} on the receiving side, but send the
100 ints from the 0th column of a
100$\times$150 int array, in C.  See figure \ref{fig-coll-exD}.

\begin{verbatim}
    MPI_Comm comm;
    int gsize,sendarray[100][150];
    int root, *rbuf, stride;
    MPI_Datatype stype;
    int *displs,i,*rcounts;

    ...

    MPI_Comm_size( comm, &amp;gsize);
    rbuf = (int *)malloc(gsize*stride*sizeof(int));
    displs = (int *)malloc(gsize*sizeof(int));
    rcounts = (int *)malloc(gsize*sizeof(int));
    for (i=0; i&lt;gsize; ++i) {
        displs[i] = i*stride;
        rcounts[i] = 100;
    }
    /* Create datatype for 1 column of array
     */
    MPI_Type_vector( 100, 1, 150, MPI_INT, &amp;stype);
    MPI_Type_commit( &amp;stype );
    MPI_Gatherv( sendarray, 1, stype, rbuf, rcounts, displs, MPI_INT,
                                                             root, comm);
\end{verbatim}
} \end{example}

\begin{figure}
\centerline{\hbox{
\psfig{figure=mycoll-fig4.ps,width=4.00in}}}
  \small
  \caption{The root process gathers column {\tt 0} of a 100$\times$150
  C array, and each set is placed {\tt stride} ints apart.
  }
  \label{fig-coll-exD}
\end{figure}

\begin{example} {\rm
\label{coll-exE}

Process i sends (100-i) ints from the ith column of a
100 $\times$ 150 int array, in C.  It is received into a buffer with stride,
as in the previous two examples. See figure \ref{fig-coll-exE}.

\begin{verbatim}
    MPI_Comm comm;
    int gsize,sendarray[100][150],*sptr;
    int root, *rbuf, stride, myrank;
    MPI_Datatype stype;
    int *displs,i,*rcounts;

    ...

    MPI_Comm_size( comm, &amp;gsize);
    MPI_Comm_rank( comm, &amp;myrank );
    rbuf = (int *)malloc(gsize*stride*sizeof(int));
    displs = (int *)malloc(gsize*sizeof(int));
    rcounts = (int *)malloc(gsize*sizeof(int));
    for (i=0; i&lt;gsize; ++i) {
        displs[i] = i*stride;
        rcounts[i] = 100-i;     /* note change from previous example */
    }
    /* Create datatype for the column we are sending
     */
    MPI_Type_vector( 100-myrank, 1, 150, MPI_INT, &amp;stype);
    MPI_Type_commit( &amp;stype );
    /* sptr is the address of start of "myrank" column
     */
    sptr = &amp;sendarray[0][myrank];
    MPI_Gatherv( sptr, 1, stype, rbuf, rcounts, displs, MPI_INT,
							root, comm);
\end{verbatim}

Note that a different amount of data is received from each process.
} \end{example}

\begin{figure}
\centerline{\hbox{
\psfig{figure=mycoll-fig5.ps,width=4.00in}}}
  \small
  \caption{The root process gathers {100-i} ints from
  column {\tt i} of a 100$\times$150
  C array, and each set is placed {\tt stride} ints apart.
  }
  \label{fig-coll-exE}
\end{figure}

\begin{example} {\rm
\label{coll-exF}

Same as Example \ref{coll-exE}, but done in a different way at the sending end.
We create a datatype that causes the correct striding at the
sending end so that that we read a column of a C array.
A similar thing was done in Example~\ref{pt2pt-exFF},
Section~\ref{subsec:pt2pt-examples}.

\begin{verbatim}
    MPI_Comm comm;
    int gsize,sendarray[100][150],*sptr;
    int root, *rbuf, stride, myrank, disp[2], blocklen[2];
    MPI_Datatype stype,type[2];
    int *displs,i,*rcounts;

    ...

    MPI_Comm_size( comm, &amp;gsize);
    MPI_Comm_rank( comm, &amp;myrank );
    rbuf = (int *)malloc(gsize*stride*sizeof(int));
    displs = (int *)malloc(gsize*sizeof(int));
    rcounts = (int *)malloc(gsize*sizeof(int));
    for (i=0; i&lt;gsize; ++i) {
        displs[i] = i*stride;
        rcounts[i] = 100-i;
    }
    /* Create datatype for one int, with extent of entire row
     */
    disp[0] = 0;       disp[1] = 150*sizeof(int);
    type[0] = MPI_INT; type[1] = MPI_UB;
    blocklen[0] = 1;   blocklen[1] = 1;
    MPI_Type_struct( 2, blocklen, disp, type, &amp;stype );
    MPI_Type_commit( &amp;stype );
    sptr = &amp;sendarray[0][myrank];
    MPI_Gatherv( sptr, 100-myrank, stype, rbuf, rcounts, displs, MPI_INT,
                                                               root, comm);
\end{verbatim}
} \end{example}

\begin{example} {\rm
\label{coll-exG}

Same as Example \ref{coll-exE} at sending side, but
at receiving side we make the
stride between received blocks vary from block to block.
See figure \ref{fig-coll-exG}.

\begin{verbatim}
    MPI_Comm comm;
    int gsize,sendarray[100][150],*sptr;
    int root, *rbuf, *stride, myrank, bufsize;
    MPI_Datatype stype;
    int *displs,i,*rcounts,offset;

    ...

    MPI_Comm_size( comm, &amp;gsize);
    MPI_Comm_rank( comm, &amp;myrank );

    stride = (int *)malloc(gsize*sizeof(int));
    ...
    /* stride[i] for i = 0 to gsize-1 is set somehow
     */

    /* set up displs and rcounts vectors first
     */
    displs = (int *)malloc(gsize*sizeof(int));
    rcounts = (int *)malloc(gsize*sizeof(int));
    offset = 0;
    for (i=0; i&lt;gsize; ++i) {
        displs[i] = offset;
        offset += stride[i];
        rcounts[i] = 100-i;
    }
    /* the required buffer size for rbuf is now easily obtained
     */
    bufsize = displs[gsize-1]+rcounts[gsize-1];
    rbuf = (int *)malloc(bufsize*sizeof(int));
    /* Create datatype for the column we are sending
     */
    MPI_Type_vector( 100-myrank, 1, 150, MPI_INT, &amp;stype);
    MPI_Type_commit( &amp;stype );
    sptr = &amp;sendarray[0][myrank];
    MPI_Gatherv( sptr, 1, stype, rbuf, rcounts, displs, MPI_INT,
                                                        root, comm);
\end{verbatim}
} \end{example}

\begin{figure}
\centerline{\hbox{
\psfig{figure=mycoll-fig6.ps,width=4.00in}}}
  \small
  \caption{The root process gathers {100-i} ints from
  column {\tt i} of a 100$\times$150
  C array, and each set is placed {\tt stride[i]} ints apart (a varying
stride).
  }
  \label{fig-coll-exG}
\end{figure}

\begin{example} {\rm
\label{coll-exH}

Process i sends {\tt num} ints from the ith column of a
100 $\times$ 150 int array, in C.  The complicating factor is that
the various values of {\tt num} are not known to {\tt root}, so a
separate gather must first be run to find these out.  The data is
placed contiguously at the receiving end.

\begin{verbatim}
    MPI_Comm comm;
    int gsize,sendarray[100][150],*sptr;
    int root, *rbuf, stride, myrank, disp[2], blocklen[2];
    MPI_Datatype stype,types[2];
    int *displs,i,*rcounts,num;

    ...

    MPI_Comm_size( comm, &amp;gsize);
    MPI_Comm_rank( comm, &amp;myrank );

    /* First, gather nums to root
     */
    rcounts = (int *)malloc(gsize*sizeof(int));
    MPI_Gather( &amp;num, 1, MPI_INT, rcounts, 1, MPI_INT, root, comm);
    /* root now has correct rcounts, using these we set displs[] so
     * that data is placed contiguously (or concatenated) at receive end
     */
    displs = (int *)malloc(gsize*sizeof(int));
    displs[0] = 0;
    for (i=1; i&lt;gsize; ++i) {
        displs[i] = displs[i-1]+rcounts[i-1];
    }
    /* And, create receive buffer
     */
    rbuf = (int *)malloc(gsize*(displs[gsize-1]+rcounts[gsize-1])
							     *sizeof(int));
    /* Create datatype for one int, with extent of entire row
     */
    disp[0] = 0;       disp[1] = 150*sizeof(int);
    type[0] = MPI_INT; type[1] = MPI_UB;
    blocklen[0] = 1;   blocklen[1] = 1;
    MPI_Type_struct( 2, blocklen, disp, type, &amp;stype );
    MPI_Type_commit( &amp;stype );
    sptr = &amp;sendarray[0][myrank];
    MPI_Gatherv( sptr, num, stype, rbuf, rcounts, displs, MPI_INT,
                                                               root, comm);
\end{verbatim}
} \end{example}

\section{Scatter}
\label{sec:coll-scatter}

\begin{funcdef}{MPI\_SCATTER( sendbuf, sendcount, sendtype, recvbuf,
recvcount, recvtype, root, comm)}
\funcarg{\IN}{ sendbuf}{ address of send buffer (choice, significant
only at root)}
\funcarg{\IN}{ sendcount}{ number of elements sent to each process
(integer, significant only at root)}
\funcarg{\IN}{ sendtype}{ data type of send buffer elements
(significant only at root) (handle)}
\funcarg{\OUT}{ recvbuf}{ address of receive buffer (choice)}
\funcarg{\IN}{ recvcount}{ number of elements in receive buffer (integer)}
\funcarg{\IN}{ recvtype}{ data type of receive buffer elements (handle)}
\funcarg{\IN}{ root}{  rank of sending process (integer)}
\funcarg{\IN}{ comm}{ communicator (handle)}
\end{funcdef}

\mpibind{MPI\_Scatter(void*~sendbuf, int~sendcount, MPI\_Datatype~sendtype, void*~recvbuf, int~recvcount, MPI\_Datatype~recvtype, int~root, MPI\_Comm~comm)}

\mpifbind{MPI\_SCATTER(SENDBUF, SENDCOUNT, SENDTYPE, RECVBUF, RECVCOUNT, RECVTYPE, ROOT, COMM, IERROR) \fargs &lt;type&gt; SENDBUF(*), RECVBUF(*) \\ INTEGER SENDCOUNT, SENDTYPE, RECVCOUNT, RECVTYPE, ROOT, COMM, IERROR}


\func{ MPI\_SCATTER} is the inverse operation to \func{MPI\_GATHER}.

The outcome is {\em as if} the root executed {\tt n} send operations,
\[\tt
MPI\_Send(sendbuf+i\cdot sendcount\cdot extent(sendtype), sendcount,
sendtype, i,...),
\]
and each process executed a receive,
\[\tt
MPI\_Recv(recvbuf, recvcount, recvtype, i,...).
\]

An alternative description is that the root sends a message with
\mpifunc{MPI\_Send(sendbuf, sendcount$\cdot$n, sendtype, ...)}. This
message is split into {\tt n} equal segments, the $i$th segment is
sent to the $i$th process in the group, and each process receives
this message as above.

The send buffer is ignored for all non-root processes.

The type signature associated with \mpiarg{sendcount, sendtype} at the root
must be equal to the type signature associated with
\mpiarg{recvcount, recvtype} at all
processes (however, the type maps may be different).
This implies that the amount of data sent must be equal to the
amount of data received, pairwise between each process and the root.
Distinct type maps between sender and receiver are still allowed.

All arguments to the function are significant on process \mpiarg{root},
while on other processes, only arguments \mpiarg{recvbuf, recvcount,
recvtype, root, comm} are significant.
The arguments \mpiarg{root} and \mpiarg{comm}
must have identical values on all processes.

The specification of counts and types
should not cause any location on the root to be read more than
once.

\begin{rationale}
Though not needed, the last restriction is imposed so as
to achieve symmetry with
\func{MPI\_GATHER}, where the corresponding restriction (a multiple-write
restriction) is necessary.
\end{rationale}


\begin{funcdef}{MPI\_SCATTERV( sendbuf, sendcounts, displs, sendtype,
recvbuf, recvcount, recvtype, root, comm)}
\funcarg{\IN}{ sendbuf}{ address of send buffer (choice, significant
only at root)}
\funcarg{\IN}{ sendcounts}{ integer array (of length group size)
specifying the number of elements to send to each processor }
\funcarg{\IN}{ displs}{ integer array (of length group size).  Entry
{\tt i} specifies the displacement (relative to \mpiarg{sendbuf} from
which to take the outgoing data to process {\tt i}}
\funcarg{\IN}{ sendtype}{ data type of send buffer elements (handle)}
\funcarg{\OUT}{ recvbuf}{ address of receive buffer (choice)}
\funcarg{\IN}{ recvcount}{ number of elements in receive buffer (integer)}
\funcarg{\IN}{ recvtype}{ data type of receive buffer elements (handle)}
\funcarg{\IN}{ root}{  rank of sending process (integer)}
\funcarg{\IN}{ comm}{ communicator (handle)}
\end{funcdef}

\mpibind{MPI\_Scatterv(void*~sendbuf, int~*sendcounts, int~*displs, MPI\_Datatype~sendtype, void*~recvbuf, int~recvcount, MPI\_Datatype~recvtype, int~root, MPI\_Comm~comm)}

\mpifbind{MPI\_SCATTERV(SENDBUF, SENDCOUNTS, DISPLS, SENDTYPE, RECVBUF, RECVCOUNT, RECVTYPE, ROOT, COMM, IERROR) \fargs &lt;type&gt; SENDBUF(*), RECVBUF(*) \\ INTEGER SENDCOUNTS(*), DISPLS(*), SENDTYPE, RECVCOUNT, RECVTYPE, ROOT, COMM, IERROR}


\func{ MPI\_SCATTERV} is the inverse operation to \func{MPI\_GATHERV}.

\func{MPI\_SCATTERV} extends the functionality of \func{MPI\_SCATTER}
by allowing a varying count of data to be sent to each process,
since \mpiarg{sendcounts} is now an array.
It also allows more flexibility as to where the data
is taken from on the root, by providing the new argument, \mpiarg{displs}.

The outcome is as if the root executed {\tt n} send operations,
\[\tt
MPI\_Send(sendbuf+displs[i]\cdot extent(sendtype), sendcounts[i],
sendtype, i,...),
\]
and each process executed a receive,
\[\tt
MPI\_Recv(recvbuf, recvcount, recvtype, i,...).
\]

The send buffer is ignored for all non-root processes.

The type signature implied by \mpiarg{sendcount[i], sendtype} at the root
must be equal to the type signature implied by
\mpiarg{recvcount, recvtype} at process
{\tt i} (however, the type maps may be different).
This implies that the amount of data sent must be equal to the
amount of data received, pairwise between each process and the root.
Distinct type maps between sender and receiver are still allowed.

All arguments to the function are significant on process \mpiarg{root},
while on other processes, only arguments \mpiarg{recvbuf, recvcount,
recvtype, root, comm} are significant.
The arguments \mpiarg{root} and \mpiarg{comm}
must have identical values on all processes.

The specification of counts, types, and displacements
should not cause any location on the root to be read more than
once.

\subsection{Examples using \func{MPI\_SCATTER}, \func{MPI\_SCATTERV}}

\begin{example} {\rm
\label{coll-exI}

The reverse of Example \ref{coll-exA}.
Scatter sets of 100 ints from the root to each process in the group.
See figure \ref{fig-coll-exI}.

\begin{verbatim}
    MPI_Comm comm;
    int gsize,*sendbuf;
    int root, rbuf[100];
    ...
    MPI_Comm_size( comm, &amp;gsize);
    sendbuf = (int *)malloc(gsize*100*sizeof(int));
    ...
    MPI_Scatter( sendbuf, 100, MPI_INT, rbuf, 100, MPI_INT, root, comm);
\end{verbatim}
} \end{example}

\begin{figure}
\centerline{\hbox{
\psfig{figure=mycoll-fig7.ps,width=3.50in}}}
  \small
  \caption{The root process scatters sets of 100 {\tt int}s to each process
  in the group.
  }
  \label{fig-coll-exI}
\end{figure}

\begin{example} {\rm
\label{coll-exJ}

The reverse of Example \ref{coll-exC}.
The root process scatters sets of 100 ints to the other processes,
but the sets of 100 are {\em stride} ints apart in the sending buffer.
Requires use of \func{MPI\_SCATTERV}.
Assume $stride \geq 100$.  See figure \ref{fig-coll-exJ}.

\begin{verbatim}
    MPI_Comm comm;
    int gsize,*sendbuf;
    int root, rbuf[100], i, *displs, *scounts;

    ...

    MPI_Comm_size( comm, &amp;gsize);
    sendbuf = (int *)malloc(gsize*stride*sizeof(int));
    ...
    displs = (int *)malloc(gsize*sizeof(int));
    scounts = (int *)malloc(gsize*sizeof(int));
    for (i=0; i&lt;gsize; ++i) {
        displs[i] = i*stride;
        scounts[i] = 100;
    }
    MPI_Scatterv( sendbuf, scounts, displs, MPI_INT, rbuf, 100, MPI_INT,
                                                              root, comm);
\end{verbatim}
} \end{example}

\begin{figure}
\centerline{\hbox{
\psfig{figure=mycoll-fig8.ps,width=3.50in}}}
  \small
  \caption{The root process scatters sets of 100 {\tt int}s, moving by
  {\tt stride} ints from send to send in the scatter.
  }
  \label{fig-coll-exJ}
\end{figure}

\begin{example} {\rm
\label{coll-exK}

The reverse of Example \ref{coll-exG}.
We have a varying stride between blocks at sending (root) side,
at the receiving side we receive into the ith column of a 100$\times$150
C array.
See figure \ref{fig-coll-exK}.

\begin{verbatim}
    MPI_Comm comm;
    int gsize,recvarray[100][150],*rptr;
    int root, *sendbuf, myrank, bufsize, *stride;
    MPI_Datatype rtype;
    int i, *displs, *scounts, offset;
    ...
    MPI_Comm_size( comm, &amp;gsize);
    MPI_Comm_rank( comm, &amp;myrank );

    stride = (int *)malloc(gsize*sizeof(int));
    ...
    /* stride[i] for i = 0 to gsize-1 is set somehow
     * sendbuf comes from elsewhere
     */
    ...
    displs = (int *)malloc(gsize*sizeof(int));
    scounts = (int *)malloc(gsize*sizeof(int));
    offset = 0;
    for (i=0; i&lt;gsize; ++i) {
        displs[i] = offset;
        offset += stride[i];
        scounts[i] = 100 - i;
    }
    /* Create datatype for the column we are receiving
     */
    MPI_Type_vector( 100-myrank, 1, 150, MPI_INT, &amp;rtype);
    MPI_Type_commit( &amp;rtype );
    rptr = &amp;recvarray[0][myrank];
    MPI_Scatterv( sendbuf, scounts, displs, MPI_INT, rptr, 1, rtype,
                                                            root, comm);

\end{verbatim}
} \end{example}

\begin{figure}
\centerline{\hbox{
\psfig{figure=mycoll-fig9.ps,width=4.00in}}}
  \small
  \caption{The root scatters blocks of {100-i} ints into
  column {\tt i} of a 100$\times$150
  C array.  At the sending side, the blocks are {\tt stride[i]} ints apart.
  }
  \label{fig-coll-exK}
\end{figure}

\section{Gather-to-all}
\label{sec:coll-allcast}

\begin{funcdef}{MPI\_ALLGATHER( sendbuf, sendcount, sendtype, recvbuf,
recvcount, recvtype, comm)}
\funcarg{\IN}{ sendbuf}{ starting address of send buffer (choice)}
\funcarg{\IN}{ sendcount}{ number of elements in send buffer (integer)}
\funcarg{\IN}{ sendtype}{ data type of send buffer elements (handle)}
\funcarg{\OUT}{ recvbuf}{ address of receive buffer (choice)}
\funcarg{\IN}{ recvcount}{ number of elements received from any
process (integer)}
\funcarg{\IN}{ recvtype}{ data type of receive buffer elements (handle)}
\funcarg{\IN}{ comm}{  communicator (handle)}
\end{funcdef}

\mpibind{MPI\_Allgather(void*~sendbuf, int~sendcount, MPI\_Datatype~sendtype, void*~recvbuf, int~recvcount, MPI\_Datatype~recvtype, MPI\_Comm~comm)}

\mpifbind{MPI\_ALLGATHER(SENDBUF, SENDCOUNT, SENDTYPE, RECVBUF, RECVCOUNT, RECVTYPE, COMM, IERROR) \fargs &lt;type&gt; SENDBUF(*), RECVBUF(*) \\ INTEGER SENDCOUNT, SENDTYPE, RECVCOUNT, RECVTYPE, COMM, IERROR}


\func{MPI\_ALLGATHER} can be thought of as \func{MPI\_GATHER}, but
where all processes receive the result, instead of just the root.
The {\tt j}th block of data sent from each process is received
by every process and placed in the {\tt j}th block of the
buffer \mpiarg{recvbuf}.

The type signature associated with \mpiarg{sendcount, sendtype},
at a process must be equal to the type signature associated with
\mpiarg{recvcount, recvtype} at any other process.

The outcome of a call to \mpifunc{MPI\_ALLGATHER(...)} is as if
all processes executed {\tt n} calls to
\begin{verbatim}
   MPI_GATHER(sendbuf,sendcount,sendtype,recvbuf,recvcount,
                                                 recvtype,root,comm),
\end{verbatim}
for {\tt root = 0 , ..., n-1}.  The rules for correct usage of
\func{MPI\_ALLGATHER} are easily found from the corresponding rules
for \func{MPI\_GATHER}.

\begin{funcdef}{MPI\_ALLGATHERV( sendbuf, sendcount, sendtype, recvbuf,
recvcounts, displs, recvtype, comm)}
\funcarg{\IN}{ sendbuf}{ starting address of send buffer (choice)}
\funcarg{\IN}{ sendcount}{ number of elements in send buffer (integer)}
\funcarg{\IN}{ sendtype}{ data type of send buffer elements (handle)}
\funcarg{\OUT}{ recvbuf}{ address of receive buffer (choice)}
\funcarg{\IN}{ recvcounts}{ integer array (of length group size)
containing the number of elements that are received from each process}
\funcarg{\IN}{ displs}{ integer array (of length group size).  Entry
{\tt i} specifies the displacement (relative to \mpiarg{recvbuf}) at
which to place the incoming data from process {\tt i}}
\funcarg{\IN}{ recvtype}{ data type of receive buffer elements (handle)}
\funcarg{\IN}{ comm}{  communicator (handle)}
\end{funcdef}

\mpibind{MPI\_Allgatherv(void*~sendbuf, int~sendcount, MPI\_Datatype~sendtype, void*~recvbuf, int~*recvcounts, int~*displs, MPI\_Datatype~recvtype, MPI\_Comm~comm)}

\mpifbind{MPI\_ALLGATHERV(SENDBUF, SENDCOUNT, SENDTYPE, RECVBUF, RECVCOUNTS, DISPLS, RECVTYPE, COMM, IERROR) \fargs &lt;type&gt; SENDBUF(*), RECVBUF(*) \\ INTEGER SENDCOUNT, SENDTYPE, RECVCOUNTS(*), DISPLS(*), RECVTYPE, COMM, IERROR}


\func{MPI\_ALLGATHERV} can be thought of as \func{MPI\_GATHERV}, but
where all processes receive the result, instead of just the root.
The {\tt j}th block of data sent from each process is received
by every process and placed in the {\tt j}th block of the
buffer \mpiarg{recvbuf}.  These blocks need not all be the same size.

The type signature associated with \mpiarg{sendcount, sendtype},
at process {\tt j} must be equal to the type signature associated with
\mpiarg{recvcounts[j], recvtype} at any other process.

The outcome is as if all processes executed calls to
\begin{verbatim}
    MPI_GATHERV(sendbuf,sendcount,sendtype,recvbuf,recvcounts,displs,
                                                   recvtype,root,comm),
\end{verbatim}
for {\tt root = 0 , ..., n-1}.  The rules for correct usage of
\func{MPI\_ALLGATHERV} are easily found from the corresponding rules
for \func{MPI\_GATHERV}.

\subsection{Examples using \func{MPI\_ALLGATHER}, \func{MPI\_ALLGATHERV}}
\label{coll:allgather-ex}

\begin{example} {\rm
\label{coll-exY}

The all-gather version of Example \ref{coll-exA}.
Using \func{MPI\_ALLGATHER}, we will gather 100 ints from every process in the
group to every process.

\begin{verbatim}
    MPI_Comm comm;
    int gsize,sendarray[100];
    int *rbuf;
    ...
    MPI_Comm_size( comm, &amp;gsize);
    rbuf = (int *)malloc(gsize*100*sizeof(int));
    MPI_Allgather( sendarray, 100, MPI_INT, rbuf, 100, MPI_INT, comm);
\end{verbatim}

After the call, every process has the group-wide concatenation of the
sets of data.
} \end{example}

\section{All-to-All Scatter/Gather}
\label{sec:coll-alltoall}

\begin{funcdef}{MPI\_ALLTOALL(sendbuf, sendcount, sendtype, recvbuf,
recvcount, recvtype, comm)}
\funcarg{\IN}{ sendbuf}{ starting address of send buffer (choice)}
\funcarg{\IN}{ sendcount}{ number of elements sent to each process (integer)}
\funcarg{\IN}{ sendtype}{ data type of send buffer elements (handle)}
\funcarg{\OUT}{ recvbuf}{ address of receive buffer (choice)}
\funcarg{\IN}{ recvcount}{ number of elements received from any
process (integer)}
\funcarg{\IN}{ recvtype}{ data type of receive buffer elements (handle)}
\funcarg{\IN}{ comm}{ communicator (handle)}
\end{funcdef}

\mpibind{MPI\_Alltoall(void*~sendbuf, int~sendcount, MPI\_Datatype~sendtype, void*~recvbuf, int~recvcount, MPI\_Datatype~recvtype, MPI\_Comm~comm)}

\mpifbind{MPI\_ALLTOALL(SENDBUF, SENDCOUNT, SENDTYPE, RECVBUF, RECVCOUNT, RECVTYPE, COMM, IERROR) \fargs &lt;type&gt; SENDBUF(*), RECVBUF(*) \\ INTEGER SENDCOUNT, SENDTYPE, RECVCOUNT, RECVTYPE, COMM, IERROR}


\func{MPI\_ALLTOALL} is an extension of \func{MPI\_ALLGATHER} to the case
where each process sends distinct data to each of the receivers.
The {\tt j}th block sent from process {\tt i} is received by process {\tt j}
and is placed in the {\tt i}th block of \mpiarg{recvbuf}.

The type signature associated with \mpiarg{sendcount, sendtype},
at a process must be equal to the type signature associated with
\mpiarg{recvcount, recvtype} at any other process.
This implies that the amount of data sent must be equal to the
amount of data received, pairwise between every pair of processes.
As usual, however, the type maps may be different.

The outcome is as if each process executed a send to each
process (itself included)
with a call to,
\[\tt
MPI\_Send(sendbuf+i\cdot sendcount\cdot
extent(sendtype),sendcount,sendtype,i, ...),
\]
and a receive from every other process
with a call to,
\[\tt
MPI\_Recv(recvbuf+i\cdot recvcount\cdot extent(recvtype),recvcount,i,...).
\]

All arguments
on all processes are significant.  The argument \mpiarg{comm}
must have identical values on all processes.


\begin{funcdef}{MPI\_ALLTOALLV(sendbuf, sendcounts, sdispls, sendtype,
recvbuf, recvcounts, rdispls, recvtype, comm)}
\funcarg{\IN}{ sendbuf}{ starting address of send buffer (choice)}
\funcarg{\IN}{ sendcounts}{ integer array equal to the group size
specifying the number of elements to send to each processor}
\funcarg{\IN}{ sdispls}{ integer array (of length group size).  Entry
{\tt j} specifies the displacement (relative to \mpiarg{sendbuf} from
which to take the outgoing data destined for process {\tt j}}
\funcarg{\IN}{ sendtype}{ data type of send buffer elements (handle)}
\funcarg{\OUT}{ recvbuf}{ address of receive buffer (choice)}
\funcarg{\IN}{ recvcounts}{ integer array equal to the group size
specifying the number of elements that can be received from
each processor}
\funcarg{\IN}{ rdispls}{ integer array (of length group size).  Entry
{\tt i} specifies the displacement (relative to \mpiarg{recvbuf} at
which to place the incoming data from process {\tt i}}
\funcarg{\IN}{ recvtype}{ data type of receive buffer elements (handle)}
\funcarg{\IN}{ comm}{ communicator (handle)}
\end{funcdef}

\mpibind{MPI\_Alltoallv(void*~sendbuf, int~*sendcounts, int~*sdispls, MPI\_Datatype~sendtype, void*~recvbuf, int~*recvcounts, int~*rdispls, MPI\_Datatype~recvtype, MPI\_Comm~comm)}

\mpifbind{MPI\_ALLTOALLV(SENDBUF, SENDCOUNTS, SDISPLS, SENDTYPE, RECVBUF, RECVCOUNTS, RDISPLS, RECVTYPE, COMM, IERROR) \fargs &lt;type&gt; SENDBUF(*), RECVBUF(*) \\ INTEGER SENDCOUNTS(*), SDISPLS(*), SENDTYPE, RECVCOUNTS(*), RDISPLS(*), RECVTYPE, COMM, IERROR}


\func{MPI\_ALLTOALLV} adds flexibility to \func{MPI\_ALLTOALL} in that
the location of data for the send is specified by \mpiarg{sdispls}
and the location of the placement of the data on the receive side
is specified by \mpiarg{rdispls}.

The {\tt j}th block sent from process {\tt i} is received by process {\tt j}
and is placed in the {\tt i}th block of \mpiarg{recvbuf}.  These blocks
need not all have the same size.

The type signature associated with
\mpiarg{sendcount[j], sendtype} at process {\tt i} must be equal
to the type signature
associated with \mpiarg{recvcount[i], recvtype} at process {\tt j}.
This implies that the amount of data sent must be equal to the
amount of data received, pairwise between every pair of processes.
Distinct type maps between sender and receiver are still allowed.

The outcome is as if each process sent a message to every other process
with,
\[\tt
MPI\_Send(sendbuf+displs[i]\cdot extent(sendtype),sendcounts[i],sendtype,i,...),
\]
and received a message from every other process with
a call to
\[\tt
MPI\_Recv(recvbuf+displs[i]\cdot extent(recvtype),recvcounts[i],recvtype,i,...).
\]

All arguments
on all processes are significant.  The argument \mpiarg{comm}
must have identical values on all processes.

\begin{rationale}
The definitions of \func{MPI\_ALLTOALL} and \func{MPI\_ALLTOALLV} give as much
flexibility as one would achieve by specifying {\tt n} independent,
point-to-point communications, with two exceptions: all messages use the same
datatype, and messages are scattered from (or gathered to) sequential
storage.
\end{rationale}

\begin{implementors}
Although the discussion of collective communication in terms of
point-to-point operation implies that each message is transferred directly
from sender to receiver, implementations may use a tree communication
pattern. Messages can be forwarded by intermediate nodes where they
are split (for scatter) or concatenated (for gather), if this
is more efficient.
\end{implementors}

%\subsection{Examples using \func{MPI\_ALLTOALL}, \func{MPI\_ALLTOALLV}}
%\label{coll:alltoall-ex}

\section{Global Reduction Operations}
\label{global-reduce}

The functions in this section perform a global reduce operation (such
as sum, max, logical AND, etc.) across all the members of a group.
The reduction operation can be either one of a predefined list of
operations, or a user-defined operation.
The global reduction functions come in several flavors: a reduce that
returns the result of the reduction at one node, an all-reduce that
returns this result at all nodes, and a scan (parallel prefix)
operation.  In addition, a reduce-scatter operation combines the
functionality of a reduce and of a scatter operation.

\subsection{Reduce}
\label{subsec:coll-reduce}

\begin{funcdef}{MPI\_REDUCE( sendbuf, recvbuf, count, datatype, op,
root, comm)}
\funcarg{\IN}{ sendbuf}{ address of send buffer (choice)}
\funcarg{\OUT}{ recvbuf}{ address of receive buffer (choice,
significant only at root)}
\funcarg{\IN}{ count}{ number of elements in send buffer (integer)}
\funcarg{\IN}{ datatype}{ data type of elements of send buffer (handle)}
\funcarg{\IN}{ op}{ reduce operation (handle)}
\funcarg{\IN}{ root}{ rank of root process (integer)}
\funcarg{\IN}{ comm}{  communicator (handle)}
\end{funcdef}

\mpibind{MPI\_Reduce(void*~sendbuf, void*~recvbuf, int~count, MPI\_Datatype~datatype, MPI\_Op~op, int~root, MPI\_Comm~comm)}

\mpifbind{MPI\_REDUCE(SENDBUF, RECVBUF, COUNT, DATATYPE, OP, ROOT, COMM, IERROR) \fargs &lt;type&gt; SENDBUF(*), RECVBUF(*) \\ INTEGER COUNT, DATATYPE, OP, ROOT, COMM, IERROR}

\func{MPI\_REDUCE} combines the elements provided
in the input buffer of each process in the
group, using the operation \mpiarg{op}, and returns the combined value in
the output buffer of the process with rank \mpiarg{root}.
The input buffer is defined by the arguments \mpiarg{sendbuf},
\mpiarg{count} and \mpiarg{datatype}; the output buffer is defined by
the arguments \mpiarg{recvbuf}, \mpiarg{count} and \mpiarg{datatype};
both have the same number of elements, with the same type.
The routine is called by all group members using the same arguments
for \mpiarg{count, datatype, op, root} and \mpiarg{comm}.
Thus, all processes provide input buffers and output buffers of the
same length, with elements of the same type.
Each process can provide one element, or a sequence of elements,
in which case the
combine operation is executed element-wise on each entry of the sequence.
For example, if the operation is \const{MPI\_MAX} and the send buffer
contains two elements that are floating point numbers (\mpiarg{count} = 2 and
\mpiarg{datatype} = \type{MPI\_FLOAT}), then $\sf recvbuf(1) =
\rm global \max (\sf sendbuf(1))$ and $\sf recvbuf(2) = \rm global \max ( \sf
sendbuf(2))$.

Sec. \ref{coll-predefined-op}, lists the set of predefined operations
provided by \MPI/. That section also enumerates
the datatypes each operation can be applied to.
In addition, users may define their own operations that can be
overloaded to operate on several datatypes, either basic or derived.
This is further explained in Sec. \ref{subsec:coll-user-ops}.

The operation \mpiarg{op} is always assumed to be
associative.  All predefined operations are also assumed to be
commutative.  Users may define operations that are assumed to be
associative, but not commutative.  The ``canonical'' evaluation order
of a reduction is determined by the ranks of the processes in the
group.  However, the implementation can take
advantage of associativity, or associativity and commutativity
in order to change the order of evaluation.
This may change the result of the reduction for operations that are not
strictly associative and commutative, such as floating point addition.


\begin{implementors}
It is strongly recommended that \mpifunc{MPI\_REDUCE} be implemented so
that the same result be obtained
whenever the function is applied on the same arguments,
appearing in the same order.  Note that this may
prevent optimizations that take
advantage of the physical location of processors.
\end{implementors}

The \mpiarg{datatype} argument of \mpifunc{MPI\_REDUCE} must be
compatible with \mpiarg{op}.  Predefined operators work only with
the \MPI/ types listed in Sec. \ref{coll-predefined-op} and Sec.
\ref{coll-minloc-maxloc}.  User-defined operators may operate
on general, derived datatypes.  In this case, each argument that
the reduce operation is applied to is one element described by such a datatype,
which may contain several basic values.
This is further explained in Section~\ref{subsec:coll-user-ops}.

\subsection{Predefined reduce operations}
\label{coll-predefined-op}

The following predefined operations are supplied for \mpifunc{MPI\_REDUCE}
and related functions \mpifunc{MPI\_ALLREDUCE}, \mpifunc{MPI\_REDUCE\_SCATTER},
and \mpifunc{MPI\_SCAN}.
These operations are invoked by placing the following in \mpiarg{op}.

% \newpage
\begin{constlist}
\constitem{Name}{ Meaning}
\constitem{}{ }
\constitem{MPI\_MAX}{ maximum}
\constitem{MPI\_MIN}{ minimum}
\constitem{MPI\_SUM}{ sum}
\constitem{MPI\_PROD}{ product}
\constitem{MPI\_LAND}{ logical and }
\constitem{MPI\_BAND}{ bit-wise and }
\constitem{MPI\_LOR}{ logical or }
\constitem{MPI\_BOR}{ bit-wise or }
\constitem{MPI\_LXOR}{ logical xor}
\constitem{MPI\_BXOR}{ bit-wise xor}
\constitem{MPI\_MAXLOC}{ max value and location}
\constitem{MPI\_MINLOC}{ min value and location}
\end{constlist}

The two operations \const{MPI\_MINLOC} and \const{MPI\_MAXLOC} are
discussed separately in Sec. \ref{coll-minloc-maxloc}.
For the other predefined operations,
we enumerate below the allowed combinations of \mpiarg{op} and
\mpiarg{datatype} arguments.
First, define groups of \MPI/ basic datatypes
in the following way.

\begin{constlist}
\constitem{C integer:}{\type{MPI\_INT, MPI\_LONG, MPI\_SHORT,
\linebreak
MPI\_UNSIGNED\_SHORT, MPI\_UNSIGNED,
\linebreak
MPI\_UNSIGNED\_LONG}}
\constitem{Fortran integer:}{\type{MPI\_INTEGER}}
\constitem{Floating point:}{\type{MPI\_FLOAT, MPI\_DOUBLE, MPI\_REAL,
\linebreak
MPI\_DOUBLE\_PRECISION, MPI\_LONG\_DOUBLE}}
\constitem{Logical:}{\type{MPI\_LOGICAL}}
\constitem{Complex:}{\type{MPI\_COMPLEX}}
\constitem{Byte:}{\type{MPI\_BYTE}}
\end{constlist}

Now, the valid datatypes for each option is specified below.

\begin{constlist}
\constitem{Op}{ Allowed Types}
\constitem{}{ }
\snir
\constitem{MPI\_MAX, MPI\_MIN}{\const{C integer, Fortran integer, Floating point}}
\rins
\constitem{MPI\_SUM, MPI\_PROD}{\const{C integer, Fortran integer, Floating point, Complex}}
\constitem{MPI\_LAND, MPI\_LOR, MPI\_LXOR}{\const{C integer, Logical}}
\constitem{MPI\_BAND, MPI\_BOR, MPI\_BXOR}{\const{C integer, Fortran integer, Byte}}
\end{constlist}


\begin{example} {\rm
\label{coll-exblas1}

A routine that computes
the dot product of two vectors that are distributed across a
group of processes and returns the answer at node zero.

\begin{verbatim}
SUBROUTINE PAR_BLAS1(m, a, b, c, comm)
REAL a(m), b(m)       ! local slice of array
REAL c                ! result (at node zero)
REAL sum
INTEGER m, comm, i, ierr

! local sum
sum = 0.0
DO i = 1, m
   sum = sum + a(i)*b(i)
END DO

! global sum
CALL MPI_REDUCE(sum, c, 1, MPI_REAL, MPI_SUM, 0, comm, ierr)
RETURN
\end{verbatim}
}
\end{example}

\begin{example} {\rm
\label{coll-exblas2}

A routine that computes
the product of a vector and an array that are distributed across a
group of processes and returns the answer at node zero.

\begin{verbatim}
SUBROUTINE PAR_BLAS2(m, n, a, b, c, comm)
REAL a(m), b(m,n)    ! local slice of array
REAL c(n)            ! result
REAL sum(n)
INTEGER n, comm, i, j, ierr

! local sum
DO j= 1, n
  sum(j) = 0.0
  DO i = 1, m
    sum(j) = sum(j) + a(i)*b(i,j)
  END DO
END DO

! global sum
CALL MPI_REDUCE(sum, c, n, MPI_REAL, MPI_SUM, 0, comm, ierr)

! return result at node zero (and garbage at the other nodes)
RETURN
\end{verbatim}
}
\end{example}

\subsection{MINLOC and MAXLOC}
\label{coll-minloc-maxloc}

The operator \const{MPI\_MINLOC} is used to compute
a global minimum and also
an index attached to the minimum value.
\const{MPI\_MAXLOC} similarly computes a global maximum and index.
One application of these is to compute a global minimum (maximum) and the
rank of the process containing this value.

The operation that defines \const{MPI\_MAXLOC} is:

\[
\left( \begin{array}{c} u \\ i \end{array} \right)
\circ
\left( \begin{array}{c} v \\ j \end{array} \right)
=
\left( \begin{array}{c} w \\ k \end{array} \right)
\]
where
\[
w = \max (u,v)
\]
and
\[
k = \left\{ \begin{array}{ll}
    i &amp; \mbox{if $u &gt; v$} \\
    \min(i,j) &amp; \mbox{if $u=v$} \\
    j &amp; \mbox{if $u &lt; v$}
\end{array}
\right.
\]

\const{MPI\_MINLOC} is defined similarly:

\[
\left( \begin{array}{c} u \\ i \end{array} \right)
\circ
\left( \begin{array}{c} v \\ j \end{array} \right)
=
\left( \begin{array}{c} w \\ k \end{array} \right)
\]
where
\[
w = \min (u,v)
\]
and
\[
k = \left\{ \begin{array}{ll}
    i &amp; \mbox{if $u &lt; v$} \\
    \min(i,j) &amp; \mbox{if $u=v$} \\
    j &amp; \mbox{if $u &gt; v$}
\end{array}
\right.
\]

Both operations are associative and commutative.
Note that if \const{MPI\_MAXLOC}
is applied to reduce a sequence of pairs
$(u_0, 0), (u_1, 1) , \ldots, (u_{n-1} , n-1)$, then the value
returned is $(u , r)$, where $u = \max_i u_i$ and $r$ is the index of
the first global maximum in the sequence.  Thus, if each process
supplies a value and its rank within the group, then a reduce
operation with \mpiarg{op} = \const{MPI\_MAXLOC} will return the
maximum value and the rank of the first process with that value.
Similarly, \const{MPI\_MINLOC} can be used to return a minimum and its
index.
More generally, \const{MPI\_MINLOC} computes a {\em lexicographic
minimum}, where elements are ordered according to the first component
of each pair, and ties are resolved according to the second component.

The reduce operation is defined to operate on arguments that
consist of a pair: value and index.
For both Fortran and C, types are provided to describe the pair.
The potentially mixed-type nature of such arguments
is a problem in Fortran.  The problem is circumvented, for Fortran, by
having the \MPI/-provided type consist of a pair of the same type as
value, and coercing the index to this type also.  In C, the \MPI/-provided
pair type has distinct types and the index is an \type{int}.


In order to use \const{MPI\_MINLOC} and \const{MPI\_MAXLOC} in a
reduce operation, one must provide a \mpiarg{datatype} argument
that represents a pair (value and index).  \MPI/ provides seven such
predefined datatypes.  The operations \const{MPI\_MAXLOC} and
\const{MPI\_MINLOC} can be used with each of the following datatypes.
\snir
\begin{constlist}
\constitem{Fortran:}{}
\constitem{Name}{ Description}
\constitem{\const{MPI\_2REAL}}{pair of \ftype{REAL}s}
\constitem{\const{MPI\_2DOUBLE\_PRECISION}}{pair of \ftype{DOUBLE PRECISION} variables}
\constitem{\const{MPI\_2INTEGER}}{pair of \ftype{INTEGER}s}
\end{constlist}
\begin{constlist}
\rins
\constitem{C:}{}
\constitem{Name}{ Description}
\constitem{\const{MPI\_FLOAT\_INT}}{\type{float} and \type{int}}
\constitem{\const{MPI\_DOUBLE\_INT}}{\type{double} and \type{int}}
\constitem{\const{MPI\_LONG\_INT}}{\type{long} and \type{int}}
\constitem{\const{MPI\_2INT}}{pair of \type{int} }
\constitem{\const{MPI\_SHORT\_INT}}{\type{short} and \type{int} }
\constitem{\const{MPI\_LONG\_DOUBLE\_INT}}{\type{long double} and \type{int} }
\end{constlist}

The datatype \const{MPI\_2REAL} is {\em as if} defined by the following
(see Section~\ref{sec:pt2pt-datatype}).

\begin{verbatim}
MPI_TYPE_CONTIGUOUS(2, MPI_REAL, MPI_2REAL)
\end{verbatim}

Similar statements apply for \const{MPI\_2INTEGER},
\const{MPI\_2DOUBLE\_PRECISION}, and \const{MPI\_2INT}.

The datatype \const{MPI\_FLOAT\_INT} is {\em as if} defined by the
following sequence of instructions.
\begin{verbatim}
type[0] = MPI_FLOAT
type[1] = MPI_INT
disp[0] = 0
disp[1] = sizeof(float)
block[0] = 1
block[1] = 1
MPI_TYPE_STRUCT(2, block, disp, type, MPI_FLOAT_INT)
\end{verbatim}
% !!! I may want to change this -- S Otto -- assumes C struct alignment /
% MPI derived type compatibility
Similar statements apply for \const{MPI\_LONG\_INT}
and \const{MPI\_DOUBLE\_INT}.

\begin{example} {\rm
\label{coll-exminlocC}

Each process has an array of 30 {\tt double}s, in C.  For each
of the 30 locations, compute the value and rank of the process containing
the largest value.

\begin{verbatim}
    ...
    /* each process has an array of 30 double: ain[30]
     */
    double ain[30], aout[30];
    int  ind[30];
    struct {
        double val;
        int   rank;
    } in[30], out[30];
    int i, myrank, root;

    MPI_Comm_rank(MPI_COMM_WORLD, &amp;myrank);
    for (i=0; i&lt;30; ++i) {
        in[i].val = ain[i];
        in[i].rank = myrank;
    }
    MPI_Reduce( in, out, 30, MPI_DOUBLE_INT, MPI_MAXLOC, root, comm );
    /* At this point, the answer resides on process root
     */
    if (myrank == root) {
        /* read ranks out
         */
        for (i=0; i&lt;30; ++i) {
            aout[i] = out[i].val;
            ind[i] = out[i].rank;
        }
    }
\end{verbatim}
} \end{example}



\begin{example} {\rm
\label{coll-exminlocF}

Same example, in Fortran.

\begin{verbatim}
    ...
    ! each process has an array of 30 double: ain(30)

    DOUBLE PRECISION ain(30), aout(30)
    INTEGER ind(30);
    DOUBLE PRECISION in(2,30), out(2,30)
    INTEGER i, myrank, root, ierr;

    MPI_COMM_RANK(MPI_COMM_WORLD, myrank);
    DO I=1, 30
        in(1,i) = ain(i)
        in(2,i) = myrank    ! myrank is coerced to a double
    END DO

    MPI_REDUCE( in, out, 30, MPI_2DOUBLE_PRECISION, MPI_MAXLOC, root,
                                                          comm, ierr );
    ! At this point, the answer resides on process root

    IF (myrank .EQ. root) THEN
        ! read ranks out
        DO I= 1, 30
            aout(i) = out(1,i)
            ind(i) = out(2,i)  ! rank is coerced back to an integer
        END DO
    END IF
\end{verbatim}
} \end{example}




\begin{example} {\rm
\label{coll-exminlocC2}

Each process has a non-empty array of values.
Find the minimum global value, the rank of the process that holds it
and its index on this process.

\begin{verbatim}
#define  LEN   1000

float val[LEN];        /* local array of values */
int count;             /* local number of values */
int myrank, minrank, minindex;
float minval;

struct {
    float value;
    int   index;
} in, out;

    /* local minloc */
in.value = val[0];
in.index = 0;
for (i=1; i &lt; count; i++)
    if (in.value &gt; val[i]) {
        in.value = val[i];
        in.index = i;
    }

    /* global minloc */
MPI_Comm_rank(MPI_COMM_WORLD, &amp;myrank);
in.index = myrank*LEN + in.index;
MPI_Reduce( in, out, 1, MPI_FLOAT_INT, MPI_MINLOC, root, comm );
    /* At this point, the answer resides on process root
     */
if (myrank == root) {
    /* read answer out
     */
    minval = out.value;
    minrank = out.index / LEN;
    minindex = out.index % LEN;
}
\end{verbatim}
} \end{example}





\begin{rationale}
The definition of \const{MPI\_MINLOC} and \const{MPI\_MAXLOC} given
here has the advantage that it does not require any special-case
handling of these two operations: they are handled like any other
reduce operation.  A programmer can provide his or her own definition
of \const{MPI\_MAXLOC} and \const{MPI\_MINLOC}, if so desired.
The disadvantage is that values and indices have to be first
interleaved, and that indices and values have to be coerced to the
same type, in Fortran.
\end{rationale}

\subsection{User-Defined Operations}
\label{subsec:coll-user-ops}

\begin{funcdef}{MPI\_OP\_CREATE( function, commute, op)}
\funcarg{\IN}{function}{ user defined function (function)}
\funcarg{\IN}{commute}{ {\tt true} if commutative; {\tt false} otherwise.}
\funcarg{\OUT}{op}{ operation (handle) }
\end{funcdef}

\mpibind{MPI\_Op\_create(MPI\_User\_function~*function, int~commute, MPI\_Op~*op)}

\mpifbind{MPI\_OP\_CREATE( FUNCTION, COMMUTE, OP, IERROR) \fargs EXTERNAL FUNCTION \\ LOGICAL COMMUTE \\ INTEGER OP, IERROR}

\func{MPI\_OP\_CREATE} binds a user-defined global operation
to an \mpiarg{op} handle that can subsequently be used in
\func{MPI\_REDUCE}, \func{MPI\_ALLREDUCE},
\func{MPI\_REDUCE\_SCATTER}, and \linebreak
\func{MPI\_SCAN}.
The user-defined operation is assumed to be associative.
If \mpiarg{commute} $=$ {\tt true}, then the operation should be both
commutative and associative. If  \mpiarg{commute} $=$ {\tt false},
\snir
then the order of operands is fixed and is defined to be in ascending, process
rank order, beginning with process zero.  The order of evaluation can be
changed, talking advantage of the associativity of the operation.  If
\mpiarg{commute} $=$ {\tt true} then the order of evaluation can be changed,
taking advantage of commutativity and associativity.
\rins

\mpiarg{function} is the user-defined function, which must have the
following four arguments: {\sf invec, inoutvec, len} and {\sf datatype}.

The ANSI-C prototype for the function is the following.
\begin{verbatim}
typedef void MPI_User_function( void *invec, void *inoutvec, int *len,
                                                MPI_Datatype *datatype);
\end{verbatim}

The Fortran declaration of the user-defined function appears below.
\begin{verbatim}
FUNCTION USER_FUNCTION( INVEC(*), INOUTVEC(*), LEN, TYPE)
&lt;type&gt; INVEC(LEN), INOUTVEC(LEN)
 INTEGER LEN, TYPE
\end{verbatim}

The \mpiarg{datatype} argument
is a handle to the data type that was passed into the call
to \func{MPI\_REDUCE}.
The user reduce function should be written such that the following
holds:
Let {\sf u[0], ... , u[len-1]} be the {\sf len} elements in the
communication buffer described by the arguments \mpiarg{invec, len}
and \mpiarg{datatype} when the function is invoked;
let {\sf v[0], ... , v[len-1]} be {\sf len} elements in the
communication buffer described by the arguments \mpiarg{inoutvec, len}
and \mpiarg{datatype} when the function is invoked;
let {\sf w[0], ... , w[len-1]} be  {\sf len} elements in the
communication buffer described by the arguments \mpiarg{inoutvec, len}
and \mpiarg{datatype} when the function returns;
then {\sf w[i] = u[i]$\circ$v[i]}, for {\sf i=0 , ... , len-1},
where $\circ$ is the reduce operation that the function computes.

Informally, we can think of
\mpiarg{invec} and \mpiarg{inoutvec} as arrays of \mpiarg{len} elements that
\mpiarg{function}
is combining.  The result of the reduction over-writes values in
\mpiarg{inoutvec}, hence the name.  Each invocation of the function results in
the pointwise evaluation of the reduce operator on \mpiarg{len}
elements:
I.e, the function returns in \mpiarg{inoutvec[i]} the value
$\sf invec[i] \circ inoutvec[i]$, for $\sf i=0, \ldots , count-1$,
where $\sf \circ$ is the combining operation computed by the function.



\begin{rationale}
The len argument allows
\func{MPI\_REDUCE} to avoid calling the function for each element
in the input buffer.  Rather, the system can choose to apply
the function to chunks of input.  In C, it is passed in as
a reference for reasons of compatibility with Fortran.

By internally comparing the value of the \mpiarg{datatype} argument to
known, global handles,
it is possible to overload the use of a single user-defined function
for several, different data types.
\end{rationale}

General datatypes may be passed to the user function.
However, use of datatypes that are not contiguous is likely to lead to
inefficiencies.

No \MPI/ communication function may be called inside the user function.
\func{MPI\_ABORT} may be called inside the
function in case of an error.

\begin{users}
Suppose one defines a library of user-defined reduce
functions that are overloaded: the \mpiarg{datatype} argument is used
to select the right execution path at each invocation, according to
the types of the operands.
The user-defined reduce function cannot ``decode'' the
\mpiarg{datatype} argument that it is passed, and cannot identify,
by itself, the correspondence between the datatype handles and the datatype
they represent.  This correspondence was established when the datatypes
were created.  Before the library is used, a library initialization
preamble must be executed.  This preamble code will define the
datatypes that are used by the library, and store handles to these
datatypes in global, static variables that are shared by the user code and the
library code.

The Fortran version of \mpifunc{MPI\_REDUCE} will invoke a user-defined reduce
function using the Fortran calling conventions and will pass a Fortran-type
datatype argument;  the C version will use C calling convention and the C
representation of a datatype handle.  Users who plan to mix languages should
define their reduction functions accordingly.
\end{users}


\begin{implementors}
We outline below a naive and inefficient implementation of
\mpifunc{MPI\_REDUCE}.

\begin{verbatim}
	if (rank &gt; 0) {
	    RECV(tempbuf, count, datatype, rank-1,...)
	    User_reduce( tempbuf, sendbuf, count, datatype)
	}
	if (rank &lt; groupsize-1) {
	    SEND( sendbuf, count, datatype, rank+1, ...)
	}
	/* answer now resides in process groupsize-1 ... now send to root
	 */
	if (rank == groupsize-1) {
	    SEND( sendbuf, count, datatype, root, ...)
	}
	if (rank == root) {
	    RECV(recvbuf, count, datatype, groupsize-1,...)
	}
\end{verbatim}

The reduction computation proceeds, sequentially, from process {\tt 0}
to process {\tt group-} {\tt size-1}.  This  %mansplit
order is chosen so as to respect
the order of a possibly non-commutative operator defined by the
function {\tt User\_reduce()}.
A more efficient implementation is achieved by taking advantage
of associativity and
using a logarithmic tree reduction.  Commutativity can be used
to advantage, for those cases in which the \mpiarg{commute} argument
to \func{MPI\_OP\_CREATE} is true.  Also, the amount of temporary buffer
required can be reduced, and communication can be pipelined with
computation, by transferring and reducing the elements in chunks of
size {\tt len} $&lt;${\tt count}.

The predefined reduce operations can be implemented as a library of
user-defined operations.  However, better performance might be
achieved if \mpifunc{MPI\_REDUCE} handles these functions as a special
case.
\end{implementors}


\begin{funcdef}{MPI\_OP\_FREE( op)}
\funcarg{\IN}{op}{ operation (handle) }
\end{funcdef}

\mpibind{MPI\_op\_free( MPI\_Op~*op)}

\mpifbind{MPI\_OP\_FREE( OP, IERROR) \fargs INTEGER OP, IERROR}

Marks a user-defined reduction operation for deallocation and sets
\mpiarg{op} to \const{MPI\_OP\_NULL}.

\subsubsection{Example of User-defined Reduce}
\label{coll-user-reduce-example}

It is time for an example of user-defined reduction.

\begin{example} {\rm
\label{coll-exX}
Compute the product of an array of complex numbers, in C.

\begin{verbatim}
typedef struct {
    double real,imag;
} Complex;

/* the user-defined function
 */
void myProd( Complex *in, Complex *inout, int *len, MPI_Datatype *dptr )
{
    int i;
    Complex c;

    for (i=0; i&lt; *len; ++i) {
        c.real = inout-&gt;real*in-&gt;real -
                   inout-&gt;imag*in-&gt;imag;
        c.imag = inout-&gt;real*in-&gt;imag +
                   inout-&gt;imag*in-&gt;real;
        *inout = c;
        in++; inout++;
    }
}

/* and, to call it...
 */
...

    /* each process has an array of 100 Complexes
     */
    Complex a[100], answer[100];
    MPI_Op myOp;
    MPI_Datatype ctype;

    /* explain to MPI how type Complex is defined
     */
    MPI_Type_contiguous( 2, MPI_DOUBLE, &amp;ctype );
    MPI_Type_commit( &amp;ctype );
    /* create the complex-product user-op
     */
    MPI_Op_create( myProd, True, &amp;myOp );

    MPI_Reduce( a, answer, 100, ctype, myOp, root, comm );

    /* At this point, the answer, which consists of 100 Complexes,
     * resides on process root
     */
\end{verbatim}

} \end{example}

\subsection{All-Reduce}
\label{subsec:coll-all-reduce}

\MPI/ includes variants of each of the reduce operations
where the result is returned to all processes in the group.
\MPI/ requires that all processes participating in these
operations receive identical results.

\begin{funcdef}{MPI\_ALLREDUCE( sendbuf, recvbuf, count, datatype, op, comm)}
\funcarg{\IN}{sendbuf}{ starting address of send buffer (choice)}
\funcarg{\OUT}{recvbuf}{ starting address of receive buffer (choice)}
\funcarg{\IN}{count}{ number of elements in send buffer (integer)}
\funcarg{\IN}{datatype}{ data type of elements of send buffer (handle)}
\funcarg{\IN}{op}{ operation (handle)}
\funcarg{\IN}{comm}{ communicator (handle)}
\end{funcdef}

\mpibind{MPI\_Allreduce(void*~sendbuf, void*~recvbuf, int~count, MPI\_Datatype~datatype, MPI\_Op~op, MPI\_Comm~comm)}

\mpifbind{MPI\_ALLREDUCE(SENDBUF, RECVBUF, COUNT, DATATYPE, OP, COMM, IERROR) \fargs &lt;type&gt; SENDBUF(*), RECVBUF(*) \\ INTEGER COUNT, DATATYPE, OP, COMM, IERROR}

Same as \func{MPI\_REDUCE} except that the result
appears in the receive buffer of all the group members.

\begin{implementors}
The all-reduce operations can be implemented as a reduce, followed by a
broadcast.  However, a direct implementation can lead to better performance.
\end{implementors}


\begin{example} {\rm
\label{coll-exallblas2}

A routine that computes
the product of a vector and an array that are distributed across a
group of processes and returns the answer at all nodes (see also Example
\ref{coll-exblas2}).

\begin{verbatim}
SUBROUTINE PAR_BLAS2(m, n, a, b, c, comm)
REAL a(m), b(m,n)    ! local slice of array
REAL c(n)            ! result
REAL sum(n)
INTEGER n, comm, i, j, ierr

! local sum
DO j= 1, n
  sum(j) = 0.0
  DO i = 1, m
    sum(j) = sum(j) + a(i)*b(i,j)
  END DO
END DO

! global sum
CALL MPI_ALLREDUCE(sum, c, n, MPI_REAL, MPI_SUM, 0, comm, ierr)

! return result at all nodes
RETURN
\end{verbatim}
}
\end{example}


\section{Reduce-Scatter}
\label{sec:coll-reduce-scatter}

\MPI/ includes variants of each of the reduce operations
where the result is scattered to all processes in the group on return.

\begin{funcdef}{MPI\_REDUCE\_SCATTER( sendbuf, recvbuf, recvcounts,
datatype, op, comm)}
\funcarg{\IN}{sendbuf}{ starting address of send buffer (choice)}
\funcarg{\OUT}{recvbuf}{ starting address of receive buffer (choice)}
\funcarg{\IN}{recvcounts}{ integer array specifying the
number of elements in result distributed to each process.
Array must be identical on all calling processes.}
\funcarg{\IN}{datatype}{ data type of elements of input buffer (handle)}
\funcarg{\IN}{op}{ operation (handle)}
\funcarg{\IN}{comm}{ communicator (handle)}
\end{funcdef}

\mpibind{MPI\_Reduce\_scatter(void*~sendbuf, void*~recvbuf, int~*recvcounts, MPI\_Datatype~datatype, MPI\_Op~op, MPI\_Comm~comm)}

\mpifbind{MPI\_REDUCE\_SCATTER(SENDBUF, RECVBUF, RECVCOUNTS, DATATYPE, OP, COMM, IERROR) \fargs &lt;type&gt; SENDBUF(*), RECVBUF(*) \\ INTEGER RECVCOUNTS(*), DATATYPE, OP, COMM, IERROR}


\func{MPI\_REDUCE\_SCATTER} first does
an element-wise reduction on
vector of $\sf count =  \sum_{i} recvcounts[i]$ elements
in the send buffer defined by \mpiarg{sendbuf, count} and
\mpiarg{datatype}.
Next, the resulting vector of results is split into {\tt n} disjoint
segments, where {\tt n} is the number of members in the group.
Segment {\tt i} contains \mpiarg{recvcounts[i]} elements.
The {\tt i}th segment is sent to process {\tt i} and stored in the
receive buffer defined by \mpiarg{recvbuf, recvcounts[i]} and
\mpiarg{datatype}.


\begin{implementors}
The \mpifunc{MPI\_REDUCE\_SCATTER}
routine is functionally equivalent to:
A \func{MPI\_REDUCE} operation function with \mpiarg{count} equal to
the sum of \mpiarg{recvcounts[i]} followed by
\func{MPI\_SCATTERV} with \mpiarg{sendcounts} equal to \mpiarg{recvcounts}.
However, a direct implementation may run faster.
\end{implementors}

\section{Scan}
\label{sec:coll-scan}

\begin{funcdef}{MPI\_SCAN( sendbuf, recvbuf, count, datatype, op, comm )}
\funcarg{\IN}{sendbuf}{starting address of send buffer (choice)}
\funcarg{\OUT}{recvbuf}{ starting address of receive buffer (choice)}
\funcarg{\IN}{count}{ number of elements in input buffer (integer)}
\funcarg{\IN}{datatype}{ data type of elements of input buffer (handle)}
\funcarg{\IN}{op}{ operation (handle)}
\funcarg{\IN}{comm}{ communicator (handle)}
\end{funcdef}

\mpibind{MPI\_Scan(void*~sendbuf, void*~recvbuf, int~count, MPI\_Datatype~datatype, MPI\_Op~op, MPI\_Comm~comm )}

\mpifbind{MPI\_SCAN(SENDBUF, RECVBUF, COUNT, DATATYPE, OP, COMM, IERROR) \fargs &lt;type&gt; SENDBUF(*), RECVBUF(*) \\ INTEGER COUNT, DATATYPE, OP, COMM, IERROR}

\func{MPI\_SCAN} is used to perform a prefix reduction
on data distributed across the group.
The operation returns, in the receive buffer of the process with rank
{\tt i}, the
reduction of the values in the send buffers of processes with ranks {\tt
0,...,i} (inclusive).  The type of operations supported,
their semantics, and the
constraints on send and receive buffers are as for \func{MPI\_REDUCE}.

\begin{rationale}
We have defined an inclusive scan, that is, the prefix reduction on
process {\tt i} includes the data from process {\tt i}.  An alternative
is to define scan in an exclusive manner, where the result on {\tt i}
only includes data up to {\tt i-1}.  Both definitions are useful.
The latter has some advantages:
the inclusive scan can always be computed from the exclusive scan with
no additional communication; for non-invertible operations
such as max and min, communication is required to compute
the exclusive scan from the inclusive scan.
There
is, however, a complication with exclusive scan since one must define the
``unit'' element for the reduction in this case.  That is, one must
explicitly say what occurs for process {\tt 0}.  This was thought to
be complex for user-defined operations and hence, the exclusive scan
was dropped.
\end{rationale}

\subsection{Example using \func{MPI\_SCAN}}
\label{coll-scan-example}

\begin{example} {\rm
\label{coll-exW}

This example uses a user-defined operation to produce a {\em segmented
scan}.  A segmented scan takes, as input, a set of values and a set of logicals,
and the logicals delineate the various segments of the scan.
For example:
$$
\begin{array}{lcccccccc}
values &amp; v_1 &amp; v_2 &amp; v_3 &amp; v_4 &amp; v_5 &amp; v_6 &amp; v_7 &amp; v_8 \\
logicals &amp; 0 &amp; 0   &amp; 1   &amp; 1   &amp; 1   &amp; 0   &amp; 0   &amp; 1   \\
result &amp; v_1 &amp; v_1 + v_2 &amp; v_3 &amp; v_3 + v_4 &amp; v_3 + v_4 + v_5 &amp; v_6 &amp; v_6 + v_7 &amp; v_8
\end{array}
$$

The operator that produces this effect is,

$$
\left( \begin{array}{c} u \\ i \end{array} \right)
\circ
\left( \begin{array}{c} v \\ j \end{array} \right)
=
\left( \begin{array}{c} w \\ j \end{array} \right) ,
$$

where,

$$
w = \left\{ \begin{array}{ll}
    u+v &amp; \mbox{if $i = j$} \\
    v &amp; \mbox{if $i \neq j$}
    \end{array}
    \right.
.
$$

Note that this is a non-commutative operator.
C code that implements it is given below.

\begin{verbatim}
typedef struct {
    double val;
    int log;
} SegScanPair;

/* the user-defined function
 */
void segScan( SegScanPair *in, SegScanPair *inout, int *len,
						MPI_Datatype *dptr )
{
    int i;
    SegScanPair c;

    for (i=0; i&lt; *len; ++i) {
        if ( in-&gt;log == inout-&gt;log )
            c.val = in-&gt;val + inout-&gt;val;
        else
            c.val = inout-&gt;val;
        c.log = inout-&gt;log;
        *inout = c;
        in++; inout++;
    }
}
\end{verbatim}

Note that the \mpiarg{inout} argument to the user-defined function
corresponds to the right-hand operand of the operator.  When using
this operator, we must be careful to specify that it is non-commutative,
as in the following.

\begin{verbatim}
    int i,base;
    SeqScanPair  a, answer;
    MPI_Op       myOp;
    MPI_Datatype type[2] = {MPI_DOUBLE, MPI_INT};
    MPI_Aint     disp[2];
    int          blocklen[2] = { 1, 1};
    MPI_Datatype sspair;

    /* explain to MPI how type SegScanPair is defined
     */
    MPI_Address( a, disp);
    MPI_Address( a.log, disp+1);
    base = disp[0];
    for (i=0; i&lt;2; ++i) disp[i] -= base;
    MPI_Type_struct( 2, blocklen, disp, type, &amp;sspair );
    MPI_Type_commit( &amp;sspair );
    /* create the segmented-scan user-op
     */
    MPI_Op_create( segScan, False, &amp;myOp );
    ...
    MPI_Scan( a, answer, 1, sspair, myOp, root, comm );
\end{verbatim}

} \end{example}

\section{Correctness}
\label{coll:correct}

A correct, portable program must invoke collective communications so
that deadlock will
not occur, whether collective communications are synchronizing or not.
The following examples illustrate dangerous use of collective routines.

\begin{example} {\rm
\label{coll-excorr1}

The following is erroneous.

\begin{verbatim}
switch(rank) {
    case 0:
        MPI_Bcast(buf1, count, type, 0, comm);
        MPI_Bcast(buf2, count, type, 1, comm);
        break;
    case 1:
        MPI_Bcast(buf2, count, type, 1, comm);
        MPI_Bcast(buf1, count, type, 0, comm);
        break;
}
\end{verbatim}

We assume that the group of {\sf comm} is \{0,1\}.
Two processes execute two broadcast operations in reverse order.  If
the operation is synchronizing then a deadlock will occur.

Collective
operations must be executed in the same order at all members of the
communication group.
}
\end{example}


\begin{example} {\rm
\label{coll-excorr2}

The following is erroneous.

\begin{verbatim}
switch(rank) {
    case 0:
        MPI_Bcast(buf1, count, type, 0, comm0);
        MPI_Bcast(buf2, count, type, 2, comm2);
        break;
    case 1:
        MPI_Bcast(buf1, count, type, 1, comm1);
        MPI_Bcast(buf2, count, type, 0, comm0);
        break;
    case 2:
        MPI_Bcast(buf1, count, type, 2, comm2);
        MPI_Bcast(buf2, count, type, 1, comm1);
        break;
}
\end{verbatim}

Assume that the group of
{\sf comm0} is \{0,1\}, of {\sf comm1} is \{1, 2\} and of {\sf comm2}
is \{2,0\}.  If the broadcast is a synchronizing operation, then there
is a cyclic dependency: the broadcast in {\sf comm2} completes only
after the broadcast in {\sf comm0}; the broadcast in {\sf comm0}
completes only after the broadcast in {\sf comm1}; and the broadcast
in {\sf comm1} completes only after the broadcast in {\sf comm2}.
Thus, the code will deadlock.

Collective operations must be executed in an order so that
no cyclic dependences occur.
}
\end{example}


\begin{example} {\rm
\label{coll-exM}

The following is erroneous.

\begin{verbatim}
switch(rank) {
    case 0:
        MPI_Bcast(buf1, count, type, 0, comm);
        MPI_Send(buf2, count, type, 1, tag, comm);
        break;
    case 1:
        MPI_Recv(buf2, count, type, 0, tag, comm, status);
        MPI_Bcast(buf1, count, type, 0, comm);
        break;
}
\end{verbatim}

Process zero executes a broadcast, followed by a blocking send operation.
Process one first executes a blocking receive that matches the send,
followed by broadcast call that matches the broadcast of process zero.
This program may deadlock.  The broadcast call on process zero
{\em may} block until process one executes the matching
broadcast call, so that the
send is not executed.  Process one will definitely block on the
receive and so, in this case, never executes the
broadcast.

The relative order of execution of collective operations and point-to-point
operations should be such, so that even if the collective
operations and the point-to-point operations are synchronizing, no
deadlock will occur.
} \end{example}

\begin{example} {\rm
\label{coll-exN}

A correct, but non-deterministic program.

\begin{verbatim}
switch(rank) {
    case 0:
        MPI_Bcast(buf1, count, type, 0, comm);
        MPI_Send(buf2, count, type, 1, tag, comm);
        break;
    case 1:
        MPI_Recv(buf2, count, type, MPI_ANY_SOURCE, tag, comm, status);
        MPI_Bcast(buf1, count, type, 0, comm);
        MPI_Recv(buf2, count, type, MPI_ANY_SOURCE, tag, comm, status);
        break;
    case 2:
        MPI_Send(buf2, count, type, 1, tag, comm);
        MPI_Bcast(buf1, count, type, 0, comm);
        break;
}
\end{verbatim}

All three processes participate in a broadcast.  Process 0 sends a message to
process 1 after the broadcast, and process 2 sends a message
to process 1 before
the broadcast.  Process 1 receives before and after the broadcast, with a
wildcard source argument.

Two possible executions of this program, with different matchings
of sends and receives, are
illustrated in figure \ref{fig-coll-exN}.
Note that the second execution has the peculiar effect that a send executed
after the broadcast is received at another node before the broadcast.
This example illustrates the fact that one should not rely on
collective communication functions to have particular synchronization
effects.
A program that works correctly only when the first execution occurs
(only when broadcast is synchronizing) is erroneous.

} \end{example}

\begin{figure}
\centerline{\hbox{
\psfig{figure=coll-matchings.ps,width=4.00in}}}
  \small
  \caption{A race condition causes non-deterministic matching of sends
  and receives.  One cannot rely on synchronization from a broadcast
  to make the program deterministic.}
  \label{fig-coll-exN}
\end{figure}

Finally, in multithreaded implementations, one can have more than one,
concurrently executing, collective communication call at a process.  In these
situations, it is the user's responsibility to ensure that
the same communicator is not used concurrently by two different
collective communication calls at the same process.

\begin{implementors}
Assume that broadcast is implemented using point-to-point \MPI/ communication.
Suppose the following two rules are followed.
\begin{enumerate}
\item
All receives specify their source explicitly (no wildcards).
\item
Each process sends all messages that pertain to one collective call before
sending any message that pertain to a subsequent collective call.
\end{enumerate}
Then, messages belonging to successive broadcasts cannot be confused,
as the order of point-to-point messages is preserved.

It is the implementor's responsibility to
ensure that point-to-point messages are not confused with collective
messages.  One way to accomplish this is, whenever a communicator is
created, to also create a ``hidden communicator'' for collective communication.
One could achieve a similar
effect more cheaply, for example, by using a hidden
tag or context bit to indicate
whether the communicator is used for point-to-point or collective
communication.
\end{implementors}









</pre></body></html>