\section{Introduction}
\label{sec:INTRO}

Computational solution to many science and engineering problems
involves representing the problem as a grid whose point values are
updated through a time simulation. At each step t+1, in the
simulation, a point's value is a function of its neighbor's values for
the previous step, t. 
For large computationally-intensive grid problems, sequential
simulations are impractical.
A great deal of work on parallelizing sequential codes using 
sophisticated compiler technology has been developed, however,
it is limited in effectiveness when applied to dynamic
simulations based on multiple physical models.
Such simulations can be parallelized explicitly by
performing data or functional decompositions of the problem.
Many of these problems are naturally
partitioned into regions of a grid which may vary in density of
points, vary in time-step, vary in convergence rate, vary in size and
shape of region, and vary in computational load. 
Variation in simulation dynamics occur in a wide variety of
problems.
For example, when doing turbulent reacting flow problems \cite{oran:87,fox:96},
it is often the case that the
time scales are very different in various domains of the same flow. 
Using traditional time step
simulations results in wasted computation time spent
updating the variables in the
slow domains. 
Variation also occurs in large simulations whose design 
results from functional
decomposition, where different parts of the simulation model have vastly 
different simulation
equations and time scales. For example, a computer model of climate
may consist of
an atmospheric model, a
hydrologic model, a land surface model, and an ocean model 
each with entirely different
computations and time step granularity \cite{foster:95}.

Developers of simulation software are already familiar with
the basic components of discrete time-stepped simulations.
The desire for increased execution performance of these
codes leads to the use of parallelism.  While parallelism
can dramatically improve performance as well as enable
solution of larger problems, the complexity and cost of
developing parallel software is high.
Our approach to solving variable
irregularly-structured grid problems is to use parallel
discrete event simulation (PDES) techniques \cite{misra:86}.
These techniques address several problems inherent
to the synchronization of parallel computations in neighboring
sub-regions of a decomposed computation.  This approach:
\begin{itemize}
\item employs the "lookahead" concepts of PDES to allow regions
to simulate at their natural rate without excessive barrier
synchronization
\item enables dynamic distribution of the regions' computation to balance load
\item accommodates the irregular size and shape of
regions through a flexible dependency management technique
\end{itemize}
We have defined a reusable object-oriented framework to support
the construction of such simulations in Java.
We call it the parallel adaptive grid simulation (PAGS) framework.
It consists of abstractions that manage
replicated worker style concurrent execution and 
a workpool which encodes and manages a variety of 
dependencies between sub-regions of the simulation.

Our experience working with members of the Center
for Scientific Supercomputing at Kansas State University
suggests that the cost of developing parallel simulation 
software is very high.
In many cases, when developers have limited expertise
with parallel programming technology it is determined
that the risk of undertaking the development of 
parallel software is too high and, consequently, the science and
computational research suffers.
We believe a high-level reusable framework targeted
at the domain of simulation software can significantly
reduce development costs while addressing the performance and
adaptability requirements of large, complex simulations. 
Our experience applying this framework bears this out.

In the next section, we discuss related research on
parallel simulation.
We then present an overview of the programming framework that supports
the construction of parallel adaptive grid simulations
in Section \ref{sec:PAGS}.
This framework is built on top of a reusable
coordination abstraction described in Section \ref{sec:CA}.
The other primary component of the framework,
described in Section \ref{sec:AW}, is a
configurable workpool abstraction that is used to encode
dependences between simulation data.
Section \ref{sec:APPLY}
illustrates the application of the framework
to the solution  of a selected parallel simulation problem
and Section \ref{sec:EVAL} evaluates the effectiveness
of the framework for that problem.
The final section summarizes our
contributions and discusses future work. 
