Probabilistic adaptive direct optimism control in Time Warp.
In a distributed memory environment the communication overhead of Time Warp as induced by the rollback procedure due to overoptimistic progression of the simulation is the dominating performance factor. To limit optimism to an extent that can be justified from the inherent model parallelism, an optimism control mechanism is proposed, which by maintaining a history record of virtual time differences from the time stamps carried by arriving messages, and forecasting the timestamps of forthcoming messages, probabilistically delays the execution of scheduled events to avoid potential rollback and associated communication overhead (antimessages). After investigating statistical forecast methods which express only the central tendency of the arrival process, we demonstrate  that arrival processes in the context of Time Warp simulations of timed Petri nets have certain predictable and consistent ARIMA characteristics, which encourage the use of sophisticated and recursive forecast procedures based on those models. Adaptiveness is achieved in two respects: the synchronization behavior of logical processes automatically progressing and conservatively blocking, that is the most adequate for (i) the specific simulation model and (ii) the communication/computation speed characteristics of the underlying execution platform.
Introduction
The distributed simulation of event occurrences by a
set of logical processes (LPs) executing asynchronously in
parallel generates the same sequence of event occurrences
that a sequential simulator would have produced, provided
that every LP simulates events in nondecreasing timestamp
order only. Although sufficient, it is not always necessary
to obey this "local causality constraint" (lcc) [13]
because events may be independent of each other with respect
to their impact on the simulation future (concurrent
events). Generally, therefore, a distributed discrete event
simulation (DDES) insures correctness if the partial event
ordering produced by the LPs executing concurrently is
consistent with the total event ordering generated by a
(hypothetical) sequential, discrete event simulation [17].
The Time Warp (TW) [16] DDES protocol, as opposed
to the conservative Chandy-Misra-Bryant (CMB) protocols
optimistically ignores lcc by letting causality errors
occur, but employs a rollback mechanism to recover
from causality violations immediately upon or after their
detection. The rollback procedure relies on the recon-
structability of past states, which can be guaranteed by a
systematic state saving policy and corresponding state re-construction
procedures. Performance inefficiencies caused
by potentially excessive amounts of memory consumption
for storing state histories, or by the waste of CPU cycles
due to overoptimistically progressing simulations that
eventually have to be "rolled back" are not present in CMB
protocols. On the other hand, while CMB protocols need
to verify whether it is safe to process an event (with respect
to lcc), TW is not reliant on any information coming
from the simulation model (e.g. lookahead). Furthermore,
the severe performance degrade imposed on CMB by the
mandatory deadlock management strategy is relieved from
TW in a natural way, since deadlocks due to cyclic waiting
conditions for messages able to make "unsafe" events safe
to process by exploiting information from their timestamps
can never occur. Another argument for the relaxation of
lcc and TW is the hope for better model parallelism exploitation
and an acceleration of the simulation over CMB
since blocking is avoided.
Despite convincing advantages, TW is not devoid of
shortcomings. The rollback mechanism is known to be
prone to inefficient behavior in situations where event occurrences
are highly dispersed in space and time. Such
"imbalanced" event structures can yield recursive rollback
invocations over long cascades of LPs which will eventually
terminate. An excessive amount of local and remote state
restoration computations is the consequence of the annihilation
of effects that have been diffused widely in space
and too far ahead in simulated time, consuming considerable
amounts of computational, memory and communication
resources while not contributing to the simulation
as such. This pathological behavior is basically due
to the "unlimited" optimism assumption underlying TW,
and has often been referred to as rollback thrashing. In
distributed memory multiprocessor environments or clusters
of RISC workstations, i.e. environments where CPU
performance is significantly tempered by the communication
performance, rollback thrashing can cause excessively
higher performance degrades (in absolute terms) as compared
to shared memory or allcache systems [5]. Of outstanding
practical interest for TW implementations in such
environments is therefore the reduction of communication
overhead induced by the protocol.
After presenting related work on optimism control for
TW in Section 2, empirical observations from a distributed
memory environment (CM-5) demonstrate that the communication
behavior of TW is the dominating performance
factor (Section 3). We show how the optimism in TW can
be related to the parallelism available in the simulation
model, which is extracted from observing message arrival
patterns along the input channels of LPs. After discussing
straightforward statistical methods for forecasting the next
message's timestamp, a self-adaptive characterization procedure
is worked out based on ARIMA (autoregressive-
integrated moving average) stochastic processes to enable
a direct, probabilistic and self-adaptive optimism control
mechanism.
Background
Attempts to "limit the optimism" in TW in order to
overcome rollback overhead potentials have appeared in
the literature. Sokol, Briscoe and Wieland [26] propose to
restrict optimistic simulation advancements to time windows
that move over simulated time. In their moving time
window (MTW) protocol, events e with an occurrence time
are not allowed to be simulated in the time
window \Delta), but are postponed for the next time
window events e and e 0 with ot(e)
and ot(e 0 ) can therefore only be simulated in parallel if
\Delta. Naturally, the protocol favors simulation
models with a low variation of event occurrence
distances relative to the window size. The implicit assumption
that event occurrence times are distributed approximately
uniformly in space, the obliviousness with respect
to potentially "good" optimism beyond the upper
window edge, as well as the difficulty to determine \Delta such
that enough events are admitted to make the simulation
efficient have been the main criticisms of this approach.
Opposed to MTW, the Breathing Time Bucket (BTB)
[27] employs adaptable "breathing" time cycles of variable
widths (time buckets). Each time bucket contains the maximum
number of causally independent events determined
by the event horizon, i.e. the minimum occurrence time of
any event scheduled in the previous bucket in some LP.
"Risk-free" executions are attained by combining an optimistic
windowing mechanism with a conservative message
sendout policy, where the necessity of any antimessage is
avoided by restricting potential rollback to affect only local
history records (as in SRADS [8]). The Breathing Time
Warp (BTW) [28] protocol combines features of MTW and
BTB, based on the belief that the likelihood of an optimistically
processed event being subject to a future correction
increases with the distance of its timestamp from
the global virtual time (GVT). Therefore, the sendout of
event messages with timestamps 'distant' from GVT are
delayed.
Other window-based optimism control mechanisms that
appeared in the literature are the Bounded Time Warp
(BTW) [30], which similar to MTW divides virtual time
into equally sized intervals, but depletes all events from every
interval before a new intervall is started, and MIMDIX
[19], which probabilistically invokes resynchronization of
LPs at regular time intervals to prevent LPs from excessive
virtual time advancement. Window-based throttling
[25] has also been used with the intent of preventing LPs
from executing too far, but in addition, aggressive objects
whose work has to be rolled back frequently are penalized
with temporary suspension (penalty-based throttling).
As such, the protocol described by Reiher and Jefferson is
adaptive in the sense that it reacts in a selfcorrecting way
to observed execution behavior.
The possibility of "adapting" the synchronization behavior
of a DDES protocol to any desirable point within
the spectrum between pure optimistic and pure conservative
approaches has already been seen in [24]. Several
contributions appeared along those ideas, one of the
earliest being the Adaptive TW concurrency control algorithm
(ATW) proposed by Ball and Hyot [3]. ATW
temporarily suspends event processing if it has observed
a certain number of lcc violations in the past, i.e. stop
LVT advancement for a time period called the blocking
window (BW). The size of BW is determined based on
the minimum of a function describing wasted computation
in terms of time spent in a (conservatively) blocked
mode or a fault recovery mode as induced by the TW roll-back
mechanism. In [12], an optimal CPU delay interval
is computed from an explicit cost model for the trade-off
between optimistically progressing and conservatively
blocking the local simulation, established from a topological
message arrival history map encoding the real-time -
virtual-time increments (decrements) per message arrival
as empirically observed during the simulation. The probabilistic
DDES protocol [10] makes use of event causality
probabilities to avoid communication overhead in TW by
probabilistic throttling. Assuming that the occurrence of
e in some LP i is probabilistically causal for a future event
changes the state variables read by e 0 , then in cases where
conservatively blocking until it is safe to
process e 0 in LP j hinders producing potentially "good"
simulation work. Clearly, in repeated executions of e; e 0 sequences
with an optimistic strategy could
have gained from a concurrent execution of e 0 and e most
of the time. The protocol not only exploits locally (on a
per channel basis in every LP) the probability of the forthcoming
message being a straggler by taking into account
the implicit probabilistic causalities, but also the architectural
characteristics of the target platform like CPU speed
and communication latencies. The local adaptive protocol
(LAP) proposed by Hamnes and Tripathi [14], based
on average LVT increments and average interarrival times
l 2

