\section{Introduction}

There is widespread interest in the engineering community
in using parallel computers to solve larger problems in scientific
computing (e.g., earthquake modeling, stress analysis) than were
previously feasible.
However, 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.
Many scientific computing problems have an
underlying combinatorial graph with useful properties derived
from its geometric structure, among them the existence of small 
separators of the underlying which can be used to partition the problem.
The placement of subproblems on the processors of a parallel computer and
the routing between them, however, require more detailed knowledge of the
target machine is maximum performance is to be obtained.

Multiplying a sparse matrix and a vector is frequently-used
inner loop in many problems in scientific computation, such as the
conjugate-gradient method for finite-element calculations 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 which that be used recursively to 
partition these graphs into however many subgraphs are desired.
The separators properties of the underlying graph in two or three
dimensions will give bounds on the load balancing 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 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
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.

