\section{Introduction}
\label{intro-sect}

% Add more motivation

The all-to-all personalized communication (AAPC) step is frequently
encountered in parallel programs. In an AAPC step, each processor
sends a block of data to every other processor, and every block of
data can potentially contain different information.  The AAPC step
occurs in multi-dimensional convolutions and in array transposes where
only one dimension of the array is distributed. Recent implementations
of data parallel compilers for High Performance Fortran\cite{hpf}
include directives for general {\em block-cyclic} array distribution.
Changing the distribution of an array often results in a communication
where all processors or nearly all processors exchange unique blocks
of data\cite{FX-COMMUNICATION}. The compiler can often detect when an
AAPC step is required, so compile time recognition of AAPC is a
reasonable assumption\cite{hinrichs-thesis-work}{\tt .}

Since AAPC steps are so prevalent, many algorithms have been developed
to perform AAPC efficiently, though implementations and performance
numbers for these algorithms are hard to find.  Most algorithms have
concentrated on machines with a hypercube
topology\cite{johnsson89,var92,take87,bokhari91}.  More recent work
has explored machines with a k-ary n-cube topology. In~\cite{var92}
Varvarigos and Bertekas propose a store and forward
algorithm. Theoretically, this algorithm optimally uses network
bandwidth. However, to utilize all network bandwidth, each node must
be able to source and sink four messages simultaneously, i.e. have
twice the memory bandwidth as incoming network bandwidth.  Horie and
Hayashi\cite{horie92} and Scott\cite{scott91} have proposed algorithms
that directly send blocks of data to their destinations.  These
messages are partitioned into contention-free phases. If these phases
are separated by global synchronization or some other method, this
approach also optimally uses the network bandwidth.  Bokhari and
Berryman\cite{bokhari92} present a hybrid approach for a
two-dimensional mesh that does not optimally use the network bandwidth
but requires fewer message start ups. This approach requires
additional buffer allocation and address calculation on the
intermediate nodes.

A number of recent parallel machines have been built with general
purpose processors and a routing backplane. The topologies of these
machines differ.  Thinking Machine's CM-5 architecture relies on a fat
tree topology, sends short messages and uses randomized routing to
deal with congestion\cite{CM5-NETWORK}.  The Intel Paragon
architecture uses a fast two-dimensional mesh connection and routes
long messages with a basic routing scheme\cite{PARAGON-XPS}.
Similarly, the Cray T3D uses fast interconnects linked to a three-dimensional torus and a virtual channel wormhole
router\cite{T3D-OVERVIEW}. The Fujitsu AP-1000 system uses a two-dimensional torus and has a large, structured buffer pool that
provides the mechanisms for virtual channel, wormhole routing and for
special routers like broadcast and AAPC.  The IBM SP-1 uses an
Omega-like, multistage switch with flexible but static
routing\cite{IBM-SP1}.

In spite of the differing interconnect topologies and technologies,
the communication architectures of these machines are quite similar.
They all use wormhole routing to keep the per-hop hardware latency
low. While some of these machines have special support for broadcast
communication, none of these machines have support specifically for
AAPC.

In~\cite{take91}, Take, Noguchi, and Yokota propose a {\em dragon
switch} for a multistage network that performs all communication as
AAPC steps. The dragon switch is reconfigured for the next message
when the tail of the current message has passed. This reconfiguration
can be safely performed with only local information by relying on the
AAPC structure.

We have studied the performance of various AAPC algorithms on
iWarp\cite{iwarp-general,iwarp-comm2}, a distributed memory computer
connected by a k-ary 2-cube or torus topology.  iWarp's communication
architecture includes many interesting features included or planned
for other systems, including program control of routing, block DMA
transfer, and low message overhead.

To be optimal, the AAPC phases proposed in~\cite{horie92}
and~\cite{scott91} must be carefully separated to preserve the
contention-free schedule. In this paper, we introduce a {\em
synchronizing switch} for torus networks based on the ideas of the
dragon switch for multistage networks described in~\cite{take91}.  The
synchronizing switch uses the structure of the AAPC phases
to perform this phase separation more efficiently
and scalably than globally synchronous methods.

We show how the synchronizing switch can be incorporated into a
standard wormhole routing communication architecture. With a small
addition to the routing hardware, many of today's distributed memory
machines can support optimal AAPC.

We implemented and evaluated a prototype of this AAPC architecture on
iWarp.  In this paper, we present our design and evaluation of this
synchronizing switch. We compare the synchronizing switch with a
message passing library that uses similar features of the
communication architecture.

In Section~\ref{opt-aapc-sect}, we describe the decomposition of of
AAPC into phases for the torus topology, the basic switching mechanism,
and we argue why a simple, local synchronizing switch primitive can
guarantee synchronization during the execution of our AAPC algorithm.
Section~\ref{msg-sect} describes an opposing approach that uses a
standard message passing library and relies on a randomized message
schedule.  Our experimental results are given in
Section~\ref{measure-sect}.  Finally, we present our conclusions in
Section~\ref{conc-sect}.















