\input{caption}
\makeatletter\long\def\unmarkedfootnote#1{{\long\def\@makefntext##1{##1}\footnotetext{#1}
}}
\makeatother
\newcommand{\comment}[1]{}

%\documentstyle[times,epsf,11pt]{article}
\documentstyle[times,epsf,twocolumn]{article}

\pagestyle{empty}
\setlength {\topmargin}{-.5in}
\setlength {\headheight}{0in}
\setlength {\footheight}{0in}
\setlength {\footskip}{1.25in}
\setlength {\textheight}{9.00in}


\setlength {\oddsidemargin}{-.25in}
\setlength {\textwidth}{7.00in}
\setlength {\columnsep}{.33in}
\setlength {\parskip}{8pt plus 2pt minus 1pt}
\setlength {\parindent}{4ex}



\def\_{\rule{.3em}{.15ex}}  % Get underscore by typing \_.

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%  Line Spacing (e.g., \ls{1} for single, \ls{2} for double, even \ls{1.5})
%%

\newcommand{\ls}[1]
   {\dimen0=\fontdimen6\the\font
    \lineskip=#1\dimen0
    \advance\lineskip.5\fontdimen5\the\font
    \advance\lineskip-\dimen0
    \lineskiplimit=.9\lineskip
    \baselineskip=\lineskip
    \advance\baselineskip\dimen0
    \normallineskip\lineskip
    \normallineskiplimit\lineskiplimit
    \normalbaselineskip\baselineskip
    \ignorespaces
   }
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\ls{1.19}

\comment{
\textheight =  9.0in
\topmargin = -.5 in 
%\oddsidemargin = -.25 in
%\evensidemargin = -.25 in
\oddsidemargin = 0 in
\evensidemargin = 0 in
\textwidth=6.5in
}

\def\AAPAIR{AAPAIR}
\def\AABLK{AABLK}
\def\DMRLE{DMRLE}
\def\DMRLEC{DMRLEC}

\renewcommand{\dbltopfraction}{.6}
\renewcommand{\topfraction}{.6}
\renewcommand{\textfraction}{.4}
\renewcommand{\floatpagefraction}{.8}
%\renewcommand{\dbltopnumber}{1}
\renewcommand{\dblfloatpagefraction}{.8}


\begin{document}
\bibliographystyle{acm}

