\section*{Parallelizing Sparse Matrix-Vector Products}

To compute ${\bf y = Kx}$ on a set of processors, we must consider
the data distribution by which vectors and matrices are stored.
Although one might divide the set of nodes among the processors, it
is more natural in finite element methods to partition elements.
Each element of the mesh is assigned to a processor, and
each mesh node resides on one or more processors, depending on
which elements contain that node.
The vectors ${\bf x}$ and ${\bf y}$ are stored in
a distributed fashion according to this mapping.  If a node $i$ resides
on several processors, the values $x_i$ and $y_i$ are replicated on those
processors.  The matrix ${\bf K}$ is distributed so that $K_{ij}$ resides
on any processor on which nodes $i$ and $j$ both reside.
Figure~\ref{cutmatrix} demonstrates this method of distributing data.

\begin{figure}
\centerline{\epsfbox{cutmatrix.ps}}
\caption{\label{cutmatrix} Finite element mesh distributed among two
processors.  Each processor holds a subset of the elements and nodes;
some nodes are mapped to more than one processor.  Each processor maintains
a {\em processor stiffness matrix}, which is a portion of the global
stiffness matrix.  X's indicate nonzero matrix entries.}
\end{figure}

The multiplication ${\bf y = Kx}$ is performed in two steps.  First, each
processor computes a local matrix-vector product over the subgraph of $G$
that resides on that processor.
Second, processors that share nodes communicate and
combine their nodal {\em y} values into correct global values for each node.
In Figure~\ref{cutmatrix}, Processors 1 and 2 must communicate to resolve
the values of the shared nodes 4, 5, and 6.

The data distribution is defined by embedding the
element adjacency graph $E$ into a graph $H$,
which represents the underlying
interconnection network of the target
machine.  (The vertices of $H$ are the set of processors, and the edges
of $H$ are the set of
communication wires connecting the processors.)
For our purposes, an {\em embedding} of the graph $E$ into a graph $H$
consists of a many-to-one mapping from the vertices of $E$ to the
vertices of $H$, together with a mapping
from each edge of $E$ to a path (possibly of length zero)
in $H$ between the images of its endpoints.

There are three primary measures of the efficiency of an
embedding.  One is its
{\em load}, which is the maximum number of finite element mesh edges
mapped to any single processor.  (To compute a sparse matrix-vector product,
each processor does an amount of work roughly equal to the number of
edges of $G$ it is assigned.)
The goal of keeping load low is to balance the parallel work among
processors.
The other two measures are the embedding's
{\em dilation}, which is the maximum path length between two processors
that need to communicate (because they share nodes), and its
{\em congestion}, which is the maximum number of edges of $E$ whose
corresponding paths travel through a single edge of $H$ (the number of
messages that cross the most congested communication wire).
The goal of keeping dilation and congestion low is to minimize the total time
required for communication.

The relative importance of dilation and congestion for a
particular machine will depend on its communication mechanism and method
of routing.
\iffalse
Expanded this discussion ... EJS
For instance, when store-and-forward routing is used,
it is crucial to minimize the number of ``hops'' that a message
takes, and the reduction of dilation is a primary concern.  On
the other hand, if the machine in question uses circuit-switched routing
then the length of the routing
paths is not as important as communication bottlenecks, so congestion becomes
more important.
\fi
One common routing mechanism is {\em store-and-forward} (or {\em packet})
routing, where a
message being sent from a source processor to a destination processor is
treated as a atomic ``packet'' of information.  This ``packet''
moves as a unit through the network one processor
at a time, and is
buffered at each intermediate processor along the way before making its
next ``hop'' toward its destination.
In this case, 
it is crucial to minimize the number of ``hops'' that a message
takes, and thus the reduction of dilation is a primary concern. 

A very different routing mechanism that is enjoying increasing popularity
is {\em circuit-switched} (or {\em wormhole}) routing.  In circuit-switched
routing, each source processor ``reserves'' an entire path to its desired 
destination processor and pipelines the bits of its message along the path,
in order to avoid the delays involved in buffering at intermediate processors.
When this routing mechanism is used, the length of the routing
paths used is not as important as the bottlenecks caused by
multiple paths contending for a single communication link.  Thus congestion is 
a more important embedding parameter than dilation for such a machine.

It is not easy to find an efficient embedding of an element adjacency graph
$E$ to a graph $H$.  To simplify
the problem, it is traditionally broken into several steps.
First, the mesh is {\em partitioned} --- cut into subdomains,
one per processor.  An ideal partition will consist of subdomains having
equal load, and will have small boundaries between subdomains
(to minimize the communication between processors).

We define the {\em quotient graph} 
$E'$ derived from $E$ and the
partition.  $E'$ is a graph with a supervertex for each subdomain,
and an edge between two supervertices if their corresponding subdomains
must communicate (because they share mesh nodes).

The second step is to
{\em place} the quotient graph $E'$ on the target machine $H$.
This placement is a one-to-one mapping of supervertices (and their
corresponding subdomains) to processors.
Finally, we {\em route} $E'$ by finding a mapping of
edges in $E'$ to paths in $H$.

It is not necessarily ideal to break the embedding
problem into these steps.  Better partitioning might be possible
with knowledge of the topology of the
target machine, and better placement might be
possible if routing is considered simultaneously.  However, finding
an optimal embedding is difficult, and some simplifying assumptions
are necessary.
More importantly, we separate partitioning from placement and
routing because
partitioning can be done independently of any specific architecture,
whereas placement and routing
depend upon the topology and communication mechanisms of the target machine.