Figure

1: LP Simulation of a Stochastic Petri Net
(CPU time and simulated time) tries to estimate a real
time blocking window. In order to prevent deadlocks, but
also to break blocking conditions early, null messages are
needed in LAP. According to Rajaei et. al. 's [23] classification
of possibilities to regulate the degree of "aggressive-
ness" and "risk" in a DDES, LAP falls into the category
switching seamlessly between optimistic and conservative
schemes, whereas the previously described adaptive protocols
are limiting optimism in TW.
Both ATW and the probabilistic protocol can be categorized
as direct optimism control mechanisms, as opposed to
indirect optimism control, where the individual LP's LVT
progression is throttled via the availability of free memory.
The adaptive memory management (AMM) scheme proposed
by Das and Fujimoto [7] attempts a combination of
controling optimism and an automatic adjustment of the
amount of memory in order to optimize fossil collection,
Cancelback [15] and rollback overheads. The Cancelback
memory management scheme allows those memory spaces
that are used for storing the most recent state and input-
/output-history of some LP to be reclaimed selectively after
TW has exhausted all available storage resources. Fossil
collection relocates memory used for storing state information
that will definitely not be reused by the rollback
procedure due to GVT progression. It has been shown [1]
that fossil collection in TW with Cancelback can always re-locate
enough memory for continuation of the simulation,
given that a certain minimum amount of memory is physically
available [18]. At this point, TW performance will
be very poor due to frequent Cancelbacks. Increasing the
amount of available memory will reduce the Cancelback
frequency, such that absolute performance will have positive
increments. But this at the same time will increase
the rollback frequency, such that the rollback overhead
will eventually start overwhelming the gain from reduced
Cancelback overheads. AMM, by controling the amount
of available memory, automatically adjusts to the "knee-
point" of optimal TW performance.
3 Reducing Communication Overhead in TW
To demonstrate the potential gain of an adaptive direct
optimism control mechanism for TW, we consider
the Stochastic Petri Net (SPN) simulation model that has
been used in [10]. The SPN (Figure 1) comprises two
places (P1, P2) and two transitions (T1, T2) with exponentially
distributed enabling delays -(T1) - exp(-1 ) and
Together with infinite server (enabling)
semantics, the SPN describes a continuous time, discrete
event dynamic system with inherent model parallelism [9].
(The occurrence time ot(T1(ffl i )) of T1 with the i-th token
is determined by t is an exponential
variate with does not
depend on the presence or absence of any other token and
can "serve" multiple tokens simultaneously, thus expressing
a notion of parallelism among individual tokens.)
This example has been chosen since it is the smallest possible
SPN structure able to express concurrency among
event occurrences, where the degree of model parallelism
can be scaled arbitrarily by simply adding tokens to the
SPN, while at the same time arbitrary load imbalance can
be imposed by mismatching timing parameters for
T2.
In order to exploit this model parallelism in a distributed
discrete event simulation, the SPN model is decomposed
into two spatial regions which are assigned to
two LPs (LP1 and LP2) as depicted in Figure 1. Two
directed communication channels replacing the SPN arcs
(T1, P2) and (T2, P1), thus interconnecting LP1 and LP2 ,
are required to carry messages containing time stamped
tokens that were generated by the firing of
a transition. k is the number of tokens, P the destination
place, and t a copy of the local virtual time (LVT) of
the LP at the instant of that firing of the transition that
produced the token. We call m a tokenmessage, since its
purpose - much like an SPN arc - is to propagate tokens
together with their timestamp from one spatial SPN region
into another one that resides in a remote LP. In the
sample SPN, the firing of a scheduled transition (internal
event) always generates an external event, namely a message
carrying a token. On the other hand, the receipt of
an event message (external event) always causes a new internal
event in the receiving LP, namely the scheduling
of a new transition firing in the local event list EVL. Depositing
tokens in a time consistent way into the target
places requires the employment of a DDES synchronization
protocol. Both, CMB and TW based protocols have
been studied in the literature to synchronize the execution
of spatially decomposed PNs [29, 2, 22, 6, 21].
3.1 TW Simulation of the SPN on the CM-5
We have implemented TW with the lazy cancellation
rollback mechanism for the concurrent execution of
PNs on the CM-5 using the CMMD message passing li-
brary.Executing the SPN simulation model in Figure 1
on the CM-5 empirically explains that communication is
the major performance pitfall of TW implementations on
distributed memory multiprocessors (Figure 2): The SPN
with one token initially assigned to a place does not contain
any model parallelism; the two LPs are blocked half
of the time. With two tokens in the SPN we have very little
model parallelism, and the LP simulation engines are
overwhelmed with communication (when 1), the ratio
of execution time used for processing events is less than
12%; the rest is wasted for communication, data structure
manipulations and blocking due to the lack of events
Number of Tokens (= Degree of Parallelism)
Percentage of CPU Time spent for Communication: LP1
Number of Tokens (= Degree of Parallelism)
Percentage of CPU Time spent for Communication: LP2
Number of Tokens (= Degree of Parallelism)
Percentage of CPU Time spent for Event Simulation: LP1
Number of Tokens (= Degree of Parallelism)
Percentage of CPU Time spent for Event Simulation: LP2
Number of Tokens (= Degree of Parallelism)
Percentage of CPU Time spent for Rollback: LP1
Number of Tokens (= Degree of Parallelism)
Percentage of CPU Time spent for Rollback: LP2
Number of Tokens (= Degree of Parallelism)
Percentage of Time Waiting for Messages: LP1
Number of Tokens (= Degree of Parallelism)
Percentage of Time Waiting for Messages: LP2

