\section*{Placement and Routing}

The result of partitioning is the quotient graph $E'$, which
describes the communication pattern among the processors
during matrix-vector multiplication.
$E'$ should be embedded into the parallel
architecture $H$ such that the communication time is minimized.
The notion of a good embedding thus depends on the target machine.

We consider two communication models.  With {\em message passing}, all
routing decisions are made by the message passing system, and these
decisions are hidden from the application.
We also consider a connection-based model called the {\em ConSet
model}.  The set of interprocessor connections we need is broken up into
a small number of {\em phases}, only one of which is
active at a time.  A phase consists of a
subset of connections that can be made simultaneously
by the available hardware resources; the
application controls which phase is instantiated at any given time.
A connection can be used only if it belongs to the phase that is currently
active.
For detailed discussion,
see Feldmann, Stricker, and Warfel~\cite{feldmann93}.

The advantage of message passing is that no explicit routing need be done.
The advantage of the ConSet model is that, because the structure
of $E'$ is known in advance, a {\em communication compiler}
can choose routes and schedule communication so as to
minimize network congestion.

We discuss below two of
our target machines, the iWarp and the Connection Machine
CM-5, and how to embed
$E'$ into them.  Our heuristics are inspired by algorithms from VLSI gate
array layout~\cite{lengauer90}.

\section*{Placement and Routing on the iWarp}

Our first target machine is the iWarp~\cite{borkar88}. The iWarp is
a distributed memory parallel computer whose processors are connected
by a two-dimensional torus.  The iWarp component is a VLSI chip that
contains a {\em processing agent} and a {\em communication agent}.  At
the heart of the communication agent is a limited set of communication
resources called {\em queues}.  Queues on adjacent processors
can be dynamically
chained together to form {\em pathways}, which are point-to-point
connections formed between processors to
implement wormhole routing.  Data
traveling along a pathway passes from processor to processor
automatically, with low latency,
without disturbing the computations on intermediate
processors.  A pathway consumes a queue on each processor it passes through,
including the processors at each end of the pathway.
These ideas are illustrated in Figure~\ref{pathways}.

\begin{figure}
\centerline{\epsfbox{pathways.eps}}
\caption{\label{pathways}
iWarp communication structures.  Pathways are constructed by linking together
queues.  Processor 0 can send data to
processor 2 without interfering with the computation on processor 1.}
\end{figure}

Because the number of queues per processor is limited,
in general not all desired connections can be
routed simultaneously.  One way to address this problem is to use a
simple message passing system:  a pathway is dynamically set up
between the source and destination, the data is transmitted,
and the pathway is taken down to free up queues to be used for other
messages.  We have also implemented ConSet communication on the iWarp,
which requires explicit routing but offers better performance.  We shall
address routing for ConSet in detail.

The characteristics of the iWarp's routing mechanism
affect the efficiency of embeddings.
Dilation is of minor importance because of the low latency of the
pathways. Congestion is an important measure because all
pathways sharing a communication bus are multiplexed over that link.
In addition to these traditional measurements, we must address the
constraint that a limited number of pathways can touch any particular
processor at any particular point in time. This makes the {\em vertex
congestion} of our embeddings, defined for each vertex in the target
graph $H$ as the total number of connections routed out of, through,
or into that vertex, of paramount importance.

For placement, as with partitioning,
it is to our advantage to take into account
the geometric information given in the original problem.
We assign each node of $E'$ a coordinate in
two- or three-dimensional space by computing the center of mass
of each subdomain (as illustrated in Figure~\ref{quotient}).
If our problem is three-dimensional, we project $E'$ to two
dimensions to match our processor topology.
One simple approach to placing a two-dimensional graph on the iWarp,
or any two-dimensional mesh topology,
is to simply halve the set of vertices repeatedly with alternating
vertical and horizontal cuts (Figure~\ref{place}),
and map the vertices to the torus in the natural way.
We further improve the placement with local hill-climbing search:  we try
swapping pairs of subdomains, and accept the swap if it reduces the sum of
all connection lengths.

\begin{figure}
\ifcolor
  \centerline{\epsfxsize=4in \epsfbox{place.color.eps}}
\else
  \centerline{\epsfxsize=4in \epsfbox{place.eps}}
\fi
\caption{\label{place}  A succession of horizontal and vertical cuts defines
the placement of the quotient graph on an $8 \times 8$ grid.}
\end{figure}

