\section{Background and Related Work}
\label{sec:RELATED}

Many science and engineering problems are described
in continuous form using partial or ordinary differential 
equations \cite{foster:95}.
To solve them computationally, they are modelled as difference
equations. These difference equations are solved through a discrete time
simulation which iteratively updates grid point values for a fixed
number of steps or until a convergence condition is satisfied. At each
time step, the value of a grid point is a function of its neighboring
points. In traditional sequential time-step simulations, all points of
one time-step must be calculated before the next time-step is
taken. In parallel simulation, we can calculate many points in
parallel by utilizing parallel shared-memory and/or distributed-memory
MIMD computer architectures.  Typically, a region of the
grid is associated with a processor,
attempting to match computation grain size with communication time
between regions, and each local region computation is performed in parallel 
for a time-step.
All processors are then synchronized and 
the parallel computation for the next time-step, using region
values from the previous step, is performed. 
If some regions don't utilize
the same size of a time-step, they converge at different rates, there
is less computing activity within a region, the
time-step within a region is variable, or the region size or shape is
variable with time, this lock-step method can be inefficient. 
The PAGS framework we describe in this paper
can adapt to the problem as these parameters change.

Parallel discrete event simulations \cite{misra:86} 
collect information on the dynamic nature of a system defined
as a collection of inter-dependent simulation entities.
Each entity in a simulation system
maintains its own local virtual (simulation) time (LVT). When a region
has simulated activity up to a time when it needs to pass information
to its neighbors, it sends a message stamped with its own LVT
to its neighbors.  In conservative PDES, each region
can only simulate up to a time for which it knows it will never
receive an incoming message with an old timestamp. Thus, an entity  
must acquire input from all of its neighbors before it can simulate. 
The blocking that is inherent in this scheme can result in
deadlock. One method to avoid deadlock is to have regions periodically
send out "null" messages with a time-stamp. This tells the recipient
region that it can simulate up to this time-stamp before asking for
more input. 
To apply these ideas to traditional grid simulation problems 
one can encode simulation messages with a triple of (t, b, l), 
where t is the region's current LVT, b is the border value to be
passed to a neighbor, and l is the lookahead. The lookahead tells the
receiving region how far it can advance its LVT before it gets
information again from the sending region. That is, a region can
predict how far it can compute before it will send new information.
This lookahead value is added to the local LVT.
Thus, a region can continue to compute
as long as it has a message (border) from all neighbors whose
timestamp equals the minimum of all timestamps on incoming messages.
The collection of LVT values thus forms a global
clock which drives the simulation.

The temporal dependences that are fundamental to discrete event
simulation must be honored in order to produce a correct result.
So too must other problem specific dependences, such as 
data dependences.  There has been a considerable amount
of work on statically computing the dependence structure for
a given problem, e.g., \cite{wolfe:96}.  
With accurate dependence information in hand
one can determine an efficient scheduling of sub-problems. 
Our approach aims at finding an efficient schedule for sub-problems
by maintaining a representation of non-temporal dependences
and using PDES to incorporate temporal dependence.
This approach is more flexible than static approaches
since the dependence representation and lookaheads can
be modified at run-time to adapt to the changing 
computational dynamics of a problem.  
