\section{Placement and Routing}

\subsection{Background}

In order to to perform each iteration of the conjugate-gradient
method for finite-element calculations we must now embed the weighted $p$-node
graph minor derived from the original graph and partition to the graph
representing the interconnection network of the target machine. To implement
an exchange of data across each edge of the original graph we must communicate
between each pair of adjacent nodes in the minor graph an amount of data
proportional to the weight of the edge between them.

For our purposes, an {\em embedding} of a weighted graph $G$ to a graph $H$
(an underlying processor network) is a mapping of the nodes of $G$ to the nodes
of $H$ (corresponding to an assignment of subproblems to processors) together
with a mapping of the edges of $G$ to paths in $H$
(corresponding to routing paths between processors containing
subproblems which need to communicate). We are only considering one-to-one
node 
mappings because our 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 $H$ corresponding
to edges in $G$, and its {\em congestion}, which is the maximum over all edges
in $H$ of the total weight of the edges in $G$ whose corresponding paths
contain that edge. (For our purpose the {\em load} of the mapping is no
importance because we only consider one-to-one mappings.)

The goal in keeping dilation and congestion low is to minimize the time
required for data exchanges, so the relative importance of these measures for a
particular machine is dependent on its communication mechanism and routing
support (e.g., store-and-forward versus circuit-switched/lockdown routing).
When we consider different machines, we also expect to discover additional
measures of the efficiency (or even feasibility) of embeddings that depend on
features specific to 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
Corp.  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 milliseconds per hop.
% what's this - I guessed... \mus/hop.  
iWarp systems are
2--dimensional tori of iWarp processors, ranging in size from 4 processors to
1024 processors.  All implementations are done on a prototype 64--processor
system at Carnegie Mellon that runs at half-speed.

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 2D torus, logical channels and pathways allow for logical
connection patterns such as rings, trees or point to point connections. 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 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 thusly does not interrupt the computation
agent.

From these characteristics of iWarp systems we can now derive our
measurements of efficiency of the embedding. Dilation is of minor importance
because of the pathways. Congestion is a very important measurement because
all pathways sharing a certain physical connection are multiplexed and the
total available bandwidth is limited. In addition to these traditional
measurements we have to face the fact that each iWarp processor
only supports up to 20 logical
channels at any point in time. So if we cannot limit the number of logical
channels needed to be at most 20, then we have to use dynamic setup
of connections (or a message passing system) which is slower than the static
setup of connections. This makes the {\em node congestion} of our embeddings
of paramount importance since it determines which style of connection setup to
use. (We are currently investigating whether there is a more efficient way to
incorporate precomputed routing patterns in our implementation.)

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 (and very regular) 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 Routing}

Because of the communication mechanism of the iWarp system, the congestion of
our embedding is more important than its dilation to the amount of time it
will take to communicate. This is analogous to the issues in Gate Array layout
(see \cite{Lengauer}). 
In Gate Array layout, the placement problem is an assignment
problem. Each gate in the netlist of the circuit has to be assigned to a set
of cells on the master that will implement this gate. In our context each
subtask (node) needs to be assigned to a processor. The routing 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 width can be chosen by
the layout procedure. In our context routing a connection in the layout
problem can be viewed as embedding an edge. Because we only have a limited
number of logical channels available we get a fixed uniform channel width.  We
used this analogy to bring some ideas from layout algorithms to our
heuristics for embedding the $p$-minor graph on the graph representing the
interconnection network of the parallel machine. In the following we will use
the placement for mapping of nodes and routing for mapping of edges.

For placement, it is clearly beneficial to take into account as much of the
geometric information given in the original problem as possible --- after all,
we are given a graph already embedded in two- or three-dimensional space
(often the first step in layout)!  One simple approach to placing
two-dimensional graphs in the grid is to simply halve the set of nodes
repeatedly, alternating vertical and horizontal cuts, and mapping the 64 nodes
to the torus in the natural way.  On the other hand, we can take advantage of
the structure in a deeper way by using the recursion tree from the
partitioning algorithm to map the nodes of the graph corresponding to the
blocks of the partition to the nodes 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 node weights and
cost functions in appropriate ways, routings with very good balance of
congestion across the network can be obtained.  We are currently experimenting
extensively with this method.

Preliminary experiments have shown that it is not likely that we will be able
to embed even the graph minors which are derived from two-dimensional
problems within the current numerical limits that would allow us to implement
our communication as a single set of static paths.  (Of course, this bodes ill
for three dimensions, where the average degree of the graph minors nearly
doubles!)  However, it seems that two sets of routing paths (one for each
direction of the bidirectional edges) will suffice in two dimensions, and
perhaps in three as well. In the meantime, other iWarp researchers are working
on ways to exchange sets of precomputed routing paths more efficiently than 
is currently possible, especially in cases such as ours where the communication
is tightly synchronized.



