\section{Introduction}

There is widespread interest in the engineering and scientific
communities in using parallel computers to solve larger problems than
were previously feasible. Many problems in computational science and
engineering can be modeled by partial differential equations.
Numerical approximation of these equations over the spatial domain of
interest by finite difference, finite element, or finite volume
methods gives rise to algebraic systems with large, sparse coefficient
matrices. Often, however, the nonzero structure is irregular,
as in problems with geometric complexity or differing
scales of resolution (typical of problems in solid and fluid
mechanics). In these cases, achieving maximum performance on
distributed memory parallel computers (which generally are limited in
both memory and communication resources) requires careful partitioning
of problems along with efficient placement of and routing between the
resulting subproblems. Such domain-based problems have an underlying
combinatorial graph with useful properties derived from its geometric
structure, among them the existence of small separators 
which can be used to partition the problem.  However, both the
placement of subproblems on the processors of a parallel computer and
the routing between them require detailed knowledge of
the target machine if maximum performance is to be obtained.

Multiplying a sparse matrix by a vector is a frequently-used inner loop
in many PDE solvers, such as Krylov subspace methods (e.g. conjugate
gradients) and other iterative methods.  There is a natural
combinatorial graph representation of this problem which reduces the
communication requirements of this multiplication to exchanging data
across all edges of the graph.  The unstructured meshes associated
with finite element calculations have underlying graphs with
embeddings in two or three dimensions already defined, which will in
general have small separators that may be used recursively to
partition these graphs into as many subgraphs as desired.  The
separator properties of the underlying graph in two or three
dimensions will give bounds on the load balancing characteristics
and communication
requirements of the resulting partition.

As was stated earlier, effective performance in placement and routing
requires careful attention to the properties of the target machines.
Our first target is the iWarp system at Carnegie Mellon 
\cite{iwarp,iwarp:arch}, whose
novel communication mechanism adds some interesting elements to the problem of
placement and routing.  Its communication mechanism, which
uses circuit-switched logical pathways multiplexed over each physical
channel, changes the measures we must consider when choosing a set of
routing paths.  In particular, the maximum congestion of a set of routing
paths is of far greater importance 
than its maximum dilation.  This allows us to draw a strong analogy
between the problem of placement and routing and
established work in the area of circuit layout \cite{Leighton,Lengauer},
and bring insights and techniques from this area to bear on our problem.
In addition, geometric information from the original problem
is helpful in the placement of subproblems.  
Preliminary experiments suggest that even relatively simple
heuristic approaches to placement and routing for these graphs that
take advantage of their geometric structure
perform nearly twice as well as the current placement and routing packages 
on iWarp \cite{assign} in terms of the quantity 
of routing resources required to route a given underlying graph.
We are also planning an implementation on the Connection Machine
CM-5 \cite{CM5,CM5network}.
