
\documentstyle{article}

\input{psfig} 

\begin{document}

\sloppy

\pagestyle{plain}

\section{Schematic view of the {\tt remap} implementation}

The {\tt remap} operation copies an array \verb$src$ to an
array \verb$dst$.  The two arrays must have the same shape (and type)
but their mappings need not be related.

The Adlib implementation is considered to be essentially ``optimal'' in
the sense that that it minimizes the number of block communication
operations required to implement the data redistribution.  In this
context a ``block communication operation'' is a send or receive
operation on a regular \verb$R$-dimensional block of memory,
parametrized by a base address, \verb$R$ extents, and \verb$R$ memory
strides.  Because arbitrary strides are allowed, a block is not
necessarily contiguous in memory: MPI allows sending
or receiving such non-contiguous blocks through derived-type constructors
such as \verb$MPI_Type_hvector$.

The \verb$remap$ operation is implemented in two stages:
\begin{enumerate}
\item
construct a {\em communication schedule}, then
\item
execute that schedule.
\end{enumerate}
A communication schedule can be implemented by three lists in each
processor:  a list of block send operations, list of block receive
operations, and a list of local block memory copy operations.

The scheme for constructing the ``send'' component of the
communication schedule is illustrated in figures 
\ref{src}, \ref{dst} and \ref{send}.
%\begin{figure}[btp]
\begin{figure}[bp]
\centerline{\psfig{figure=src.eps,height=2in}}
\caption{\label{src}Distribution of array {\em src} onto a grid of
four processors}
\end{figure}
\begin{figure}[btp]
\centerline{\psfig{figure=dst.eps,height=2in}}
\caption{\label{dst}Distribution of section of {\em dst} array
corresponding to highlighted block of {\em src} array}
\end{figure}
\begin{figure}[btp]
\centerline{\psfig{figure=send.eps,height=2in}}
\caption{\label{send}Block send operations required to redistribute
highlighted block of {\em src} array}
\end{figure}
In figure \ref{src} we see that the source array is mapped into
a processor grid with some blocks on each processor (in the picture
\verb$src$ has a block cyclic distribution in one of its dimensions).
On each processor, we enumerate the locally held blocks in an outer
loop.  One such block is highlighted.  This block represents some
regular section of the \verb$src$ array.  This section has to be
copied to the corresponding regular section of the \verb$dst$ array.
Figure \ref{dst} illustrates how the latter regular section might
be mapped to the processor grid.  We enumerate the blocks of the
target section: in this case redistributing the
highlighted block requires one local copy operation
and three send operations, as illustrated in figure \ref{send}.

An analoguous procedure constructs the receive schedule.

As block sends and receives are enumerated they are placed in
queues, prioritized by the difference between source and destination process
ids (modulo the number of processes).  Messages of ``hop'' 1 will be sent
first, followed by messages of hop 2, and so on (hop 0 corresponds to
local memory copies).  During the ``execute'' phase of the \verb$remap$,
sends and receives occur in different logical threads (which are
simulated by using MPI non-blocking communication operations).  This
strategy avoids deadlock.

\end{document}