To route for the ConSet model, we must address two problems. First, each edge
of $E'$ must be assigned to one phase, during which its connection will be
active.  We would like to use as few phases as possible, as there is a cost 
associated with switching between phases.
Second, each phase's set of connections must be routed with a fixed
number of queues per processor and with minimal congestion.
We solve both problems together using sequential routing techniques based on
weighted shortest path algorithms.

To find a routing schedule that uses $k$ phases, we proceed as follows:

First, we sort all connections, from longest to shortest, based on the
distance in $H$ from source to destination.  Each vertex of $H$
(in each of the $k$ phases) is assigned
an initial cost of one.  We define the {\em length}
of a path between two vertices in
$H$ in a particular phase
to be the sum of the costs of the vertices along the path in that phase.
Second, we attempt to route the connections, one by one.
In each of the $k$ phases, a shortest
path from the source to the destination within that phase
is found, and the path is assigned to whichever phase yields the shortest
path overall (Figure~\ref{route}).
Each time a connection is successfully routed, the cost of
each vertex along its path in its assigned phase is increased.  
(The increase is nonlinear, and
the cost of a vertex whose queues are all used is infinite.)

\begin{figure}
\ifcolor
  \centerline{\epsfxsize=4in \epsfbox{route.color.eps}}
\else
  \centerline{\epsfxsize=4in \epsfbox{route.eps}}
\fi
\caption{\label{route}  Connections are routed by finding the path of
least cost from among the communication phases.  The cost of each processor is
shown; the cost of a processor
increases nonlinearly with the number of connections through that processor.}
\end{figure}

If all connections can be routed this way (this may not be the case, if the
number of phases $k$ we are considering is too small), 
we have found a solution.  However, it may not be a good one, 
because the quality depends on the order in which
connections are routed.  Whether or not all connections are successfully
routed, the communication compiler tries to improve the routing with a 
``ripup and reroute'' stage.  In this stage,
routes are repeatedly selected at random to be ripped up,
and the vertex costs along their paths are updated after their removal; 
the removed connections are then rerouted using the shortest paths
algorithm, often along less congested routes and possibly even in a different
phase.
During this
stage it is often possible to find a route for a previously unroutable 
connection.

Since the shortest paths routing algorithm is quite fast, we try
to keep the number of phases low by first running the algorithm with only
one phase (that is, with $k = 1$).  If the algorithm fails to route all the
connections in just one phase, then we increase the value of $k$ to $2$, and
run the algorithm again.  We continue increasing $k$ until the algorithm
succeeds in routing all the desired connections in $k$ phases.
When routing is complete, a schedule is generated that describes
a good order in which to exchange messages during each phase.  The placement,
routing, and scheduling heuristics are all described in detail
by Feldmann et al.~\cite{feldmann93}.

\begin{figure}
\ifcolor
  \centerline{\epsfxsize=5.5in \epsfbox{2phase.color.eps}}
\else
  \centerline{\epsfxsize=5.5in \epsfbox{2phase.eps}}
\fi
\caption{\label{routing}  Interprocessor connections on a 64-processor iWarp
for the quotient graph $E'$.  Two communication phases are required.}
\end{figure}

Figure \ref{routing} illustrates the quotient graph of
Figure \ref{quotient}, placed and routed on a 64-processor iWarp
by our algorithms.
We have tried other heuristics for placement and routing,
including simulated annealing and linear programming, but they
have not performed as well.

\section*{Placement on the Connection Machine CM-5}

Another target machine is the Connection Machine CM-5~\cite{tmc91}.
The CM-5 is a distributed memory parallel
computer whose computational nodes are connected by a fat-tree
network~\cite{leiserson92}.
The network supports message passing
communication, as well as efficient primitives for
synchronization, broadcast, and scan.
The network topology, a
fat-tree, is best suited for communication patterns with hierarchical
locality.  The network is organized such that groups of 4
processors have the highest bandwidth among themselves, groups of 16
processors have a slightly lower bandwidth, and anything past a 16
processor boundary has yet a lower bandwidth.

This hierarchical locality of a fat-tree is well suited for
recursive bisection partitioners, as the separators give a
hierarchical decomposition.  While partitioning $E$, we derive a
binary {\em cut tree} $T$, which is the recursion tree of the
partitioning algorithm.  The leaves of $T$ represent the subdomains
(vertices of
$E'$).  We can collapse alternate levels of $T$ to obtain a 4-ary tree
whose structure matches that of the fat-tree network, and embed
this tree into the fat-tree in the natural way.
Because the network hardware
takes care of routing, we do
not need to specify an embedding of the edges.