\title{
\begin{flushleft}
\vspace{-0.9in}
\scriptsize {\em 
ACM Intl. Conf. on Measurement and Modeling of Computer Systems, 
May, 1996.
}
\end{flushleft}
\vspace{0.4in}
\Large\bf 
Fast Message Assembly Using Compact Address Relations
}
%\author{\mbox{Paper \#537.98}}
\author{Peter A. Dinda \hspace{.5in} David R. O'Hallaron \\
Carnegie Mellon University\\
5000 Forbes Avenue \\
Pittsburgh, PA 15213 \\
\verb!(pdinda,droh)@cs.cmu.edu! \\
}

\date{}
\maketitle 

\unmarkedfootnote{
Supported in part by the Advanced Research Projects
Agency/CSTO monitored by SPAWAR under contract N00039-93-C-0152, in
part by the National Science Foundation under Grant ASC-9318163, and
in part by a grant from the Intel Corporation.
}
{\footnotetext[0]{
Permission to make digital or hard copies of part or all of 
this work for personal or classroom use is granted without 
fee provided that copies are not made or distributed for 
profit or commercial advantage and that copies bear this 
notice and the full citation on the first page. Copyrights 
for components of this work owned by others than ACM must be 
honored. Abstracting with credit is permitted. To copy 
otherwise, to republish, to post on servers or to redistribute
to lists, requires prior specific permission and/or a fee. 

\vspace{0.3cm}
\noindent
SIGMETRICS 96-5/96 Philadelphia, PA, USA \\
\copyright 1996 ACM  
}}
   
\Large
{\bf Abstract}
\normalsize

Message assembly and disassembly represent a significant fraction of
 total communication time in many parallel systems.  We introduce a
run--time approach for fast message assembly and disassembly.
The approach is based on generating addresses by decoding a
precomputed and compactly stored address relation that describes the
mapping of addresses on the source node to addresses on the
destination node.  The main result is that relations induced by
redistributions of regular block--cyclic distributed arrays can be
encoded in an extremely compact form that facilitates high throughput
message assembly and disassembly.  We measure the throughput of
decoding--based message assembly and disassembly on several systems
and find performance on par with copy throughput.


\section{Introduction}
\label{sec:intro}

Many parallel programs perform operations on distributed data
structures by using a message passing system to transfer data items
from noncontiguous addresses in the memory of a source node to
noncontiguous addresses in the memory of a destination node.  These
programs typically amortize the fixed overhead of transferring a
message by packing a collection of data items into a contiguous
message buffer, which the message passing system then transfers over
the network as a single message.  When the message arrives at the
destination, the message is copied from the network to a buffer, which
the user program then unpacks to the appropriate memory locations.  We
refer to the process of packing the data as {\em message assembly} and
to unpacking as {\em message disassembly}.

On machines with fast communication systems, the performance of the
message assembly and disassembly steps can have a significant impact
on the overall communication performance of a program.  In such
systems, the memory system tends to be the bottleneck rather than the
communication system~\cite{STRICKER-OPT-MEM-PERF-COMM-INPROCEEDINGS}.
The range of these systems is increasing with the advent of high speed
networks~\cite{STEENKISTE-HOST-INTERFACE-DESIGN-JOURNAL}.  Further,
even on machines with slow communication systems, overly slow message
assembly and disassembly can lead to disappointing overall
performance.

The message assembly and disassembly operations needed to implement
distributed data structures such as distributed arrays are nontrivial
and the running times of different algorithms can vary significantly.
For example, the running time of the assembly step for a High
Performance Fortran (HPF)~\cite{hpf93} block--cyclic assignment
statement can vary by several orders of magnitude, depending on the
nesting of the assembly loops~\cite{gupta94}.  As another example,
because of asymmetry in the Cray T3D memory system, a transpose
operation implemented with contiguous reads and strided writes runs
twice as fast as the equivalent operation implemented with strided
reads and contiguous writes~\cite{STRICKER-OPT-MEM-PERF-COMM-INPROCEEDINGS}.


\comment{
The general problem addressed here is how to perform fast message
assembly and disassembly in the context of a run--time communication
library.  The library should be fast in the sense that data items
should be transferred between their original locations and the message
buffer at or near the copy throughput of the memory system for the
memory reference pattern. Furthermore, since the assembly and
disassembly routines are in a library, they can rely only on run--time
information.
}

This paper describes a purely run--time,
inspector/executor~\cite{saltz91,AGRAWAL-CHAOS-BLOCK-STRUCT-JOURNAL}
approach for message assembly/disassembly and provides an initial
characterization of its performance on real systems.  In our approach,
when a data transfer is first encountered, the inspector precomputes
the mapping of source node addresses to destination node addresses and
stores this {\em address relation} in some encoding.  The executor
actually performs the transfer by reading and decoding the stored
address relation to generate the addresses needed to assemble the
message on the source node and disassemble it on the destination node.
The intuition is that reading and decoding the address relation is
cheaper than recomputing it on the fly and that by repeatedly using a
stored relation, we can amortize the initial cost of computing and
encoding it.

Our innovation is to encode the address relation in new, compact ways
that facilitate fast message assembly/disassembly executors --- they
are ``fast'' in the sense that data transfer rates to and from the
message buffer approach the copy throughput of the memory system for
the reference pattern.  In previous
work~\cite{AR-CACHING-LCR-INPROCEEDINGS} and in the extended version
of this paper~\cite{FAST-ASSEMBLY-ADDRESS-RELATIONS-TECHREPORT}, we
derive and validate a model that predicts, for a simple index array
encoding, that the regime where the inspector/executor approach is
faster than recomputing address relations on the fly is quite large,
and even extends to cases where computing a member of the relation
requires only a few instructions.  Here, we concentrate on the
executor and develop encodings that exploit the attributes of
relations induced by redistributions of HPF regular, block--cyclicly
distributed arrays to achieve low storage costs and fast message
assembly and disassembly.

\comment{
 Our approach is based on
the notion of decoding a precomputed {\em address relation} that
describes the mapping of addresses on the source node to addresses on
the destination node.  The run--time model is a classic
inspector/executor --- our innovation is to encode the address
relation in new, compact ways.  For each data transfer between a
source and a destination, the appropriate address relation is
precomputed and stored in some encoding.  The stored encoding of the
address relation is decoded by the message assembly and disassembly
routines each time data is transferred.  As with any
inspector/executor scheme, the aim is to exploit the fact that many
parallel programs repeatedly perform the same data transfers. The
focus of this paper is on the performance of the executor (i.e., the
assembly or disassembly step.)
}

We begin with an overview of address relations and approaches to
generating them in Section~\ref{sec:relations}.  The next section,
Section~\ref{sec:represent}, characterizes the address relations
induced by redistributions of block--cyclic arrays, points out the
regularities these relations exhibit, and describes four representative
redistributions.  Section~\ref{sec:compact} introduces address
relation encodings that can encode arbitrary relations, but exploit
the regularities we describe.
%Want this to be one paragraph
\comment{
In Section~\ref{sec:models} we consider a simple but
memory--inefficient encoding of address relations (i.e., an index
array). For this encoding we derive a model that predicts, given
measurable machine parameters, the regimes where decoding address
relations, rather than recomputing them each time, can improve the
average message assembly latency.  For those cases where decoding the
relations is effective, we extend the model to predict the break--even
point (i.e.  how many times does an address relation have to be reused
to amortize the cost of precomputing it) and the upper bound on the
speedup.  Validation on the Intel iWarp~\cite{iwarpoverview,iwarpcomm}
and Paragon~\cite{PARAGON-XPS-MANUAL} systems suggests that the models
have good predictive power. Surprisingly, the results indicate that
even with the simple index array encoding, if recomputing an address
in the assembly loop involves more than a few instructions (1 on the
iWarp, 16 on the Paragon), then decoding a precomputed address
relation can do better.  Further, beyond this threshold, the cost of
precomputing the address relation can be quickly amortized.  }
%One paragraph
Next, in Section~\ref{sec:measure}, we measure the performance of
message assembly/disassembly routines based on the different compact
encodings of address relations.  The performance on each of the four
representative redistributions of Section~\ref{sec:relations} is measured.
Results are given for several common systems: DEC
Alpha~\cite{DEC-3000-JOURNAL}, Intel
Paragon~\cite{PARAGON-XPS-MANUAL}, IBM RS/6000
~\cite{RS6000-ARCHITECTURE-JOURNAL}, IBM SP/2~\cite{IBM-SP1}, Gateway
Pentium 90~\cite{PENTIUM-OVERVIEW-INPROCEEDINGS}, and Micron Pentium
133. The encouraging conclusion is that in most cases, assembly and
disassembly routines based on a highly compact encoding can run at or
near the copy throughput of the memory system for the memory reference
pattern of the relation.  Finally, Section~\ref{sec:discuss} discusses
other implications of decoding precomputed address relations as well
as some open questions that still need to be addressed before the
ultimate usefulness of our approach can be understood.

\section{Generating address relations}
\label{sec:relations}

The transfer of data items from the memory of a {\em source} node to
the memory of a {\em destination} node can be characterized with a
binary relation $R$, which is called an {\em address relation}. The
relation $R$ is a set of {\em tuples} $(s_i, d_i) \in R$, where $s_i$
is an address on the source, called a {\em source address}, and $d_i$
is an address on the destination, called a {\em destination address}.

There are two constraints on the elements of an address relation: (1)
source and destination addresses point to valid memory locations, and
(2) destination addresses are unique.\footnote{ In general, it would
be possible to relax this constraint by associating a binary
associative combining operation with each address relation to handle
non--unique destination addresses. However, we will assume unique
destination addresses in this paper.} Thus, address relations can
describe arbitrary permutations such as transpose operations, as well
as replication of source data items on the destination, but as 
defined here, they cannot describe operations like reductions or
scans.  
\comment{For example, the address relation $\{ (1,4), (2,3)\}$
describes a data transfer that takes the pair of elements at locations
1 and 2 on the source, swaps them, and stores them in locations 3 and
4 on the destination.  The relation $\{ (1,1), (1,2)\}$ describes a
data transfer that copies the data item at location 1 on the
source to locations 1 and 2 on the destination.
}


For a particular data transfer, the message assembly and disassembly
routines must somehow generate the appropriate address relation.
Where the addresses are computed is determined by the message passing
model.  With a {\em send/receive} model, the source node computes the
source addresses and the destination node computes the destination
addresses.  With a {\em put} model, the source node computes the
entire address relation and passes the destination addresses along
with the data.  With a {\em get} model, the destination node computes
the entire address relation and sends the source addresses to
the source, which replies with the data.

%
%  Pseudocode instead of verbatim would save space
%  Also, boxes around would be nice.
%

One approach for generating the address relation is to recompute the
addresses on the fly in the assembly routine. For example, at a high
level an assembly routine to transfer $n$ data items using a {\em
send/receive} model has the following form:
\small
\begin{verbatim}
    loop i = 1 to n	
        recompute source address s(i)
        buffer[i] = memory[s(i)]
    endloop	
\end{verbatim}
\normalsize
Even for fairly regular access patterns, such as those induced by HPF
whole array assignment statements, recomputing the addresses each time
can be complex.  Parallelizing compilers can help a great deal by
exploiting compile--time knowledge to generate specialized assembly
loops for each data transfer~\cite{stichnoth94,IRREGULAR-MALAGA}.
However, if the data access pattern is irregular (and thus unknown to
the compiler), or if a parallelizing compiler is not available, then a
general--purpose run--time library assembly routine is necessary, and
there is a limit to the number of special--case optimizations that
such a library routine can exploit.  Of course, a parallelizing
compiler is also limited to some number of optimizations, but it is
practical to support a far larger number because optimizations can be
selected at compile--time instead of run--time.

We are exploring an alternative approach, based on
inspector/executor~\cite{saltz91,AGRAWAL-CHAOS-BLOCK-STRUCT-JOURNAL},
that allows a general--purpose message assembly routine in a run--time
library to run efficiently without any special--case run--time or
compile--time optimizations. The idea is that instead of recomputing
the address relation from scratch during message assembly, the
relation is precomputed and {\em encoded} (i.e., stored in memory in
some form), either at startup time or the first time a particular data
transfer is encountered.  This inspector phase takes the following
form:
\small
\begin{verbatim}
    loop i = 1 to n	
        compute source address s(i) 
          and receiver address r(i)
        encode s(i), r(i) into relation
    endloop	
\end{verbatim}
\normalsize
The encoded address relation is then {\em decoded} inside the message
assembly loop to provide addresses.  The message assembly routine (the
executor) to transfer $n$ data items using a {\em send/receive} model
would have the following form:
\small
\begin{verbatim}
    loop i = 1 to n	
        decode relation to generate 
          source address s(i)
        buffer[i] = memory[s(i)]
    endloop	
\end{verbatim}
\normalsize
Depending on the message passing model (send/receive, put, or get),
the assembly and disassembly loops will have a different form, but a
library can support all three forms by simply providing the facility
to compute an address relation.

Notice that the two assembly loops above have a similar form. The
intuition behind the decoding approach is that it should be faster to
decode a precomputed form of the address relation than to recompute it
on the fly each time. 
%In some sense, recomputing address relations
%from scratch inside the assembly loop can be thought of as decoding a
%null--encoded relation.
The decoding time depends on the relation itself and its encoding in
memory. 
\comment{
In the next section we derive a representative set of
relations that capture the basic memory access patterns induced by
regular HPF block--cyclic array assignment statements. We then use
these relations to derive a family of encodings that provide the basis
%for the analytic models in Section~\ref{sec:models} and 
for the empirical results in Section~\ref{sec:measure}.
}

\section{Representative address relations}
\label{sec:represent}

%
% Arb, except that it must be onto
%
In general, the elements of an address relation are arbitrary.
However, in many cases the address relations induced by operations on
distributed data structures have considerable regularity. For example,
consider the redistribution of a distributed array in an HPF program.
Each dimension of a regular block--cyclic distributed array has some
size $N$ and is distributed over some number of nodes $P$ with some
fixed block size $M$.  Conceptually, the dimension is split into
$\lceil N/M \rceil$ blocks of size $M$ ($N - M (\lceil N/M \rceil -1) \leq
M$ for the final block) which are then distributed round robin over
the $P$ nodes.  The most common regular block--cyclic distributions
are BLOCK, where there are only $\lceil N/M \rceil = P$ blocks and
CYCLIC, where $M=1$.  Each dimension of an array can be independently
distributed.

The idea of array redistribution is to change the location (node and
address) of elements of the array so as to alter its distribution.
Because the redistribution may be onto a disjoint group of nodes, we
refer to {\em source} and {\em destination} distributions and nodes.
Figure~\ref{fig:redist} shows a source distribution of a
2--dimensional array with a (BLOCK,*) distribution (over two
processors.)  The shaded array elements are those that node 0 owns.
The ``*'' indicates a non--distributed dimension.  The same figure
also shows a destination distribution of (CYCLIC,*) (also over two
processors.)  To redistribute the array, for each pair of source and
destination nodes, we compute the intersection of the elements the
nodes own (which is highlighted in the figure) and map the source node
address of each element in the intersection to its address in the
destination node.  Data is gathered from the source node addresses to
a contiguous buffer, communicated, and scattered to the destination
node addresses.

\begin{figure}[tbph]
\centerline{\epsfxsize 2.5in \epsfbox{example.eps}}
\caption{Redistributing regular block--cyclic arrays}
\label{fig:redist}
\end{figure}

For 1--dimensional BLOCK and CYCLIC arrays, it can clearly be seen
that only simple stride--$j$ to stride--$k$ mappings can occur in an
address relation induced by redistribution.  BLOCK to BLOCK
redistributions result in unit strides on both the source and
destination nodes while the combination of CYCLIC and BLOCK results in
a unit stride on either the source or destination node and a non--unit
stride on the other.  CYCLIC to CYCLIC redistributions result in
non--unit strides on both nodes, as do certain forms of transpose
operations.  With more than one dimension, the access pattern is the
Cartesian product of the access patterns generated for each matching
dimension~\cite{stichnoth93a}.  This can also be seen in
Figure~\ref{fig:redist}.  The basic mapping is stride--2 to stride--1
repeated four times.  This pattern is then repeated stride--8 to
stride--8 16 times.

We place array redistributions of BLOCK and CYCLIC distributed arrays
into four equivalence classes based on whether their basic source and
destination reference patterns have unit or non--unit strides. The four
two--dimensional array redistributions (of a $1024\times 1024$ array
on four processors) of Figure~\ref{fig:repdist} are representatives of
the four classes.  Each distribution is over four nodes.  We include a
data transpose operation instead of a CYCLIC to CYCLIC redistribution
to demonstrate that our technique extends to transposes as well.

\begin{figure*}[tbph]
\begin{center}
\small
\begin{tabular}{|c|c|c|c|c|c|c|c|}
\hline
\multicolumn{2}{|c|}{Redistribution} & \multicolumn{2}{c|}{Assembly} & 
            \multicolumn{2}{c|}{Disassembly} & \multicolumn{2}{c|}{Tuples}  \\ 
\hline
Source & Destination & Read & Write & Read & Write & (0 to all) & (0 to 0)  \\
\hline
(BLOCK,*)  & (*,BLOCK) & 1 & 1 & 1 & 1 & 262144 & 65536\\
(BLOCK,*)  & (CYCLIC,*) & 4 & 1 & 1 & 1 & 262144 & 65536\\
(CYCLIC,*) & (BLOCK,*) & 1 & 1 & 1 & 4 & 262144 & 65536\\
(*,CYCLIC) & (CYCLIC,*)$^T$ & 4 & 1 & 1 & 1024 & 262144 & 65536\\
\hline
\end{tabular}
\normalsize
\end{center}
\caption{Representative redistributions of $1024 \times 1024$ distributed array (four processors), basic memory access strides, and number of tuples.  (``T'' represents a transpose)}
\label{fig:repdist}

\end{figure*}

\section{Encoding address relations}
\label{sec:compact}

In this section, we use the four representative address relations from
Figure~\ref{fig:repdist} to drive the development of compact address
relation encodings that can exploit the regularity of relations
induced by redistributions of regular block--cyclic arrays, while
retaining the expressive power to encode arbitrary relations.

We begin with the \AAPAIR~ encoding, which is a simple index
array that exploits no regularity in the relation, and then introduce
a series of encodings (\AABLK, \DMRLE, and \DMRLEC) that
incrementally exploit more regularity in the relations without loss of
expressive power. 
%For example, \DMRLEC~ exploits more regularity in the
%relations than \DMRLE, which exploits more regularity than
%\AABLK, which exploits more regularity than the \AAPAIR~ base case.
For each encoding, we place a total order $\leq$ on the tuples
of the address relation:
\begin{displaymath}
(s_i,d_i) \leq (s_j,d_j) \Leftrightarrow (s_i <  s_j) \vee ((s_i = s_j) \wedge (d_i
\leq d_j)).
\end{displaymath}
In other words, the tuples are ordered by source node address first,
then by destination node addresses.  The encodings we describe are
also readily adaptable to ordering by destination addresses first.
Because on decoding the relation, we generate addresses according to
this order, the destination--first order may be preferable on machines
which perform strided stores badly. Each encoding is designed so that
it can be used efficiently to assemble and disassemble messages. The
idea is that we repeatedly load some {\em key} from a stored relation,
expand it to a {\em symbol} according to the encoding, and then use
the symbol to gather or scatter some number of data elements.  We do
not consider encodings that are wholly expanded before use.  The
innovation here is not in developing simple data compression
techniques, but in applying these techniques to address relations and
using them during message assembly and disassembly.

Figure~\ref{fig:sizes} shows the total space required for address
relations on source node 0 for each of the representative relations of
Figure~\ref{fig:repdist}.  The sizes are in bytes and measured on the
DEC 3000/400, which is a 64--bit platform.  Relative sizes are the
same on 32--bit platforms, but the absolute sizes are halved.  Note
that the chart has a log scale.  The difference between the \AAPAIR~
and \DMRLEC~ encodings is over three orders of magnitude. Further, the
absolute size of the \DMRLEC--encoded relations is roughly 1Kbytes,
which is quite small.

\begin{figure}[htbp]
\centerline{\epsfxsize 2.5in \epsfbox{sizes.eps}}
\caption{Total size of all address relations on sending node 
zero in each encoding}
\label{fig:sizes}
\end{figure}

The \AAPAIR~encoding (Address, Address PAIR) is simply an array
of source-destination address pairs.  It takes advantage of no memory
access patterns and always requires storage space proportional to the
number of data items transferred.  The keys and symbols for \AAPAIR~are
the tuples themselves.

The \AABLK~encoding (Address, Address BLocK) run-length
encodes~\cite{DATA-COMPRESSION-OVERVIEW-TECHREPORT} blocks of stride--1 to
stride--1 mappings.  The symbols generated are of the form $(s,d,l)$,
which means that addresses $s$ through $s+l-1$ on the source map to
address $d$ through $d+l-1$ on the destination.  The keys are simply the
symbols. Notice that this is sufficient for the first representative
redistribution in Figure~\ref{fig:repdist}, but not the others.

The \DMRLE~ encoding (Difference Map, Run-Length Encoded)
generalizes \AABLK~ to map blocks of addresses with a stride--$j$ source
to a stride-$k$ destination. To encode the relation in \DMRLE, we form
the difference map sequence $\langle(ds_{i},dd_{i})\rangle$ from the
ordered sequence of tuples $\langle(s_{i},d_{i})\rangle$:
\begin{displaymath}
(ds_i, dd_i) = \left \{ 
\begin{array}{ll}
(s_0,d_0) & i=0 \\
(s_i-s_{i-1},d_i-d_{i-1}) & i > 0
\end{array}
\right .
\end{displaymath}
The difference map is then run-length encoded to produce symbols of
the form $(ds,dd,l)$ which are stored as keys.  Notice that this
encoding significantly reduces space requirements for the three
redistributions where \AABLK~ fails, and performs only marginally worse
for the fourth.   

The \DMRLE~ encoding efficiently encodes the basic stride--$j$ to
stride--$k$ mapping, but for multidimensional arrays this will be
repeated many times.  Clearly, because the symbols for inner
dimensions will occur more frequently than for outer dimensions, a
Huffman-encoding~\cite{HUFFMAN-CODES-JOURNAL} of the symbols would
most readily reduce their storage cost.  However, Huffman codes are of
variable length, so keys could span word boundaries and be expensive
to decode during message assembly.  Instead, we adopt a dictionary
substitution encoding~\cite{DATA-COMPRESSION-OVERVIEW-TECHREPORT} of
the symbols as fixed length keys.  The key length is the minimum power
of two bits necessary to represent all the unique symbols.  This
scheme is efficient for message assembly because keys cannot span word
boundaries and there is always the same number of keys per word.

To encode in \DMRLEC~(Difference Map, Run-Length Encoded, Compressed)
the relation is first encoded in \DMRLE ~and all unique $(ds,dd,l)$
symbols are found via hashing.  These symbols are stored in a table of
size $2^k$ for the minimum $k$ possible.  Each symbol is encoded as a
$2^k$-bit key representing its offset in the table.  As can be seen
from Figure~\ref{fig:sizes} this technique reduces the storage cost of
the relations induced by the encoding relations by two orders of
magnitude over \DMRLE.  Overall, \DMRLEC~is three to four orders of
magnitude more space efficient than \AAPAIR.

%\section{Message assembly performance models}
%\label{sec:models}

%This section introduces some models that characterize the tradeoffs
%between decoding precomputed address relations or recomputing them on
%the fly (which we will refer to as decoding vs. recomputing).  In
%particular, the models predict {\em threshold}, {\em break--even}, and
%{\em speed--up}.  {\em Threshold} is the minimum number of
%instructions at which decoding can produce tuples in the relation
%faster than recomputing.  In other words the threshold tells us if,
%for a particular relation, decoding the relation will ever be faster
%than recomputing it.  For those cases where threshold is defined, {\em
%break--even} tells us the number of times a relation must be reused
%before the one--time cost of encoding the relation is amortized, and
%{\em speedup} is the maximum improvement that is possible.

%The models are designed for a {\em put} message passing model, where 
%the source node generates the entire relation.  Only the \AAPAIR~ 
%encoding is used because it is independent of the relation.
%Validation on both the Intel iWarp and Intel Paragon systems finds 
%close agreement between the predicted and actual values.  An important 
%observation is that the threshold values are very low, on the order of 
%one instruction on the iWarp and 16 on the Paragon.  In other words, 
%if it is not possible to produce a tuple every instruction cycle on 
%the iWarp, or every 16 instruction cycles on the Paragon, then 
%decoding \AAPAIR~ wins over precomputing.

%\subsection{Algorithm and machine properties}

%Given some address relation, $n_g$ is the average number of machine
%instructions required to generate a tuple in the relation (either when
%encoding or recomputing the relation).  We model the generation of
%address relation tuples as instruction--issue--rate limited and as
%providing the address relation in an on--line manner.  Further, we
%assume that tuple generation is integer--based and performed in
%registers.

%Additionally, we must know $r_i$, the number of integer instructions
%the machine can issue per second.  Since memory accesses are at the
%heart of message assembly, we characterize the memory system by four
%values: $r_{rc}$ and $r_{wc}$, the read and write bandwidths for
%unit--stride accesses, respectively; and $r_{rr}$ and $r_{wr}$, the
%read and write bandwidths for random memory accesses. These
%parameters, along with the others in the models, are listed in
%Figure~\ref{fig:parms}.
%\begin{figure}[htbp]
%\centering

%\begin{tabular}{|l|l|}
%\hline
%\multicolumn{2}{|c|}{Problem parameters}\\ 
%\hline	
%\hline
%$n$      & data words in the message \\
%$n_i$    & times the data transfer is performed\\
%\hline
%\hline
%\multicolumn{2}{|c|}{Algorithm parameters}\\ 
%\hline	
%\hline
%$n_{ac}$ & loop overhead instructions during decoding\\
%$n_{au}$ & loop overhead instructions during recomputing\\
%$n_g$    & instructions required to compute a tuple \\
%$n_o$    & loop overhead instructions during encoding\\
%\hline
%\hline
%\multicolumn{2}{|c|}{Machine parameters}\\ 
%\hline	
%\hline
%$r_{i}$  & integer instructions/sec the machine can issue\\
%$r_{rc}$ & read bandwidth for unit--stride memory accesses\\
%$r_{rr}$ & read bandwidth for random memory accesses\\
%$r_{wc}$ & write bandwidth for unit--stride memory accesses\\
%$r_{wr}$ & write bandwidth for random memory accesses\\
%\hline
%\end{tabular}

%\caption{Summary of model parameters}
%\label{fig:parms}
%\end{figure}
 
%\subsection{Model for recomputing address relations}

%The time to recompute an address relation during message assembly
%has two components: $t_g$, the time to compute the address relation;
%and $t_{au}$, the message assembly time:
%\begin{displaymath}
%t_{recompute} = t_g + t_{au}
%\end{displaymath}
%The time to compute the address relation is largely determined by the
%complexity of algorithm used, its implementation, and the instruction
%execution rate of the machine.  We characterize the algorithm in terms
%of $n_g$, the number of integer instructions executed per tuple of the
%address relation.  Thus for an $n$ word message, the time required is
%\begin{displaymath}
%t_g = \frac{n n_g}{r_i}
%\end{displaymath}
%The address computation code generates source/destination address
%tuples $(s,r)$ in registers in an on-line manner.  For each of these
%tuples, we read the data word at address $s$, write $r$ to the message
%buffer, then write the data word to the message buffer.  Note that the
%writes to the message buffer are to consecutive addresses, so their
%performance can be captured by $r_{wc}$, the unit--stride write
%bandwidth of the machine.  On the other hand, the source side
%addresses of the tuples may not be contiguous, so we capture their
%performance with $r_{rr}$, the random read bandwidth of the machine.
%Furthermore, we capture the loop overhead as a number of instructions,
%$n_{au}$.  Thus the time to copy the data is
%\begin{displaymath}
%t_{au} = n \left (\frac{1}{r_{rr}} + \frac{2}{r_{wc}} + 
%\frac{n_{au}}{r_i}
%          \right ) 
%\end{displaymath}
%Note that this expression does not take into account cache thrashing
%between the reads and writes.  An implementation will probably
%optimize access patterns by reading several data items at a time.  If
%the compiler software--pipelines the assembly loop, we should be close
%to the above expression.  Substituting into the expression for
%$t_{recompute}$, we get an average assembly latency of 
%\begin{equation}
% t_{recompute} = n \left ( \frac{n_g+n_{au}}{r_i} +
% \frac{1}{r_{rr}} + \frac{2}{r_{wc}} \right )
%\label{equ:uncached}
%\end{equation}

%\subsection{Model for decoding address relations}

%The average latency for decoding precomputed address relations has
%three components: $t_g$, the time to compute the address relation;
%$t_o$, the time to store the address relation in memory, and $t_{ac}$,
%the message assembly time using the stored address relation.  The
%average latency is
%\begin{displaymath}
% t_{decode} = \frac{t_g + t_o}{n_i} + t_{ac}
%\end{displaymath}
%Note that the first two components are amortized over the number of
%times the communication is performed, $n_i$.  $t_g$ is the same as for
%the case where we recomputed the relation on the fly and was
%determined in the preceding section.  We assume the \AAPAIR~ encoding
%from Section~\ref{sec:compact}.  As each tuple of the address relation
%is generated, we write it to memory.  Thus storing the address
%relation involves two contiguous writes for each in-register tuple
%produced by the address relation computation.  In addition, we execute
%$n_o$ loop overhead instructions, so
%\begin{displaymath}
% t_o = n \left ( \frac{2}{r_{wc}} + \frac{n_o}{r_i} \right )
%\end{displaymath}
%When assembling the message from the stored address relation, for each
%tuple in the message, we first perform two consecutive reads to read a
%tuple of the address relation.  Then, we perform a random read
%to read the data word.  Finally, we perform two consecutive writes to
%write the data word and the destination address into the message buffer.
%We also execute $n_{ac}$ loop overhead instructions, thus the time to
%assemble a message with $n$ data words is
%\begin{displaymath}
% t_{ac} = n \left (\frac{2}{r_{rc}} + \frac{1}{r_{rr}} +
%\frac{2}{r_{wc}} +\frac{n_{ac}}{r_i}\right ) 
%\end{displaymath}
%Note that this expression does not take into account cache thrashing
%between the reads and writes, but we continue the assumption of the
%preceding section.  Substituting into the expression for $t_{decode}$,
%we see that an $n$ word communication between two nodes requires time
%\begin{equation}
% t_{decode} = n \left ( \frac{(n_g+n_o)/r_i + 2/r_{wc}}{n_i} +
%	\frac{n_{ac}}{r_i} + \frac{2}{r_{rc}} \\
%       + \frac{1}{r_{rr}} + \frac{2}{r_{wc}} \right )
%\label{equ:cached}
%\end{equation}

%\subsection{Threshold, break--even, and speedup}

%Equations \ref{equ:uncached} and \ref{equ:cached} can help us answer
%the following questions: For a message assembly step that occurs many
%times at run--time, can decoding a precomputed address relation ever
%outperform simply recomputing it?  If so, how many times must the
%relation be reused before the decoding strategy wins?  Finally, what
%is the ultimate speedup of the decoding strategy over the recomputing
%strategy?

%Decoding can only be effective if we can assemble the message faster
%using the precomputed relation than by recomputing it on the fly. In
%other words, we require that
%\begin{displaymath}
%t_{ac} < t_g + t_{au}
%\end{displaymath}
%or
%\begin{equation}
%% r_{rc} > \frac{2r_i}{n_g+n_{au}-n_{ac}}
%n_g > \frac{2r_i}{r_{rc}} + n_{ac}-n_{au}
%\label{equ:necessary}
%\end{equation}
%The right hand side of Equation (\ref{equ:necessary}) is a
%machine--specific {\em threshold} below which decoding precomputed
%address relations is ineffective. Notice that threshold is largely
%determined by the ratio of instruction issue rate and memory read
%bandwidth.

%If (\ref{equ:necessary}) is true, then we can also predict
%how many times the address relation must be decoded in order to
%break--even with recomputing on the fly.  This {\em break--even} point
%is found by setting $t_{decode} = t_{recompute}$ and solving for
%$n_i$.  In doing this we find that the break--even point is
%\begin{equation}
% n_i = \left \lceil \frac{r_{rc}}{r_{wc}} \left (
%           \frac{(n_g+n_o)r_{wc} +
%           2r_i}{(n_g+n_{au}-n_{ac})r_{rc}-2r_i} \right ) 
%\right \rceil 
%\label{equ:crossover}
%\end{equation}
%It is important to point out that as $n_g$ moves away from the
%threshold, the break--even point decreases sharply because the $n_g$
%terms begin to dominate. 

%Finally, the ultimate speedup of decoding versus recomputing is
%\begin{equation}
%\label{equ:speedup}
%\frac{t_g+t_{au}}{t_{ac}} = \frac{r_{rc}r_{wc}r_{rr}(n_g+n_{au}) 
%              + r_ir_{rc}(r_{wc}+2r_{rr})}
%             {r_{rc}r_{wc}r_{rr}n_{ac} + r_ir_{rc}(r_{wc}+2r_{rr})}
%\end{equation}
%The speedup is linear in $n_g$, so is bounded only by the complexity 
%of the address computation.

%\subsection{Validation on iWarp and Paragon}

%This section validates the break--even and speedup models using
%measurements from message assembly loops running on the Intel iWarp and
%Paragon system.  For each system, the threshold is defined, so we use
%(\ref{equ:crossover}) to predict the number of iterations necessary
%for the decoding approach to break--even with the recomputing approach, as
%a function of $n_g$, and we use (\ref{equ:speedup}) to predict the
%ultimate speedup of the decoding approach over the recomputing
%approach, also as a function of $n_g$.  In each case, the address
%relation is the identity relation, the encoding scheme is \AAPAIR, and
%$n_g$, the number of instructions to compute the relation, is varied
%by inserting nops into the code stream.  The predictions are then
%compared to actual measurements on the hardware.

%For the iWarp system, $r_{rc}=r_{rr}=r_{wc}=r_{wr}=10^7$ words/second,
%and a node can execute $r_i=2 \times 10^7$ instructions/second.
%Specifically, the iWarp clock speed is 20 MHz and all memory
%operations complete in two cycles.  There is no cache and we assume no
%dual dispatch of loads and stores.

%The implementation parameters ($n_{au}$, $n_o$, and $n_{ac}$) can be
%estimated {\em statically} by simply counting the number of
%instructions in each loop, or {\em dynamically} by accounting for
%bypass stalls that arise in the loops. The static estimates for iWarp
%are $n_{au}=5$, $n_o=6$, and $n_{ac}=2$. The dynamic estimates are
%$n_{au}=7$, $n_o=8$, and $n_{ac}=3$.

%Figure~\ref{fig:iw}(a) shows the measured and predicted number of
%iterations needed on iWarp for the message assembly latency of the
%decoding scheme to break even with that of the recomputing scheme for
%different $n_g$.  Entries with ``-'' denote that the value is
%undefined (i.e., $n_g$ is below the threshold). The predictions made
%using the dynamic measurements are exact.  The predictions made using
%the static measurements are pessimistic for small $n_g$, but quickly
%converge to the actual numbers as $n_g$ increases. Notice also
%that the predicted threshold (using the dynamic estimates) is
%only one instruction cycle!

%\begin{figure*}[htbp]
%\centering
%\small
%\begin{tabular}{cc}
%\begin{tabular}{|c|c|c|c|} 
%\hline
%\multicolumn{4}{|c|}{Break-even}\\ 
%\hline
%$n_g$       & Actual         & Predicted         & Predicted \\
%            &                & (static)          &  (dynamic) \\    
%\hline
%   1        &         13     &        -         &        13 \\
%   2        &         7      &         12        &        7\\
%   3        &         5      &          7        &        5\\
%   4        &         4      &          5        &        4\\
%   5        &         4      &          4        &        4\\
%   6        &         3      &          4        &        3\\
%   7        &         3      &          3        &        3\\
%   8        &         3      &          3        &        3\\
%\hline
%\end{tabular} 
%&
%\begin{tabular}{|c|c|c|c|} 
%\hline
%\multicolumn{4}{|c|}{Speedup}\\ 
%\hline
%$n_g$       & Actual         & Predicted         & Predicted \\
%            &                & (static)          &  (dynamic) \\    
%\hline
%   1       &         1.05    &         1.00     &         1.07 \\
%   2       &         1.12    &         1.09     &         1.15 \\
%   3       &         1.22    &         1.16     &         1.23 \\
%   4       &         1.28    &         1.25     &         1.32 \\
%   5       &         1.35    &         1.33     &         1.39 \\
%   6       &         1.43    &         1.41     &         1.47 \\
%   7       &         1.49    &         1.49     &         1.54 \\
%   8       &         1.59    &         1.59     &         1.61 \\
%\hline
%\end{tabular}\\
%(a) & (b) \\
%\end{tabular}
%\caption{(a) Break--even (Eqn. \protect{\ref{equ:crossover}})
%and 
%(b) speedup (Eqn. \protect{\ref{equ:speedup}}) on iWarp
%}
%\label{fig:iw}
%\end{figure*}

%Figure~\ref{fig:iw}(b) compares the actual and predicted speedup of
%the decoding scheme over the recomputing scheme on iWarp. As in
%Figure~\ref{fig:iw}(a), the dynamic predictions are quite close for
%all $n_g$ and the static predictions are pessimistic for small $n_g$.
%However, it is important to note that even with static measurements,
%the predictions only become inaccurate when $n_g$ approaches the
%threshold.  Another important point is that the purpose of
%Figure~\ref{fig:iw}(b) is to help validate the models when $n_g$ is
%small, and not to highlight impressive speedups. In fact, the speedups
%grow arbitrarily large as $n_g$ increases (see
%Equation~\ref{equ:speedup}.)

%A Paragon node contains a 50 MHz pipelined, multiple issue RISC node.
%We can estimate the instruction issue rate by noting that we do not
%use the floating point pipeline.  Therefore we can issue at most
%$r_i=5 \times 10^7$ instructions/second.  We directly measured the
%memory parameters and found $r_{rc}=9 \times 10^6$ words/second,
%$r_{wc}=8.2 \times 10^6$ words/second, and $r_{rr}=r_{wr}=0.9 \times
%10^6$ words/second.  Only a static measurement (instruction counting)
%of the implementation properties was performed, which found
%$n_{au}=6$, $n_o=7$, and $n_{ac}=11$.

%Figure~\ref{fig:86}(a) shows, for different $n_g$, the measured and
%predicted number of iterations needed for decoding to break even with
%recomputing.  The predictions are pessimistic, but quickly converge to
%the actual values with increasing $n_g$.  Notice that $n_g$ must be
%much larger to permit break--even on the Paragon than on the iWarp.  The
%predicted threshold is 17 instructions/tuple and the actual
%threshold is 16 instructions/tuple.  This is not surprising given
%that the Paragon's instruction issue rate is much higher than its
%memory bandwidth, while the iWarp's issue rate is well matched to its
%memory bandwidth.

%\begin{figure}[htbp]
%\centering
%\small
%\begin{tabular}{cc}
%\begin{tabular}{|c|c|c|} 
%\hline
%\multicolumn{3}{|c|}{Break--even}\\ 
%\hline
%  $n_g$ & Actual & Predicted \\
%        &        & (static) \\
%\hline

%    14     &        -    &        -\\
%    15     &        -    &        -\\
%    16     &        19      &        -\\
%    17     &        11      &        41    \\     
%    18     &         9      &        20\\
%    19     &         7      &        14\\
%    20     &         6      &        11\\
%    21     &         5      &         9\\
%    22     &         5      &         7\\
%    23     &         4      &         7\\
%    24     &         4      &         6\\
%    25     &         4      &         5\\
%\hline
%\end{tabular}
%&
%\begin{tabular}{|c|c|c|} 
%\hline
%\multicolumn{3}{|c|}{Speedup}\\ 
%\hline
%  $n_g$ & Actual & Predicted \\
%        &        & (static) \\
%\hline
%    14     &        -   &         -\\
%    15     &        -   &         -\\
%    16     &       1.03     &         -\\
%    17     &       1.06     &         1.01\\
%    18     &       1.09     &         1.02\\
%    19     &       1.12     &         1.03\\
%    20     &       1.15     &         1.04\\
%    21     &       1.17     &         1.05\\
%    22     &       1.20     &         1.06\\
%    23     &       1.22     &         1.07\\
%    24     &       1.24     &         1.08\\
%    25     &       1.26     &         1.09\\
%\hline
%\end{tabular}\\
%(a) & (b) \\
%\end{tabular}
%\caption{(a) Break--even (Eqn. \protect{\ref{equ:crossover}})
%and 
%(b) speedup (Eqn. \protect{\ref{equ:speedup}}) on Paragon
%}
%\label{fig:86}
%\end{figure}

%Figure~\ref{fig:86}(b) compares the actual and predicted speedup of
%decoding over recomputing on the Paragon. Notice that speedup does not
%increase as quickly with $n_g$ as on the iWarp
%(Figure~\ref{fig:iw}(b).)  This is the result of the lower memory
%bandwidth relative to instruction issue rate on the Paragon.  The
%predictions are not as accurate as for the iWarp, reflecting the fact
%the Paragon's memory system is more complex.  However, the predictions
%are pessimistic and quickly converge to the correct values.

%The significant lesson we can learn from the models developed in this 
%section is that the threshold for the decoding approach is quite low 
%(1 instruction/tuple on the iWarp and 16 instructions/tuple on the 
%Paragon).  In practice, the time to recompute the relation on the fly 
%for simple and regular access patterns, such as those induced by 
%BLOCK($P$) and CYCLIC($P$) distributions, falls beneath this 
%threshold and communication based on either approach has roughly the 
%same performance.  However, as the access pattern becomes even 
%slightly less regular, communication performance using the decoding 
%approach becomes attractive.  For example, we have measured the time 
%to redistribute block--cyclic HPF arrays (including message 
%assembly/disassembly and the actual data transfers) and found that the 
%decoding approach was a factor of two faster than the recomputing 
%approach\footnote{A reference is not given here in order to 
%preserve anonymity. It will be included in the final paper}.


\section{Measured performance}
\label{sec:measure}

We have developed analytical models for predicting the performance of
the \AAPAIR
~encoding~\cite{AR-CACHING-LCR-INPROCEEDINGS,FAST-ASSEMBLY-ADDRESS-RELATIONS-TECHREPORT}.
These models show that the inspector/executor approach using \AAPAIR~
outperforms the recomputing on the fly approach in a surprising number
of instances.
%However, the \AAPAIR~encoding is quite memory--inefficient, requiring
%space proportional to the number of data items being assembled.  

Performance for the more compact encodings is difficult to model
analytically since it depends heavily on the access patterns in the
relation, unlike with the \AAPAIR ~encoding.  Instead, we directly
measured the performance of message assembly and disassembly on six
different machines.  For each machine, each encoding (\AAPAIR, \AABLK,
\DMRLE, and \DMRLEC) was measured on each of the four representative 
redistributions of Figure~\ref{fig:repdist}.  The performance measure
in all cases is the absolute copy throughput (in MBytes/sec) of the
assembly and disassembly routines.  By copy throughput, we mean the
number of MBytes that are packed into (unpacked out of) the message
buffer each second during message assembly (disassembly).  

%In this
%section we investigate the performance of message assembly and
%disassembly based on the more compact \AABLK, \DMRLE, and \DMRLEC~
%encodings.

The measurements are taken from {\bf ART} --- {\bf A}ddress {\bf R}elation
{\bf T}oolbox --- a portable library, entirely written in C and
designed to be used with a conventional message passing system based
on the {\em send/receive} model.  The address relations used are those
induced between source node zero and destination node zero for each of
the four representative block--cyclic redistributions of
Figure~\ref{fig:repdist}.  
%The reason for measuring node zero to node
%zero transfers is to guarantee that the largest address relation is
%used.
%, although the address relations between each pair of nodes are of
%identical size for the representative redistributions.  
The distributed array contains $1024
\times 1024$ 8-byte doubles, so the zero to zero relation assembly and
disassembly steps copy 512 KBytes.  A larger $2048 \times 2048$ array
(2048 KBytes assembled/disassembled) was also tested with only minor
changes in measured copy throughput.

The identical C code was compiled and measured on the DEC
3000/400~\cite{DEC-3000-JOURNAL}, the Intel
Paragon~\cite{PARAGON-XPS-MANUAL}, the IBM
RS/6000~\cite{RS6000-ARCHITECTURE-JOURNAL} 250, the IBM
SP-2~\cite{IBM-SP1}, and two
Pentium~\cite{PENTIUM-OVERVIEW-INPROCEEDINGS,PENTIUM-MICRO-JOURNAL} systems:
a Gateway Pentium 90, and a Micron Pentium 133.  The details of each
testing environment are given in Figure~\ref{fig:machines}.
\begin{figure*}[tbph]
\begin{center}
\small
\begin{tabular}{|l|l|l|l|}
\hline
Machine & Node &  Compiler & Operating System\\
\hline
DEC 3000/400 & Alpha (21064 \@ 133 MHz) & GNU C 2.6.3, DEC CC 3.11 
    & OSF/1 2.0 \\
Intel Paragon & i860 (i860XP \@ 50 MHz) & Intel C R4.5 & OSF/1 1.0.4 \\
IBM RS/6000 250 & PowerPC (601 \@ 80 MHz) & IBM XLC 1.3.0.4 & AIX 3.2 \\
IBM SP-2 & POWER2 (66 MHz) & IBM XLC 1.3.0.33 & AIX 3 \\
Gateway Pentium 90 & i386 (Pentium \@ 90 MHz) & GNU C 2.4.5 & NetBSD 1.0A \\
Micron Pentium 133 & i386 (Pentium \@ 133 MHz) & GNU C 2.4.5 & NetBSD 1.0A \\
\hline
\end{tabular}
\normalsize
\end{center}
\caption{Testing environments}
\label{fig:machines}
\end{figure*}
Figure \ref{fig:results} shows the results for the first four
machines, while Figure \ref{fig:results-pentium} shows the results for
the Pentium--based machines.  Each row shows the results for a single
machine.  Message assembly throughput is shown on the left and
disassembly throughput on the right.  Superimposed on each
graph are annotated lines that represent the throughput of the library
\verb.memcpy(). routine and the throughput of C-coded strided copies
of doubles.  A line annotated ``stride--$k$'' on an assembly graph
indicates the throughput of a copy loop that copies from a stride of
$k$ doubles to a stride of 1, while on a disassembly graph it
indicates the throughput of a copy loop that copies from a stride of 1
to a stride of $k$ doubles.
%\footnote{The final paper will also show
%stride--1024 measurements in each graph for comparison to the
%disassembly throughput of the transpose.} 
Each chart measures the absolute throughput on the same scale, so that
results can be compared across machines.  Except for the Pentium
machines (Figure~\ref{fig:results-pentium}), only the throughput of
the
\AAPAIR~(as a baseline) and
\DMRLEC~encodings are shown.  This is because the story is the same
for these machines: \DMRLEC~is always the fastest compact encoding;
\DMRLE~ has similar performance, and \AABLK~ is the slowest for all
but the first redistribution. The situation is more complex on the
Pentium machines, so the throughputs of all four encodings are shown.


\begin{figure*}[pthb!]
\begin{center}
\small
\begin{tabular}{cc}
Alpha - Assemble & Alpha - Disassemble \\
\epsfxsize 2.5in \epsfbox{alpha_assem.eps} & \epsfxsize 2.5in 
\epsfbox{alpha_disassem.eps} \\
Paragon - Assemble & Paragon - Disassemble \\
\epsfxsize 2.5in \epsfbox{i860_assem.eps} & \epsfxsize 2.5in 
\epsfbox{i860_disassem.eps} \\
RS/6000 - Assemble & RS/6000 - Disassemble \\
\epsfxsize 2.5in \epsfbox{ppc_assem.eps} & \epsfxsize 2.5in 
\epsfbox{ppc_disassem.eps} \\
SP-2 - Assemble & SP-2 - Disassemble \\
\epsfxsize 2.5in \epsfbox{pwr2_assem.eps} & \epsfxsize 2.5in 
\epsfbox{pwr2_disassem.eps} \\
\end{tabular}
\normalsize
\end{center}
\caption{Throughput (MBytes/sec) of message assembly and message 
disassembly using  \AAPAIR~ and \DMRLEC~ on DEC Alpha 3000/400, Intel Paragon,
IBM RS/6000, and IBM SP-2}
\label{fig:results}
\end{figure*}



The principle observation is that, for most of the machines, message
assembly and disassembly using the \DMRLEC~encoding operates at rates
that are at or close to the copy throughput possible for their memory
reference patterns.  The remainder of this section analyzes each
machine in turn.

On the DEC 3000/400, \DMRLEC~gives ideal assembly and disassembly
throughputs for all the test cases.  \DMRLEC~ benefits from the
separate load/store pipeline in the Alpha 21064
processor~\cite{ALPHA-MICRO-JOURNAL,DEC-ALPHA-21064-JOURNAL}. Even on
a load stall, integer instructions associated with \DMRLEC~can
continue to issue.
%\begin{figure*}[htbp]
%\begin{center}
%\begin{tabular}{cc}
%\epsfxsize 2.5in \epsfbox{alpha_assem.eps} & \epsfxsize 2.5in 
%\epsfbox{alpha_disassem.eps} \\
%(a) & (b) \\
%\end{tabular}
%\end{center}
%\caption{Throughput (MBytes/sec) of (a) message assembly and (b) message 
%disassembly using  \AAPAIR~ and \DMRLEC~ on DEC 3000/400}
%\label{fig:alpha}
%\end{figure*}


On a Paragon node (i860~\cite{I860-PR-MANUAL} processor),
\DMRLEC~gives near ideal assembly throughput for all the test cases, as
shown in Figure~\ref{fig:results}.  The disassembly results
are somewhat unexpected, however.  Although the first test case
(stride--1 writes) operates with ideal throughput, the third test case
(stride--4 writes) actually does slightly better than a stride--4 copy
loop.  We explain this due to different code generation on the part of
the compiler for the disassembly loop and the stride--4 copy loop.  As
can be seen by the factor of two difference between a compiler
generated stride--1 copy loop and the library \verb.memcpy().
routine, there is considerable room for improving on the stride--$k$
copy loops generated by the Paragon node compiler.
%\begin{figure*}[htbp]
%\begin{center}
%\begin{tabular}{cc}
%\epsfxsize 2.5in \epsfbox{i860_assem.eps} & \epsfxsize 2.5in 
%\epsfbox{i860_disassem.eps} \\
%(a) & (b) \\
%\end{tabular}
%\end{center}
%\caption{Throughput of message (a) assembly and (b) disassembly using
%\AAPAIR~and \DMRLEC~on Paragon}
%\label{fig:i860}
%\end{figure*}


The RS/6000 250 (PowerPC 601~\cite{PPC601-MICRO-JOURNAL}) also
achieves near ideal assembly and disassembly throughput with \DMRLEC.
The IBM XLC compiler has software-pipelined each of the assembly,
disassembly, and strided copy loops.
%\begin{figure*}[htbp]
%\begin{center}
%\begin{tabular}{cc}
%\epsfxsize 2.5in \epsfbox{ppc_assem.eps} & \epsfxsize 2.5in 
%\epsfbox{ppc_disassem.eps} \\
%(a) & (b) \\
%\end{tabular}
%\end{center}
%\caption{Throughput (MBytes/sec) of (a) message assembly and 
%(b) message disassembly using \AAPAIR~and \DMRLEC~on IBM RS/6000 Model 250}
%\label{fig:ppc}
%\end{figure*}

The throughput measurements of message assembly and disassembly using
\DMRLEC~on the IBM SP-2 are also close to ideal, tracking the 
throughput of the strided copy loops closely.  The IBM XLC compiler
has software--pipelined assembly, disassembly, and each of the strided
copy loops.  Because the
POWER2~\cite{POWER2-ARCH-INPROCEEDINGS,POWER2-PROCESSOR-INPROCEEDINGS}
processor, like the Alpha, can continue to issue integer instructions
while a load miss is being handled, instructions associated with
\DMRLEC~are free.
% We outperform memcpy() by about 5% and we are unsure why.

%\begin{figure*}[htbp]
%\begin{center}
%\begin{tabular}{cc}
%\epsfxsize 2.5in \epsfbox{pwr2_assem.eps} & \epsfxsize 2.5in 
%\epsfbox{pwr2_disassem.eps} \\
%(a) & (b) \\
%\end{tabular}
%\end{center}
%\caption{Throughput (MBytes/sec) of (a) message assembly and 
%(b) message disassembly using \AAPAIR~ and \DMRLEC~on IBM SP-2}
%\label{fig:pwr2}
%\end{figure*}

The performance of the Pentium systems is more complex than that of
the other machines, as can be seen in
Figure~\ref{fig:results-pentium}. On both machines, the assembly and
disassembly throughput of \DMRLEC~is lower than \DMRLE.  On the faster
Micron machine, only the first test case achieves copy throughput for
message assembly, and then only in the simple
\AABLK~encoding.      Message assembly and disassembly appear to
be instruction issue limited for \DMRLEC~on both machines.  Because the
ratio of memory copy bandwidth (as measured by \verb.memcpy().) to
instruction issue rate is higher on the Micron, it is not surprising
that it performs comparatively worse in message assembly and
disassembly using \DMRLEC.

We believe that three factors contribute to this behavior.  First, the
GNU C compiler does not support Pentium optimizations, so clearly, no
scheduling is done to improve the multiple issue rate.  Second, the
Pentium is both register starved and non--orthogonal.  There are a
significant number of instructions in the message assembly loop that
do nothing but move values associated with the compact encodings to
and from the appropriate registers for certain operations.  In other
cases, memory operands are used where registers would appear with a
larger register set.  Finally, although the latency of memory operands
is shortened by the on--chip cache, the cache is not actually dual
ported, but banked, so cache references can become
serialized.\footnote{We also compiled the library with Microsoft's
Visual C++ 2.2, which includes Pentium-specific optimizations, but saw
no difference in performance during informal tests.  This leads us to
believe that the architecture or memory system is the overriding
factor in the lack-luster performance of the Pentiums.} Note that even
with this complexity, \DMRLEC~always performs better than
\AAPAIR~on the Pentium.




%\begin{figure*}[htbp]
%\begin{center}
%\begin{tabular}{cc}
%\epsfxsize 2.5in \epsfbox{p90_assem.eps} & \epsfxsize 2.5in 
%\epsfbox{p90_disassem.eps} \\
%(a) & (b) \\
%\end{tabular}
%\end{center}
%\caption{Throughput (MBytes/sec) of (a) message assembly and (b) 
%message disassembly using \AAPAIR, \AABLK, \DMRLE, and \DMRLEC~ on 
%Gateway Pentium 90 system}
%\label{fig:p90}
%\end{figure*}
%\begin{figure*}[htbp]
%\begin{center}
%\begin{tabular}{cc}
%\epsfxsize 2.5in \epsfbox{p133_assem.eps} & \epsfxsize 2.5in 
%\epsfbox{p133_disassem.eps} \\
%(a) & (b) \\
%\end{tabular}
%\end{center}
%\caption{Throughput (MBytes/sec) of (a) message assembly and (b) message
%disassembly using \AAPAIR, \AABLK, \DMRLE, and \DMRLEC~on 
%Micron Pentium 133 system}
%\label{fig:p133}
%\end{figure*}



%\begin{figure*}[thbp!]
\begin{figure*}
\small
\begin{center}
\begin{tabular}{cc}
Pentium 90 - Assemble & Pentium 90 - Disassemble \\
\epsfxsize 2.5in \epsfbox{p90_assem.eps} & \epsfxsize 2.5in 
\epsfbox{p90_disassem.eps} \\
Pentium 133 -Assemble  & Pentium 133 - Disassemble \\
\epsfxsize 2.5in \epsfbox{p133_assem.eps} & \epsfxsize 2.5in 
\epsfbox{p133_disassem.eps} \\
\end{tabular}
\end{center}
\normalsize
\caption{Throughput (MBytes/sec) of message assembly and message
disassembly using \AAPAIR, \AABLK, \DMRLE, and \DMRLEC~on 
Gateway Pentium 90 and Micron Pentium 133 systems}
\label{fig:results-pentium}
\end{figure*}

\section{Discussion}
\label{sec:discuss}

%The preceding sections demonstrated that the decoding approach to
%message assembly can outperform the recomputing approach for many
%relations.  We introduced address relation encodings that
%significantly reduce the space required to store common address
%relations.  The message assembly and disassembly throughputs of these
%encodings were measured on several machines and found to be on par
%with the copy bandwidth.  
%In this section we describe other attractive attributes of the
%decoding approach, arguing that stored, encoded address relations are
%a powerful interface to communication systems.  Additionally, we note
%that even with compact address relations discussed in this paper, an
%address relation caching strategy could still be useful.


By taking address computation out of the critical path of data
transfer, the decoding approach makes message assembly throughput
depend on the address relation and the memory access pattern it
encodes instead of how the address relation is computed.  One
advantage of this is that it becomes easier to achieve reasonable
communication performance without a large number of special--case
optimizations in the compiler and run--time library.  Instead of
optimizing each address computation algorithm for each architecture,
only message assembly for each address relation encoding needs to be
optimized for each architecture in order for all data transfers to
benefit.

Another interesting property of the decoding approach is that the
entire relation is available to be optimized at a new level of the
software hierarchy.  For example, by ordering the relation by
destination node addresses first, we can optimize for reference
locality on the destination node instead of on the source node.  As
shown in ~\cite{STRICKER-OPT-MEM-PERF-COMM-INPROCEEDINGS}, the choice
is architecture--dependent and can have a significant impact on
performance.

Stored encoded address relations also appear to be a good interface
from user programs to the communication system because they are
implementation neutral.  This permits communication systems to be
highly specialized for the available hardware while still presenting
the same interface to the programmer or compiler.  However, to best
utilize the hardware, it may be necessary to change the encoding of
the address relation before using it.  For example, the relation may
be transformed into a DMA gather map on the source to make best use of
a network adapter such as the one described in~\cite{GNECTAR-IFIP}.
It is unclear whether this is the optimal approach, since the main
processor could presumably support better encodings than the network
adaptor. However, it is an intriguing possibility.

%
% This is new
%
%
Address relations could also be a powerful abstraction in the
interface {\em between} the layers of a communication system.
Consider a TCP/IP implementation where each layer merely added tuples
necessary to prepend its header to the packet instead of recopying it.
The data link layer could then simply gather the contents of the
packet directly to the wire.  With appropriate user-level semantics,
such a communication system could avoid all data copies.

Even with the compact address relation encodings described in this
paper, it is still useful to be able to bound the amount of memory
used to store address relations.  Address relations can still have
huge space requirements if they do not have regularity to exploit.
This leads naturally to a caching approach.  When the allotted
amount of memory is in use and a new relation needs to be stored, a
victim relation must be chosen and flushed from memory to make room.
User or compiler-supplied hints would be helpful to minimize cache
thrashing. For example, if the run--time system were told that a group
of relations were associated with the same collective communication
operation, then it might make sense to flush and restore these
relations as a group.  Another possibility is to publicize the
characteristics of the address relation cache so that compilers and
programmers can make reasonable choices, as with a memory cache.

Since address relations can be decoded at near copy throughputs on
most systems, it might be interesting to investigate using precomputed
address relations as the basis for a generalized form of
\verb.memcopy(). on uniprocessors.   An example application for such
a library routine could be bit block transfers (bit--blit) and
transfers of regions in graphical interfaces and games.


\section{Conclusions and open issues}
\label{sec:conclude}

This paper introduced the notion of an address relation for
describing data transfers between the nodes of a parallel system, and
it described how compact encoded forms of these relations can
serve as the basis for fast message assembly and disassembly.
%Analytic models and measurements on real systems suggest two main
%conclusions.  First, the threshold at which decoding precomputed
%address relations during message assembly and disassembly becomes
%effective is quite low, on the order of units or tens of instructions.
%Second, 
The main result is that
message assembly and disassembly based on decoding compact
address relations typically perform at near copy throughput for
the relations induced by redistributions of regular block--cyclic
distributed arrays.  A side effect is that the storage requirements for
these relations is drastically reduced to a practical level.

While the paper shows encouraging results for a carefully constrained
(but very useful) set of relations, it does not address the
fundamental question of how to characterize machines and address
relations so that we can decide whether to decode or recompute, and if
we decide to decode, what encoding of the relation to use. This issue
will become increasingly important for relations with irregular memory
reference patterns, since the potential benefit of decoding would seem
to be greatest for the irregular cases. It will be necessary to
understand how to encode and decode relations that are more irregular
than the relations described in this paper, as well as to understand
the performance impact of these encodings.  One motivating application
for these irregular relations is sparse matrix--vector multiplication
over irregular finite--element meshes.

Another avenue to explore is the design of more aggressive encoding
schemes such as the Huffman--based~\cite{HUFFMAN-CODES-JOURNAL}
\DMRLE~encoding mentioned in Section~\ref{sec:compact}. Another
possibility is to use LZW~\cite{LZ-JOURNAL,LZW-JOURNAL} or a variant
thereof for further compression.~\footnote{Early experiments with the
\verb.gzip.  LZW--based compressor show dramatic compression, but we
do not yet know if LZW--based decoding can be made to run at copy
throughput speeds.}

We are also interested in how much the performance of message assembly
and disassembly depends on single--node compilers.  Many parallelizing
compilers generate sequential source code and rely on the single--node
compiler to produce good results.  However, as can be seen from the
factor of two difference between a compiler--generated copy loop and
the library \verb.memcpy(). routine on the Paragon
(Figure~\ref{fig:results}), this reliance may be unwarranted.  If so,
then the decoding approach becomes more attractive since the assembly
routine for each encoding could be low--level coded for each
architecture. Such low--level coding would be probably be impractical
for the recomputing approach due to the many variants of assembly
routines.  Instead, a parallelizing compiler could precompute address
relations at compile--time, and rely on low--level coded library of
message assembly routines to achieve near copy throughput. In general
though, the appropriate interaction between a parallelizing compiler
and a run--time message assembly library based on decoding precomputed
address relations is not yet understood.


\comment{
\subsection*{ACKNOWLEDGEMENTS}

We would like to thank Thomas Stricker for illuminating the finer
points of deposit model communication, James Stichnoth for his work
and explanations of array assignments between regular block-cyclic
distributed arrays, and Ed Segall for providing the impetus to look
at run--time approaches to fast message assembly.
}



\small
\bibliography{/afs/cs/project/iwarp/member/pdinda/BIB/texbib,/afs/cs/project/iwarp/member/droh/bib/refs}

\end{document}
 