Figure

2: TW Performance (lazy cancellation) of LP 1 and LP 2 on CM-5
scheduled in the local EVL. The situation improves when
more tokens are in the system: with a parallelism degree
of about 25% of the CPU time can be used
for executing internal events, but still the communication
overhead is above 40%.
To investigate the impact of lcc violations due to inhomogeneous
LVT increments in the communicating LPs
on communication overhead induced by rollback we can
(in our example) control the balance of LVT progress by
the parameter we have a balanced
situation. Service at T1 takes on average as long as at
. Setting twice as fast (with respect
to LVT progression) than T2, i.e. the enabling time
is twice as long; the higher the expected enabling time of
(which is 1
), the more tokens will reside in P1 (in
steady state) enabling T1. The charts for rollback costs in

Figure

empirically show that the smaller -1 , the more
rollbacks are induced in LP2 , imposing increasing rollback
overhead on the CPU executing LP2 . Clearly, an LP with
small LVT increments followed by an LP with high LVT
increment will frequently force its successor to rollback,
given they work at the same event processing speed. From
the waiting time charts in Figure 2 it is observed, that a
shift of load happens from LP1 to LP2 with increasing -1 ,
giving LP2 the chance to spend more CPU time on event
execution. This is, unfortunately, at the expense of LP1 ,
which is forced to idle for load (tokens).
A consequence, in order to improve overall TW perfor-
mance, is that rollback (and consequently communication-
) overhead has to be avoided as far as possible. Reducing
the absolute number of rollbacks/communications is
the main issue of an optimism control mechanism in this
context. Moreover, since the event structure of general
simulation problems cannot be assumed to be stationary
over the whole simulation interval, the capability of LPs to
adapt to phases (where different degrees of optimism are
advisable) emerging at runtime is demanded.
3.2 Gaining from Direct Optimism Control
The (synchronous) parallel execution of the sample
SPN is illustrated in Table 1. In step 0, both LPs use
precomputed random variates from their individual future
lists and schedule events (EVL). (Let the future
lists be
In step 1, LP1
and LP2 execute their respective earliest internal events,
generating external events (messages with copies of LVT)
to be sent to the other LP, etc. At the beginning of step 3,
LP2 at LVT at the end of step 2) faces the
straggler (out-of-timestamp-order message) h1;P2; 0:37i in
its input queue IQ; the next element in LP2 's future list is
0.42. Since the effect of the straggler is in the local future
of LP2 , i.e. hT2@(0:37 + 0:42)i, the lazy rollback strategy
applies and rollback is avoided at all. The event hT2@0:79i
is executed in that step, setting and the out-
putmessage h1;P1; 0:79i is generated (output queue, OQ)
and sent at the end of the step. Unfortunately in step 4, a
new straggler h1;P2; 0:73i is observed in IQ of LP2 , but now
with the effect that at time
LP2 is forced to roll back (Figure 1, top). Indeed, LP2
in step 3 generated and sent out h1;P1; 0:79i without considering
any information whether the implicit optimism is
justified or not. If LP2 would have observed that it received
"on the average" one input message per step, with an "av-
erage" timestamp increment of 0.185, it might have established
a hypothesis that in step 4 a message is expected
to arrive with an estimated timestamp of
0.555 (= timestamp of previous message
crement). Taking this as an alarm for potential rollback,
could have avoided the propagation of the local optimistic
simulation progression by e.g. delaying the sendout
of h1;P1; 0:79i for one step. This is illustrated in Figure 1,
bottom: LP2 just takes the input message from IQ and
schedules the event hT2@0:79i in EVL, but does not process
it. Instead, the execution is delayed until the hypothesis
upon the next message's timestamp is verified.
The next message is h1;P1; 0:73i, the hypothesis can be
dropped, and a new event hT2@0:78i is scheduled and processed
next. Apparently two rollbacks and the corresponding
sending of antimessages could be avoided by applying
a direct optimism control scheme, that employs blocking if
there is empirical evidence (in the statistical sense) for a
potential future rollback. In the next section we develop
an adaptive optimism control mechanism, that by monitoring
the arrival process of messages "on-the-fly" determines
whether to let the simulation make full use of the available
parallelism, or whether to throttle the optimism in order
to prevent from costly rollbacks.
4 Probabilistic Direct Optimism Control
An indirect optimism control mechanism like AMM,
although successful in shared memory environments, appears
inappropriate for distributed memory systems since
it potentially increases the number of rollbacks and thus
the communication overhead. Instead, optimism control
directly via throttling the simulation engine is advisable
for distributed memory multiprocessors.
To be able to directly control the optimism in TW,
each LP in our approach monitors the LVT progression
on each of its incident channels, i.e. logs the timestamps
of messages as they arrive. From the observed message
arrival patterns, each LP formulates a hypothesis on the
timestamp of the next message expected to arrive, and
- related to statistical confidence in the forecast value -
by means of throttling adapts to a synchronization behavior
that is presumably the best tradeoff among blocking
(CMB) and optimistically progressing (TW) with respect
to this hypothesis in the current situation. Throttling is
done probabilistically in the sense that blocking is induced
with a certain probability.
Assume that the history over the last n message arrivals
maintained
in LP l for every (input) channel chk;l , and that b ts(m i+1))
is an estimate for the timestamp of the forthcoming message
Let the confidence 0 - i( b
express the "trust" in this estimate. Then LP l having
TW with unlimited optimism
IB LVT P1 EVL OB RB IB LVT P2 EVL OB RB
TW with "controlled" optimism
IB LVT P1 EVL OB RB IB LVT P2 EVL OB RB

Table

1: Reducing Communication Overhead with Probabilistic LP Simulation
program PADOC Simulation Engine( )
while GVT - endtime do
2.1 for all arriving messages m do
update(arrivalstatistics, m);
affects local past */
then /* rollback */
restore earliest state before(ts(m));
generate and sendout(antimessages);
else chronological insert(m, IQ);
2.2 b
ts
2.3 i(b confidence in forecast(arrivalstatistics);
2.4 if ts(first(EVL)) - ts(first nonnegative(IQ))
then
then /* delay execution */
else process(first(EVL));
else process(first nonnegative(IQ));
2.5 sendout(outputmessages);
2.6 fossil collection(advance GVT());
od while;

Figure

3: PADOC Simulation Engine.
scheduled tr as the transition to fire next, say at ot(tr ),
would execute the occurrence of tr with some probability
Pi[execute htr @ot(tr)i], but would block for the average
amount of CPU time s (used to simulate one transition
firing) with probability . The algorithm sketch of
the PADOC (Probabilistic Direct Optimism Control) LP
simulation engine in Figure 3 explains further details.
Note that in contrast to other adaptive TW mechanisms
that compute an optimal delay window for blocking
the simulation engine [3, 14, 12], the PADOC engine blocks
for a fixed amount of real time (i.e. s), but loops over the
blocking decision, incrementally establishing longer blocking
periods. By this discretization of the "blocking win-
dow" PADOC preserves the possibility to use information
on the arrival process encoded in the timestamps of mes-
Executed Transition Firing Scheduled Transition Firings Tokenmessage Arrival
Simulated Timed 1 d n-3 d 1 d n
ts
ts
.
d n-1 d n
d n-2 D
ts m

Figure

4: Message Timestamp Forecast
sages that arrive in between blocking phases. Algorithms
based on variable size blocking windows fail to make use
of intermediate message arrivals.
4.1 Incremental Forecast Methods
Predicting the timestamp of the forthcoming message
having observed n arrivals is explained in Figure
4. Basically, by statistically analyzing the arrival
instants ts(m i\Gamman+1 ); ts(m i\Gamman+2 an estimate
is the difference in timestamps
of two consecutive messages. (Note that ffi k is negative
if m i\Gamman+k is a straggler.)
The choice of the size of the observation history n as
well as the selection of the forecast procedure is critical for
the performance of the PADOC engine for two reasons:
(i) the achievable prediction accuracy and (ii) the computational
and space complexity of the forecast method.
Generally, the larger n, the more information on the arrival
history is available in the statistical sense. Considering
much of the arrival history will at least theoretically
give a higher prediction precision, but will also consume
more memory space. Intuitively, complex forecast methods
could give "better" predictions than trivial ones, but
are liable to intrude on the distributed simulation protocol
with an unacceptable amount of computational resource
consumption. Therefore, incremental forecast methods of
low memory complexity are recommended, i.e. procedures
can be computed from the previous forecast
and the actual observation ts(m i+1) in O(c)
instead of O(cn) time.
Arithmetic Mean If no observation window is imposed
on the arrival history, but all observed ffi j 's are considered,
Message number
Arrivals at LP2
50 100 150 200 250 300
Message number
Arrivals at LP2
50 100 150 200 250 300
Message number
Arrivals at LP2
50 100 150 200 250 300
Message number
Arrivals at LP2

Figure

5: Arrival Processes as observed at LP 2 (CM-5)
then the observed mean b
as an estimate of
the timestamp of the forthcoming message has a recursive
form. Upon the availability of the next time difference
ts(m i+1) can be computed incrementally as:
Exponential Smoothing The arithmetic mean based
forecast considers all observations equally "impor-
tant". A possibility to express the history as an exponentially
weighted sum (e.g. give recent history higher "im-
portance" than past history) is the exponential smoothing
of the observation vector by a smoothing factor ff
\Delta in this case has the incremental form
high weight to the last observation, and
potentially yields a high variation in the forecasts. ff - 0
causes intense smoothing, making forecasts less reactive to
shocks in the arrival process. We use the smoothing factor
which is periodically readjusted during the simulation.
Median Approximation The virtual time increments in
general cannot be assumed to yield a nonskewed, unimodal
distribution of values, as is implicitly assumed when the
arithmetic mean is used as an index of central tendency.
Particularly, if the frequency of time increments has a pdf
skewed to the left, then the arithmetic mean is higher in
value than the median, and would thus overestimate the
next message's timestamp. A consequence would be "over-
pessimism" in the blocking policy. Forecast based on the
median would use the estimate
which cannot be computed incrementally, as new timestamp
increments have to be inserted in a sorted list of ffi i 's
to find the value of the median afterwards. As an approximation
for the median we have developed the following
Execution %-Simulation %-Rollback
Time LP1 LP2 LP1 LP2
DD TW 0.46 12.7 13.7 5.8 16.1
TW+A 0.62 23.7 41.0 6.8 5.4
TW+S 0.96 19.4 37.7 6.8 8.4
TW+A 0.64 19.8 41.8 5.8 6.8
TW+S 0.66 17.1 39.2 6.0 8.2
TW+A 1.17 24.3 43.5 5.8 9.5
SS TW 0.91 11.0 15.0 11.7 15.3
TW+M 0.57 16.6 37.6 7.3 6.9
TW+S 1.03 19.8 37.9 7.4 9.6
TW+A 0.91 23.1 41.6 6.8 9.3

Table

2: TW with M, S and A for CM-5.
supplement. Let
mean , which is a constant for
every distribution (e.g. for the exponential distribution we
have
c
we find a forecast based on a median which is approximated
by the arithmetic mean as
The performance of the three "straightforward" forecast
methods (arithmetic mean (M), exponential smoothing (S)
and approximated median (A)) applied to the SPN in Figure
1 with 4 tokens in the initial marking and different timing
scenarios is summarized in Table 4.1 (generated using
the N-MAP virtual processor simulation tool with CM-5
performance settings [11]). In the scenario referred to as
DD both T1 and T2 obey deterministic, but imbalanced
timing In the second case, SD,
has stochastic timing with -(T1) - exp(1), but T2 is deterministically
timed as 8. Similarly, DS represents
exp(1=8). Note that in any case
LVT progression in LP2 is (on average) eight times higher
than in LP1 causing significant load imbalance and roll-back
(communication) overhead. (All forecast confidences
are kept constant at refers
to TW with unlimited optimism.) Sample arrival process
traces as collected on the CM-5 are depicted in Figure 5 for
Lag
ACF
-0.20.6Lag
-0.20.6Lag
-0.40.4Lag
-0.20.6Lag
Partial
ACF
Lag
-0.40.2Lag
-0.4
-0.2Lag
-0.3
-0.2

Figure

Autocorrelation and Partial Autocorrelation Function of Arrival Processes at LP 2 (CM-5)
the two LPs for DD (left), SD (half-left), DS (half-right)
and SS (right).
Since the timestamp differences in DD toggle between
behavior represents
a neutral case for all methods, e.g. method M repeatedly
overestimates and underestimates the next timestamp
and thus cannot gain over TW in the long run. Overall execution
time grows, however, since forecasting intrudes the
simulation engine (stalls CPU cycles). The first quartuple
of lines in Table 4.1 explains the order of intrusion induced
by the various methods. In the case SD (second quartuple
of lines in Table 4.1), method A finds the highest chances
to avoid rollbacks and can outperform U. For DS, method
M finds an absolute stress case, yielding a slowdown as
compared to U. If the arrival process has two stochastic
components (SS) both M and A can outperform U. The
most important observation from Table 4.1 is, that all
the methods are able to increase the percentage of overall
execution time spent for simulating events over the communication
overhead induced. Thus the optimism control
schemes are even more promising for distributed memory
environments, for which the communication/computation
speed ratio is smaller than on the CM-5, e.g. a cluster of
RISC workstations.
The main drawback of the forecast schemes M, S and
A are that they cannot cope with transient "patterns" of
arrivals, but do respect only a central tendency of timestamp
increments. Arrival patterns that show certain regu-
larities, or at least some correlation in the time increments,
can yield to stress cases as was seen above. Therefore forecast
methods able to identify correlations and to predict
next events at the maximum likelihood of those correlations
are demanded.
4.2 ARIMA Forecasts
In this section we follow the idea of considering the arrival
process as an unknown stochastic processes fX t
are a series of in-
ARIMA
ARIMA
ARIMA
ARIMA
DD SD DS SS
AAAA
AAAA
AAAA
AAAA
AAAA
AAAA
AAAA
AAAA
AAAA
AAAA
AAAA
AAAA
AAAA
AAAA
AAAA
AAAA
AAAA
AAAA
AAAA
AAAA
AAAA
AAAA
AAAA
AAAA
AAAA
AAAA
AAAA
AAAA
AAAA
AAAA
AAAA
AAAA
AAAA
AAAA
AAAA
AAAA
AAAA
AAAA
AAAA
AAAA
AAAA
AAAA
AAAA
AAAA
AAAA
AAAA
AAAA
AAAA
AAAA
AAAA
AAAA
AAAA
AAAA
AAAA
AAAA
AAAA
AAAA
AAAA
AAAA
AAAA
AAAA
AAAA
AAAA
AAAA
AAAA
AAAA
AAAA
AAAA
AAAA
AAAA
AAAA
AAAA
AAAA
AAAA
AAAA
AAAA
AAAA
AAAA
AAAA
AAAA
AAAA
AAAA
AAAA
AAAA
AAAA
AAAA
AAAA
AAAA
AAAA
AAAA
AAAA
AAAA
AAAA
AAAA
AAAA
AAAA
AAAA
AAAA
AAAA
AAAA
AAAA
AAAA
AAAA
AAAA
AAAA
AAAA
AAAA
AAAA
AAAA
AAAA
AAAA
AAAA
AAAA
AAAA
AAAA
AAAA
AAAA
AAAA
AAAA
AAAA
AAAA
AAAA
AAAA
AAAA
AAAA
AAAA
AAAA
AAAA
AAAA
AAAA
AAAA
AAAA
AAAA
AAAA
AAAA
AAAA
AAAA
AAAA
AAAA
AAAA
AAAA
AAAA
AAAA
AAAA
AAAA
AAAA
AAAA
AAAA
AAAA
AAAA
AAAA
AAAA
AAAA
AAAA
AAAA
AAAA
AAAA
AAAA
AAAA
AAAA
AAAA
AAAA
AAAA
AAAA
AAAA
AAAA
AAAA
AAAA
AAAA
AAAA
AAAA
AAAA
AAAA
AAAA
AAAA
AAAA
AAAA
AAAA
AAAA
AAAA
AAAA
AAAA
AAAAAAAA
AAAA
AAAA
AAAA
AAAA
AAAA
AAAA
AAAA
AAAA
AAAA
AAAA
AAAA
AAAA
AAAA
AAAA
AAAA
AAAA
AAAA
AAAA
AAAA
AAAA
AAAA
AAAA
AAAA
AAAA
AAAA
AAAA
AAAA
AAAA
AAAA
AAAA
AAAA
AAAA
AAAA
AAAA
AAAA
AAAA
AAAA
AAAA
AAAA
AAAA
AAAA
AAAA
AAAA
AAAA
AAAA
AAAA
AAAA
AAAA
AAAAAAAA
AAAA
AAAA
AAAA
AAAA
AAAA
AAAA
AAAA
AAAA
AAAA
AAAA
AAAA
AAAA
AAAAAAAA
AAAA
AAAA
AAAA
AAAA
AAAA
AAAA
AAAA
AAAA
AAAA
AAAA
AAAA
AAAA
AAAA
AAAA
AAAA
AAAA
AAAA
AAAA
AAAA
AAAA
AAAA
AAAA
AAAA
AAAA
AAAA
AAAA
AAAA
AAAA
AAAA
AAAA
AAAA
AAAA
AAAA
AAAA
AAAA
AAAA Simulation AAAA
AAAA
Communication AAAA
AAAA
Rollback AAAA
AAAA
Blocking

Figure

8: TW with ARIMA for RS6000 Cluster
stances of a random variable. Specifically X
are the empirically observed timestamp differences, transformed
by the series mean ffi. If fX t g are statistically
dependent variables, the arrival process can be modeled
by an integrated autoregressive moving average process
e.g. [4])
where r is the d-fold differencing operator,
and B the backward shift operator defined by B
This means that for e.g. 2, the
process Y is assumed to be
a stationary ARMA[p; q] (=ARIMA[p;0; q]), composed by
a pure autoregressive process of order p (AR[p]) explaining
Y t as a dependency Y
being a white noise random error, and a pure moving
average process of order q (MA[q]) that explains Y t as a
series of i.i.d. white noise errors Y
ffl and E(Y t
Looking at the arrival process as obtained on the CM-5
for LP2 of the SPN in Figure 1 (Figure 5) and the corresponding
autocorrelation (ACF) and partial ACF (Fig-
ts
ts
ts
ts
ts
Probability
of
Delay
Probability
of
Delay

Figure

7: Probabilistic Direct Optimism Control with ARIMA Forecasting
ure 6), we find high positive correlation after every fourth
lag for DD (Figure 6, left) obviously due to the four tokens
in the SPN. The case SD (Figure 6, half-left) leads
us to hypothesize that the arrival process is AR, since we
find ACF dying down in an oscillating damped exponential
fashion. This is also intuitive because the deterministic
component in the process dominates the
stochastic one (-(T1) - exp(1)). DS (Figure 6, half-right)
gives evidence for a suitable representation of the the arrivals
as a MA process, becuase ACF has a single spike at
lag 1, and PACF dies down, etc.
For the automated characterization of the arrival process
as an ARIMA[p; d; q] process, the classical Box-Jenkins
procedure can be adapted:
1. Model Order Identification First, the order of
the ARIMA model, [p; d; q] is identified. Since the theoretical
partial autocorrelations %k\Gamma1 (k) to the lag k vanish
after some k ? p for a pure AR[p], the order of
such a process can be approximated from the empirical
partial autocorrelations rk\Gamma1 (k). Similarly, for a pure
MA[q], the theoretical autocorrelations % (
some k ? q, such that again the empirical data (auto-
correlations r(k)) can be used to approximate the order.
For a combined ARMA[p; q] process, the Akaike-criterion,
i.e. the combination (p; q) that minimizes AIC(p;
log boe 2
approximates the order. (boe 2
p;q is a
Maximum-Likelihood estimate of the variances oe 2
ffl of the
underlying white noise error.) The Akaike-criterion has a
more general form for ARIMA[p; d; q] processes. Indeed,
as intuitively recognized, we find best order fittings e.g.
for SD as ARIMA[3; 0; 0] or for DS as ARIMA[0; 0; 4].
2. Model Parameter Estimation In the next step,
the parameters in (1) (OE are determined
as maximum likelihood estimates from the empirical
data, i.e. the estimates -
that minimize the square sum S 2 ( -
t of the residuals ~
" t\Gammaq are used as the model parameters.
3. Model Diagnostics/Verification A well know
method to validate the model with the estimates -
and -
'q is the Portmonteau lack-of-fit-test, which
tests whether the residuals ~ " t are realizations of a white
noise process. The confidence level (1 \Gamma ff) of the test can
be used as a measure to quantify the "trust" in the model
and, as a consequence, in the forecast.
4. Forecast Finally, the (recursive) Durbin-Levinson
method provides an algorithm for the one-step (or k-step)
best linear prediction for b
At a confidence level the PADOC simulation
engine (Figure 3, in Step 2.4) executes the next
scheduled a transition firing with probability
\Gammabts
otherwise the CPU is blocked for s time units. Figure 7
explains the blocking probability (2) related to the confidence
level The higher the confidence i, the
steeper the ascent of the delay probability as LVT progresses
towards b
ts. (Steepness of the sigmoid function in

Figure

7 (left) with higher than in Figure 7
0:90). Note also that after LVT progression in
LP j has surpassed the estimate b
ts (

Figure

7, right), delays
become more and more probable, expressing the increasing
rollback hazard the LP runs into. A general observation
is that with i - 1, PADOC imposes a synchronization
behavior close to CMB, whereas with i - 0, optimism is
as unlimited as in (plain) TW. Moreover, by periodically
rebuilding the ARIMA model, the PADOC scheme adapts
the LP to a synchronization behavior directly reflecting the
inherent model parallelism, and also copes with transient
arrival processes.
Clearly, the ARIMA approach for optimism control is
much more expensive in space and execution time than the
previous methods M, S and A. Since the implementation
of steps 1. - 3. of the Box Jenkins procedure is still under
way, we have provided the simulator with an ARIMA
model computed off-line for the performance comparison
reported in Figure 8. For the SPN in Figure 1 with a model
parallelism of 100 (i.e. 50 tokens in P1 and P2) and an NMAP
execution with RS6000 and PVM 3.2 performance
characteristics, we find the ARIMA based method able to
outperform TW (and all other approaches
not shown), while being at least as good as those in stress
cases like DD. The same scenario executed for the CM-
5 revealed about the same performance characteristics for
the ARIMA method, whereas M, S, and A gained less. M
and S tend to more consistent forecasts and therefore better
performance as model parallelism increases, whereas
ARIMA is not significantly sensitive to model parallelism.
5 Conclusion
A probabilistic direct optimism control (PADOC)
mechanism for the TW distributed discrete event simulation
protocol has been presented. Our simulation engine,
by temporarily blocking the processing of internal events,
avoids the generation and sendout of messages in states for
which it is likely that they will have to be "rolled back".
Vice versa, every LP tends to await messages that influence
the local causality among events with high probability, in
order to avoid causality violations. A statistical analysis
of the message arrival history is used to make forecasts
for the timestamps of future messages, thus enabling every
LP to adapt its local synchronization behavior to the
most efficient strategy with respect to the anticipated fu-
ture. Two classes of forecast methods are studied: (i) for
estimates based on (weighted) means, efficient (incremen-
tal) procedures can be implemented causing negligible or
minor intrusion on the simulation engine. Those methods
(arithmetic mean, exponential smoothing and median
however cannot cope well with seasonal,
nonstationary arrival process, and are thus prone to pathological
behavior. (ii) at the cost of higher computational
complexity, more sophisticated forecast methods with a
much higher prediction precision in the case of periodic or
seasonal (correlated) channel (virtual) time increments can
be used. Specifically, the time increment process can be
modelled as an integrated autoregressive moving average
process (ARIMA[p; d; q]), and the probabilities for delaying
the execution of the next internal event can be directly
related to the confidence in the model approximation.
The PADOC mechanism gains adaptiveness in the sense
that, independent of the ratio of the communication and
computation speed of the target platform, the synchronisation
policy is adjusted automatically to that point in
the continuum between TW and CMB protocols, that is
most appropriate for the parallelism inherent in the simulation
model. Forecasting based on ARIMA[p; d; q] models,
moreover, makes the simulation engine also able to adapt
to transient (nonstationary) arrival processes.

Acknowledgements

This paper was elaborated while the
author was visiting the University of Maryland, supported
by a grant from the Academic Senate of the University
of Vienna. The use of the resources at the Computer
Science Dept. and the CM-5 at UMIACS are gratefully
acknowledged. The work was partially supported by the
Austrian Federal Ministry of Science and Research under
grant CEI GZ 308.926 and the Oesterreichische Nationalbank
under grant No. 5069. The author wishes to thank
the anonymous referees for valuable comments on a preliminary
version of this paper.



--R

The Effect of Memory Capacity on Time Warp Performance.
Time Warp Simulation of Stochastic Petri Nets.
The Adaptive Time-Warp Concurrency Control Algorithm
Time Series: Theory and Methods.
Effect of Communication Overheads on Time Warp Performance: An Experimental Study.
Distributed Simulation of Petri Nets.
An Adaptive Memory Management Protocol for Time Warp Parallel Simulation.
SRADS with Local Rollback.
Concurrent Execution of Timed Petri Nets.
Adaptive Logical Processes: The Probabilistic Distributed Simulation Protocol.
Performance Oriented Development of SPMD Programs Based on Task Structure Specifications.
Estimating Rollback Overhead for Optimism Control in Time Warp.
Parallel Discrete Event Simulation.
Investigations in Adaptive Distributed Simulation.
Virtual Time II: The Cancelback Protocol for Storage Management in Time Warp.
Fast Concurrent Simulation Using the Time Warp Mechanism.
Virtual Time.
Optimal Memory Management for Time Warp Parallel Simulation.
The MIMDIX Operating System for Parallel Simulation.
Distributed Discrete-Event Simulation
Automated Parallelization of Timed Petri-Net Simulations
Parallel Simulation of Timed Petri-Nets
The Local Time Warp Approach to Parallel Simulation.
A Spectrum of Options for Parallel Simulation.
Limitation of Optimism in the Time Warp Operating System.
MTW: A Strategy for Scheduling Discrete Simulation Events for Concurrent Execution.
SPEEDES: A Multiple-Synchronization Environment for Parallel Discrete-Event Simulation
Breathing Time Warp.
Parallel Simulation of Petri Nets.
Performance Evaluation of the Bounded Time Warp Algorithm.
--TR
Virtual time
Distributed discrete-event simulation
Time series: theory and methods
Limitation of optimism in the time warp operating system
Parallel discrete event simulation
Virtual time II: storage management in conservative and optimistic systems
Optimal memory management for time warp parallel simulation
Breathing Time Warp
The local Time Warp approach to parallel simulation
The effect of memory capacity on Time Warp performance
Investigations in adaptive distributed simulation
Effect of communication overheads on Time Warp performance
An adaptive memory management protocol for Time Warp parallel simulation
Concurrent execution of timed Petri nets
Parallel simulation of timed Petri-nets
A spectrum of options for parallel simulation
Distributed Simulation of Petri Nets
Performance Oriented Development of SPMD Programs Based on Task Structure Specifications
Estimating rollback overhead for optimism control in Time Warp

--CTR
Francesco Quaglia, A restriction of the elastic time algorithm, Information Processing Letters, v.83 n.5, p.243-249, 15 September 2002
Francesco Quaglia , Vittorio Cortellessa, Grain sensitive event scheduling in time warp parallel discrete event simulation, Proceedings of the fourteenth workshop on Parallel and distributed simulation, p.173-180, May 28-31, 2000, Bologna, Italy
Francesco Quaglia, A scaled version of the elastic time algorithm, Proceedings of the fifteenth workshop on Parallel and distributed simulation, p.157-164, May 15-18, 2001, Lake Arrowhead, California, United States
David M. Nicol , Michael M. Johnson , Ann S. Yoshimura , Michael E. Goldsby, Performance modeling of the IDES framework, ACM SIGSIM Simulation Digest, v.27 n.1, p.38-45, July 1997
Francesco Quaglia, Combining periodic and probabilistic checkpointing in optimistic simulation, Proceedings of the thirteenth workshop on Parallel and distributed simulation, p.109-116, May 01-04, 1999, Atlanta, Georgia, United States
Tapas K. Som , Robert G. Sargent, A probabilistic event scheduling policy for optimistic parallel discrete event simulation, ACM SIGSIM Simulation Digest, v.28 n.1, p.56-63, July 1998
Francesco Quaglia, Event history based sparse state saving in time warp, ACM SIGSIM Simulation Digest, v.28 n.1, p.72-79, July 1998
Edward Mascarenhas , Felipe Knop , Vernon Rego, Minimum cost adaptive synchronization: experiments with the ParaSol system, Proceedings of the 29th conference on Winter simulation, p.389-396, December 07-10, 1997, Atlanta, Georgia, United States
Vittorio Cortellessa , Francesco Quaglia, Techniques for optimizing model execution I: aggressiveness/risk effects based scheduling in Time Warp, Proceedings of the 32nd conference on Winter simulation, December 10-13, 2000, Orlando, Florida
Kiran S. Panesar , Richard M. Fujimoto, Adaptive flow control in time warp, ACM SIGSIM Simulation Digest, v.27 n.1, p.108-115, July 1997
Malolan Chetlur , Nael Abu-Gazaleh , R. Radhakrishnan , P. A. Wilsey, Optimizing communication in time-warp simulators, ACM SIGSIM Simulation Digest, v.28 n.1, p.64-71, July 1998
Edward Mascarenhas , Felipe Knop , Reuben Pasquini , Vernon Rego, Minimum cost adaptive synchronization: experiments with the ParaSol system, ACM Transactions on Modeling and Computer Simulation (TOMACS), v.8 n.4, p.401-430, Oct. 1998
Reuben Pasquini , Vernon Rego, Optimistic parallel simulation over a network of workstations, Proceedings of the 31st conference on Winter simulation: Simulation---a bridge to the future, p.1610-1617, December 05-08, 1999, Phoenix, Arizona, United States
Samir R. Das, Estimating the cost of throttled execution in time warp, ACM SIGSIM Simulation Digest, v.26 n.1, p.186-189, July 1996
Francesco Quaglia , Vittorio Cortellessa, On the processor scheduling problem in time warp synchronization, ACM Transactions on Modeling and Computer Simulation (TOMACS), v.12 n.3, p.143-175, July 2002
Christoper H. Young , Radharamanan Radhakrishnan , Philip A. Wilsey, Optimism: not just for event execution anymore, Proceedings of the thirteenth workshop on Parallel and distributed simulation, p.136-143, May 01-04, 1999, Atlanta, Georgia, United States
Bernard P. Zeigler , Doohwan Kim, Design of high level modelling / high performance simulation environments, ACM SIGSIM Simulation Digest, v.26 n.1, p.154-161, July 1996
Richard M. Fujimoto, Parallel and distributed simulation, Proceedings of the 31st conference on Winter simulation: Simulation---a bridge to the future, p.122-131, December 05-08, 1999, Phoenix, Arizona, United States
S. Schmerler , Y. Tanurhan , K. D. Mller-Glaser, Advanced optimistic approaches in logic simulation, Proceedings of the conference on Design, automation and test in Europe, p.362-369, February 23-26, 1998, Le Palais des Congrs de Paris, France
Francesco Quaglia , Vittorio Cortellessa , Bruno Ciciani, Trade-Off between Sequential and Time Warp-Based Parallel Simulation, IEEE Transactions on Parallel and Distributed Systems, v.10 n.8, p.781-794, August 1999
Kevin Jones , Samir R. Das, Combining optimism limiting schemes in time warp based parallel simulations, Proceedings of the 30th conference on Winter simulation, p.499-506, December 13-16, 1998, Washington, D.C., United States
Samir R. Das, Adaptive protocols for parallel discrete event simulation, Proceedings of the 28th conference on Winter simulation, p.186-193, December 08-11, 1996, Coronado, California, United States
Ranjit Noronha , Nael B. Abu-Ghazaleh, Early cancellation: an active NIC optimization for time-warp, Proceedings of the sixteenth workshop on Parallel and distributed simulation, May 12-15, 2002, Washington, D.C.
Samir R. Das , Richard M. Fujimoto, Adaptive memory management and optimism control in time warp, ACM Transactions on Modeling and Computer Simulation (TOMACS), v.7 n.2, p.239-271, April 1997
Carl Tropper, Parallel discrete-event simulation applications, Journal of Parallel and Distributed Computing, v.62 n.3, p.327-335, March 2002
Richard M. Fujimoto, Parallel simulation: parallel and distributed simulation systems, Proceedings of the 33nd conference on Winter simulation, December 09-12, 2001, Arlington, Virginia
Alois Ferscha, Adaptive Time Warp Simulation of Timed Petri Nets, IEEE Transactions on Software Engineering, v.25 n.2, p.237-257, March 1999
Richard M. Fujimoto, Parallel simulation: distributed simulation systems, Proceedings of the 35th conference on Winter simulation: driving innovation, December 07-10, 2003, New Orleans, Louisiana
RS6000 cluster;time warp;forecast models;optimism control;PVM;petri nets