\noindent Many physical phenomena in science and engineering can be modeled by
partial differential equations (PDEs). When these equations are complex
or are posed on irregularly shaped domains, they usually do not admit
closed-form solutions. A numerical approximation of the solution is
thus necessary.  Computational science and engineering has
emerged as an activity that applies the tools of numerical analysis,
computer science, and applied mathematics to creating computer
models of natural and man-made systems, with the goal of gaining a
better understanding of the chemical, electrical, fluid mechanical,
magnetic, solid mechanical, or thermal phenomena exhibited by these
systems.

The most popular methods for numerically approximating the solution of
linear or nonlinear PDEs replace a continuously defined PDE by a finite
number of weakly coupled linear or nonlinear algebraic equations.  This
process of {\em discretization} associates an unknown (a variable)
and an equation with each of a finite
number of points in the problem domain.
As a concrete example, consider the problem of simulating heat conduction
through a solid, such as the key illustrated in Figure~\ref{key}.
The temperature is recorded at a finite number of points, called
{\em nodes}, on the surface and in the interior of the key.
An exact solution would describe the temperature as a continuous
function of location in
the key, but an exact solution is not attainable, so instead we try to
approximate the temperature at each node.  These nodal temperatures are
unknowns, whose values we discover by solving a set of algebraic equations.

\begin{figure}[hbt]
\centerline{\epsfxsize=4in \epsfbox{key2.1.ele.eps}}
\caption{\label{key} Discretization of an author's office key.
A node occurs wherever edges intersect.}
\end{figure}

The accuracy of the numerical
approximation improves as the number of nodes increases.
(We would obtain the exact solution if we placed a node at every point in the
key, but real computers restrict us to a finite number of nodes.)
However, the
complexity of solving the algebraic system is typically superlinear in
the number of points, and as this number increases,
more time is spent solving the system than is
spent modeling and interpreting the results. Some PDE
problems are intractable on current sequential computers,
and scientists and engineers have become interested in using parallel
computers to attack them.  Problems for which high performance computing 
is required include global climate change, aerospace
vehicle design, cardiovascular blood flow, combustion,
weather forecasting, air pollution, and earthquake-induced ground motion.

The algebraic equations that result from discretization
couple physically adjacent nodes.
Hence, when points are laid down in a uniform, grid-like
fashion as in Figure~\ref{struc}, the structure can be exploited to
yield efficient solvers that parallelize easily.
On the other hand, many problems (like the key) are
defined on irregularly shaped domains, and resist regular
discretization.  Others exhibit phenomena that occur on widely
differing spatial scales.  In this case, uniform
distribution of points is inefficient, because the spacing of points
must reflect the areas that require the finest resolution or greatest
accuracy.
The excess points in other areas lead to unnecessary computational
effort.

\begin{figure}
\centerline{\epsfbox{la.struc.ps}}
\caption{\label{struc} Structured discretization of Los Angeles Basin.}
\end{figure}

\begin{figure}
\centerline{\epsfbox{la.unstruc.ps}}
\caption{\label{unstruc} Unstructured discretization of Los Angeles Basin.}
\end{figure}

Consider the {\em unstructured} mesh in Figure~\ref{unstruc},
which depicts a layered cross-section of the Los Angeles Basin.
The problem is to predict
the surface ground motion due to a strong earthquake. The
discretization is finer in the top layers of the valley, reflecting
the much smaller wavelength of seismic waves in the softer upper
soil, and becomes coarser with increasing depth, as the soil becomes
stiffer and the corresponding wavelength increases. The structured
discretization of the same problem (Figure~\ref{struc})
employs a uniform distribution
of points, the density being dictated by the uppermost layer.
Although the data structures, storage requirements, and parallelization
of structured meshes
are considerably simplified, the resulting several-orders-of-magnitude
increase in the number of unknowns is unacceptable.
Other multiscale phenomena include turbulence,
plasticity, transonic aerodynamics,
and crack propagation.  Unstructured discretization of these
problems can result in greater efficiency.  Unfortunately, it is difficult
to efficiently map an unstructured mesh to a parallel computer.

A number of parallel PDE solvers exist, but some
are built to solve a specific
problem (e.g.\ the Navier-Stokes equations), and some are restricted
to structured meshes.
Our philosophy is that if parallel
computers are to contribute to scientific progress, it is necessary to
build general-purpose tools that allow researchers in engineering and
science to model the complexities of real
domains.

This article describes
Archimedes, an automated system for solving partial differential
equations on geometrically complex domains using distributed memory
supercomputers.
The tasks that must be performed by such a system are
manifold. First, Archimedes discretizes the object or domain being modeled by
generating an unstructured mesh that fills the region.  Then,
the domain is partitioned into separate subdomains, which are
mapped onto individual processors.  Communication is routed between
these processors.  Finally, code is generated to solve a PDE in
parallel.  We shall discuss how we have automated each of these
tasks, and describe our efforts to bring state-of-the-art computing
to state-of-the-art engineering.

\section*{The Genesis of Archimedes}
% Perhaps ``The History of Archimedes'' would be better ...
% but I liked the sound of this ... EJS

The events that led to the development of Archimedes are informative.
In late 1991, civil engineers at Carnegie Mellon began exploring the
use of parallel computers for modeling earthquake-induced ground
motion.  They manually implemented a simulation on the Thinking
Machines CM-2.  To obtain fast enough communication for the simulation
to be useful, they had to use a block-structured mesh and
painstakingly partition it by hand.
Unfortunately, because the
gradation of the block-structured mesh was insufficiently flexible,
the mesh used smaller elements than were desired in the rock surrounding
the valley.  These smaller elements made necessary the use of small time
steps to ensure stability of the numerical method, and so
the solver was forced to take many more iterations
than the physics required.  Switching to a method that does not exhibit
these advantages was considered, but would have
entailed a complete rewriting of the code.  Parallel
computers, rather than a tool, were becoming an impediment to doing
science!

Frustrated by the painstaking level of detail required to create
efficient programs, the engineers sought out computer
scientists at Carnegie Mellon for assistance.  During these
discussions, we realized that by exploiting prior work in
mesh generation and VLSI routing, and our own ongoing work
in graph partitioning and parallelizing compilers, it would be
possible to fully automate the irregular finite element modeling
process.  Thus the Archimedes collaboration was born.
