%
% Wrapper file for AAPC TR
%
\documentstyle[times,cmu-titlepage,11pt,twoside]{article}

\textheight = 8.5in
\textwidth = 6.1 in
\topmargin = -0.25 in
\oddsidemargin = 0.2 in
\evensidemargin = \oddsidemargin

\renewcommand{\floatpagefraction}{1}
\renewcommand{\topfraction}{1}
\renewcommand{\bottomfraction}{1}
\renewcommand{\textfraction}{0}
\def\intextsep{14pt}

\begin{document}

\input epsf

\def\figpath{./all.fig/}

\newfont{\helv}{phvr scaled 1000}
\newfont{\bh}{phvb scaled 1000}
%\def\helv{}
%\def\bh{}

\bibliographystyle{alpha}

\newtheorem{lemma}{Lemma}
\newtheorem{condition}{Condition}

\newlength{\caplen}
\setlength{\caplen}{\textwidth}
\addtolength{\caplen}{-1\parindent}


\title{An Architecture for Optimal All-to-All Personalized Communication}

\author{Susan Hinrichs, Corey Kosak, David R. O'Hallaron,\\
Thomas M. Stricker, and Riichiro Take$\ddag$}

%\author{Susan Hinrichs, Corey Kosak, David R. O'Hallaron,\\
%Thomas M. Stricker, and Riichiro Take}
\date{September, 1994}
\trnumber{CMU-CS-94-140}

\citationinfo{\begin{center}This report is an extended version of a paper that
appeared in SPAA '94.\end{center}}



\support{
This research was sponsored in part by the Advanced Research Projects
Agency/CSTO monitored by SPAWAR under contract N00039-93-C-0152, and in
part by the Air Force Office of Scientific Research under Contract
F49620-92-J-0131.}
\unmarkedfootnote{$\ddag$ Author's current address: Riichiro Take, Fujitsu
Laboratories Ltd., 1015 Kamikodanaka, Nakahara-ku, Kawasaki 211, Japan.
email: riro@flab.fujitsu.co.jp.
}

\disclaimer{
The views and conclusions contained in this document are
those of the authors and should not be interpreted as
representing the official policies, either expressed or
implied, of the U.S. Government.}

\keywords{All-to-all personalized communication, AAPC, 
communication architecture, complete exchange, Cray T3D, 
IBM SP1, iWarp, parallel systems, TMC CM5}

\thispagestyle{empty}

\abstract{
In all-to-all personalized communication (AAPC), every node of a
parallel system sends a potentially unique packet to every other node.
AAPC is an important primitive operation for modern parallel
compilers, since it is used to redistribute data structures
during parallel computations. As an extremely dense communication
pattern, AAPC causes congestion in many types of networks
and therefore executes very poorly on general purpose, asynchronous
message passing routers.

\indent We present and evaluate a network architecture that executes
all-to-all communication optimally on a two-dimensional torus.  The
router combines optimal partitions of the AAPC step with a self-synchronizing switching mechanism integrated into a conventional
wormhole router. Optimality is achieved by routing along shortest
paths while fully utilizing all links.  A simple hardware addition for
synchronized message switching can guarantee optimal AAPC routing in
many existing network architectures.

\indent The flexible communication agent of the iWarp VLSI component allowed
us to implement an efficient prototype for the evaluation of the
hardware complexity as well as possible software overheads.  The
measured performance on an $8 \times 8$ torus exceeded 2 GigaBytes/sec
or 80\% of the limit set by the raw speed of the interconnects.  We
make a quantitative comparison of the AAPC router with a conventional
message passing system.  The potential gain of such a router for
larger parallel programs is illustrated with the example of a two-dimensional Fast Fourier Transform.
}

\maketitle

%\input abstract

% Make sure text starts on RHS page.
\pagebreak[4]
{\pagestyle{empty}\vspace*{\fill}
\pagebreak[4]}

\setcounter{page}{1}

\newpage
\pagebreak

%\parskip=.5\baselineskip
%\setlength{\parskip}{.5\baselineskip}

%\begin{figure}[p]
%\end{figure}

\input intro
\input optaapc
\input patterns
\input dragon
\input dragon-correct
\input dragon-other
\input dragon-over
\input other
\input measure
\input conclusions
\input acknowledgements
\bibliography{./aapc}

\end{document}







