\section{Placement and Routing}
\label{placement}

\subsection{Background}

Let $H$ be a graph which represents the interconnection network of the target
machine.  Once we have partitioned $G$ into subgraphs that correspond to
subproblems to be solved locally, and identified which subproblems will have
to communicate and how much information they will have to send to each other,
we must embed the resulting $p$-vertex weighted graph $G'$ into $H$.  To
implement the exchange of data across each edge of $G$, we must communicate
between each pair of adjacent vertices in the $p$-vertex graph $G'$ an amount
of data proportional to the weight of the edge between them.

For our purposes, an {\em embedding} of a weighted graph ${\cal G}$ into a
graph ${\cal H}$ (as distinguished from an embedding of a graph in two- or
three-dimensional space) is a mapping of the vertices of ${\cal G}$ to the
vertices of ${\cal H}$, corresponding to an assignment of subproblems to
processors, together with a mapping of the edges of ${\cal G}$ to paths in
${\cal H}$, corresponding to routing paths between processors which need to
communicate.  We are only considering one-to-one vertex mappings because our
first target machine does not support multi-tasking and our partitioning
approach already guarantees us load balancing. In general, the two most
important measures of the efficiency of such an embedding are its {\em
dilation}, which is the maximum length of the paths in ${\cal H}$
corresponding to edges in ${\cal G}$, and its {\em congestion}, which is the
maximum over all edges in ${\cal H}$ of the total weight of the edges in
${\cal G}$ whose corresponding paths contain that edge. (Since we are only
considering one-to-one mappings, the {\em load} of our embeddings will always
be one.)

The goal of keeping dilation and congestion low is to minimize the total time
required for communication, so the relative importance of these measures for a
particular machine is dependent on its communication mechanism and routing
method (e.g., store-and-forward versus circuit-switched routing).
When we consider different machines, we also expect to discover additional
measures of the efficiency (or even feasibility) of embeddings that depend on
specific features of their architectures.

\subsection{The iWarp System}

Our first target machine is the iWarp system. 
The iWarp system is based on a single chip VLSI processor
\cite{iwarp,iwarp:arch} developed jointly by Carnegie Mellon and Intel
Corporation.  The iWarp component contains a {\em computation agent}, and a
{\em communication agent} for transferring data to and from other iWarp
processors.  Computing rates up to 20 Megaflops and 20 MIPS per cell are
possible in the computation agent. The communication agent can sustain a
bandwidth of 320 Megabytes/second per cell with a latency of 0.2 microseconds
per hop. iWarp systems are 2-dimensional tori of iWarp processors, ranging in
size from 4 to 1024 processors.  All implementations are done on a prototype
64-processor system at Carnegie Mellon.

iWarp processors communicate with neighboring processors over structures
called {\em logical channels}, which can be chained together to form {\em
pathways} \cite{iwarp:arch}. Although the physical connection pattern of the
iWarp is a 2-dimensional torus, logical channels and pathways allow for logical
connection patterns such as rings, trees, or even hypercubes \cite{Stricker}.
A network of logical channels can be created statically at compile time or
created and destroyed dynamically at runtime. Each iWarp processor can support
at most 20 logical channels incident to it at any point in time. (Note that a
logical channel is a unidirectional communication medium.)  Since pathways are
handled completely by the communication agent the delay at each processor
along such a pathway is very small, and data communicated thus does not
interrupt the computation agent.

From these characteristics of iWarp systems we can now discuss some
measurements of the efficiency of embeddings.  Dilation is of minor importance
because of the low latency of the pathways.  Congestion is a very important
measurement because all pathways sharing a certain physical connection are
multiplexed over that link, and the total available bandwidth is limited to 40
Megabytes/second per physical channel. In addition to these traditional
measurements we have to face the fact that each iWarp processor can only
support up to 20 logical channels at any point in time.  Therefore if we
cannot limit the number of logical channels needed to be at most 20, then we
have to use dynamic setup of pathways, which
is slower than the static setup of pathways. This makes the {\em vertex
congestion} of our embeddings, defined for each vertex
in the target graph $H$ as
the total number of paths in $H$ (that correspond to edges in $G'$) that are
incident to that vertex,
of paramount importance since it determines which style
of pathway setup to use. (We are currently investigating whether there are
more efficient ways to implement precomputed routing patterns which require
more than 20 logical channels per processor.)

We have implemented code for the iWarp system to solve a second-order
time-varying equation used for earthquake simulation, with encouraging
results.  This code uses a mesh which has been manually element-partitioned
to allow the use of static pathways.

Code for the direct solution of a three-dimensional finite element problem is
currently running on the iWarp, but it was designed for one specific
block-structured three-dimensional grid.  The next step is to modify this code
to handle more general and useful irregular grids in two and three dimensions.

\subsection{Approaches to Placement and 
\newline Routing}

Because of the communication mechanism of the iWarp system, the congestion of
our embeddings are more important than their dilation to the amount of time it
will take to communicate the needed messages.  This is analogous to some of
the issues considered in Gate Array layout (see \cite{Lengauer}), where the
placement problem reduces to an assignment problem.  In the Gate Array layout
problem, each gate in the netlist of the circuit has to be assigned to a set
of cells on the master that will implement the gate.  In our placement
problem, each subtask needs to be assigned to a processor.  The routing
problem between gates in the Gate Array layout problem is characterized by the
fact that the routing channels on the master have a fixed width (often the
same over the whole chip).  This is in contrast to standard-cell and
full-custom layout, where the channel widths can be chosen by the layout
algorithm.  Routing a connection in the layout problem is analogous to
embedding a graph edge in the processor network.  The limited number of
logical channels is analogous to the fixed uniform channel width in the Gate
Array layout problem.  We use the analogy between these problems to bring some
ideas from layout algorithms to our heuristics for embedding the $p$-vertex
weighted graph of subproblems into the graph representing the interconnection
network of the target machine.  Placement corresponds to the mapping of
vertices to vertices, and routing to the mapping of edges to paths.

For placement, it is clearly to our advantage to take into account as much of
the geometric information given in the original problem as possible.  After
all, the first step in layout is often to come up with an embedding of the
graph in the plane, and $G$ is given to us already embedded in
two- or three-dimensional space.  One simple approach to placing
two-dimensional graphs in the grid is to simply halve the set of vertices
repeatedly with alternating vertical and horizontal cuts, and map the 64
vertices to the torus in the natural way.  On the other hand, we can take
advantage of the structure of the graph in a deeper way by using the recursion
tree from the partitioning algorithm to map the $p$ vertices of the graph of
partition blocks to the vertices of the torus.  There are many other heuristics
for this placement problem, including simulated annealing and distance
minimization, which we continue to investigate.

There are also a variety of approaches which can be taken for routing the
needed connections.  The simplest are one- and two-bend routing schemes with
or without randomization, but algorithms using weighted shortest paths to
minimize congestion seem to work considerably better. By rerouting paths which
pass through areas of high congestion and varying the vertex weights and cost
functions in appropriate ways, routings with very good balance of congestion
across the network can be obtained.  Local optimization heuristics yield
further improvements.  We are currently experimenting extensively with these
methods.

Preliminary experiments have shown that it is not likely that we will be able
to embed even the weighted graphs which are derived from partitions of
two-dimensional problems within the current numerical limits that would allow
us to implement our communication as a single set of static paths.  This does
not bode well at all for three-dimensional problems, where the average degree
of the weighted graphs is nearly double.  However, in two dimensions it seems
that in general we can divide up the communication into two sets of statically
routable paths (as it turns out, simply putting one orientation of each
bidirectional edge into each set will work).  Two sets may suffice for three
dimensions as well, but this requires more study.  iWarp researchers are
currently studying the question of how efficiently one can switch between
precomputed sets of routes such as these when the communication phases are
tightly synchronized.

\subsection{The Connection Machine CM-5}

Our next target machine is the Connection Machine CM-5
\cite{CM5,CM5network}. The CM-5 is made up of SPARC 
microprocessors with optional
vector units which are connected by three different interconnection networks:
the data network (organized as a fat-tree \cite{L} with processors at
the leaves), the control network, and the
diagnostic network. The data network provides a high-bandwidth network (up to
20 Megabytes/sec at each processor) that supports
message-based,
point-to-point communication.  Sending a message over the network requires no
special routing decisions by the user. 
The fat-tree network is best suited for communication patterns with
hierarchical locality.  
\iffalse
It supplies the highest per-processor
bandwidth within clusters of four processors, a slightly lower
per-processor bandwidth within clusters of 16, and the lowest
per-processor bandwith across the root of the fat-tree.  
\fi
Communication
patterns that take advantage of locality run up to four times faster
than random patterns with the same total throughput.
The control network supports the
data-parallel programming model as well as efficient primitives for
synchronization,
broadcast and scan.

To solve PDEs, we need to embed the $p$-minor graph $G'$ into
the data network. Because the network hardware takes care of the routing
via a randomized algorithm \cite{GL}, we do
not need to specify the embedding of the edges, 
but only need to map the vertices of
$G'$ to the target fat-tree in a way that will
enable the hardware to find efficient routings.

Because fat-tree topologies do not have the same bandwidth on all their
communication links, a general guideline to optimize the efficiency of the
routing of a certain communication pattern is to keep all point to point
communication as local as possible.
This means that it is important to keep the
number of messages passing through any switch proportional
to the available capacity.  The
quality of a placement of $G'$ on a fat-tree $F$ is
measured by how well its communication requirements match the actual capacity
limitations of the fat-tree. 

It is clear how to use the separator results to obtain a natural
and fairly efficient placement.
During partitioning of $G$, we
derive a binary {\em cut tree} $T$, 
which is the recursion tree of the partitioning 
algorithm.
The leaves of $T$ represent the vertices of $G'$. 
We can collapse alternate levels of $T$ to obtain a 4-ary tree whose
structure matches that of the fat-tree of the data network, and embed this
tree into the fat-tree in the natural way.  Due to the properties of the
geometric separators and the fat-tree network, this mapping should yield
reasonably good results.
We are interested in seeing how 
locality concerns affect the performance of our implementation.

We intend to analyze the time spent on
computation and communication (once the optional vector units are available
to us), and compare the efficiency and simplicity of the CM-5's
data-parallel and MIMD programming models against each other and
the iWarp MIMD implementation.   


