A Cost Model for Selecting Checkpoint Positions in Time Warp Parallel Simulation.
AbstractRecent papers have shown that the performance of Time Warp simulators can be improved by appropriately selecting the positions of checkpoints, instead of taking them on a periodic basis. In this paper, we present a checkpointing technique in which the selection of the positions of checkpoints is based on a checkpointing-recovery cost model. Given the current state $S$, the model determines the convenience of recording $S$ as a checkpoint before the next event is executed. This is done by taking into account the position of the last taken checkpoint, the granularity (i.e., the execution time) of intermediate events, and using an estimate of the probability that $S$ will have to be restored due to rollback in the future of the execution. A synthetic benchmark in different configurations is used for evaluating and comparing this approach to classical periodic techniques. As a testing environment we used a cluster of PCs connected through a Myrinet switch coupled with a fast communication layer specifically designed to exploit the potential of this type of switch. The obtained results point out that our solution allows faster execution and, in some cases, exhibits the additional advantage that less memory is required for recording state vectors. This possibly contributes to further performance improvements when memory is a critical resource for the specific application. A performance study for the case of a cellular phone system simulation is finally reported to demonstrate the effectiveness of this solution for a real world application.
the execution of events at each LP (this is also referred to as causality). These mechanisms are,
in general, conservative or optimistic. The conservative ones enforce causality by requiring LPs to
block until certain safety criteria are met. Instead, in the optimistic mechanisms, events may be
executed in violation of timestamp order as no "block until safe" policy is considered. Whenever
a causality error is detected, a recovery procedure is invoked. This allows the exploitation of
parallelism anytime it is possible for causality errors to occurs, but they do not.
We focus on the Time Warp optimistic mechanism [10]. It allows each LP to execute events
unless its pending event set is empty and uses a checkpoint-based rollback to recover from timestamp
order violations. A rollback recovers the state of the LP to its value immediately prior the violation.
While rolling back, the LP undoes the effects of the events scheduled during the rolled back portion
of the simulation. This is done by sending a message with an antievent for each event that must be
undone. Upon the receipt of an antievent corresponding to an already executed event, the recipient
LP rolls back as well.
There exist two main checkpointing methods to support state recovery, namely incremental state
saving and sparse checkpointing ( 1 ). The former [2, 23, 25] maintains a history of before-images of
the state variables modified during event execution so that state recovery can be accomplished by
backwards crossing the logged history and copying before-images into their original state locations.
This solution has the advantage of low checkpointing overhead whenever small fractions of the state
are updated by event execution. However, in order to provide short state recovery latency, it requires
the rollback distance to be sufficiently small. The second method, namely sparse checkpointing,
is traditionally defined as recording the LP state periodically, each - event executions [11]. If a
value of - greater than one is used, the checkpointing overhead is kept low, however an additional
time penalty is added to state recovery. More precisely, state recovery to an unrecorded state
involves reloading the latest checkpoint preceding that state and re-updating state variables through
the replay of intermediate events (coasting forward). It has been shown ([4, 19]) that periodic
checkpoints taken each - event executions give rise to coasting forward with length uniformly
distributed between 0 and
Recently, solutions mixing features of both methods have been presented in [5, 15, 22].
Recent papers ([16, 17]) have shown that it is possible to achieve fast state recovery with less
checkpointing overhead than that of periodic checkpointing if an appropriate selection of checkpoint
positions is adopted. Along this line we present in this paper a checkpointing technique which selects
the positions of checkpoints basing on a cost model that associates to any state a checkpointing-
recovery overhead. The checkpointing overhead is either the time to take a checkpoint or zero
depending on whether the state is recorded or not. The recovery overhead is the time penalty
associated to a possible (future) rollback to that state. This penalty varies depending on whether
the state is recorded or not (if the state is not recorded, then it must be reconstructed through
coasting forward, so the recovery overhead depends on the position of the last taken checkpoint and
on the granularity of coasting forward events). Then, the convenience of recording that state as a
checkpoint is determined basing on the cost model. In order to solve the model, an estimate of the
probability for that state to be restored due to rollback in the future of the simulation execution
has to be performed. We present a method to solve this problem which actually requires quite
negligible computational effort. In addition, we remark that the cost model, being very simple, is
solved on-line without incurring significant overhead. As a final point, we note that the model takes
explicitly into account the granularity of any simulation event (and not just a mean value among
all the events) while determining the recovery overhead associated to a given state. This allows
our solution to exhibit the potential for providing good performance also in the case of simulations
having high variance of the event granularity (this is typical in both battlefield simulations or
simulations of complex communication systems).
We also report simulation results of a classical benchmark (the PHOLD model [7]) in several
different configurations. The obtained data show that our technique actually leads to a reduction of
the checkpointing-recovery overhead, thus allowing faster execution of the simulation. This happens
especially when the benchmark parameters are chosen to represent large and complex simulated
systems. In addition, we noted that the amount of memory used by our technique is similar to or
even less than that of previous solutions.
The remainder of the paper is organized as follows. In Section 2 a background on sparse
checkpointing methods is presented. In Section 3 our cost model and the outcoming checkpointing
technique are described. Performance data are reported in Section 4.
Related Work
As pointed out in the Introduction, the traditional approach to sparse checkpointing consists of
recording the LP state periodically each - event executions, - being the checkpoint interval. Several
analytical models have been presented to determine the time-optimal value (- opt ) for the check-point
interval. The assumption underlying all these models is that the coasting forward length is
uniformly distributed between 0 and results reported in [4, 19] have shown
that this is a good approximation of the real distribution of the coasting forward length anytime
checkpoints are taken on a periodic basis). In addition, most of these models [11, 13, 19] assume
there exists a fixed value for the time to record a state as a checkpoint (which is usually a good
approximation) and that the granularity of simulation events has small variance. A more general
model is the one presented in [21], which takes into account how the exact granularity of simulation
events affects the coasting forward time (thus the state recovery time). The relevance of this model
relies on the fact that several real world simulations, such as battlefield simulations or simulations
of mobile communication systems, have actually high variance of the event granularity which should
be taken into account in order to determine the time-optimal value - opt of the checkpoint interval.
The extended experimental study in [14] pointed out the effects of the variation of the checkpoint
interval on the rollback behavior. Several stochastic queuing networks connected with different
topologies were considered. Presented results showed that when the checkpoint interval slightly
increases a throttling effect appears which tends to reduce the number of rollbacks (this is due to
interactions among the LPs on the same processor). Instead, when the checkpoint interval is largely
increased (which produces, on the average, much longer coasting forwards), a thrashing effect gives
rise to an increase in the number of rollbacks (this is due to interactions among LPs on distinct
processors).
To tackle dynamism in the rollback behavior (which can be originated, for example, by variations
of the load on the processors or even by thrashing/throttling phenomena) a number of adaptive
techniques that dynamically adjust the value of - have been proposed. Most of them [1, 4, 19] are
based on the observation of some parameters of the LP behavior (for example the rollback frequency)
over a certain number of executed events, referred to as observation period, and recalculate the
checkpoint interval at the beginning of each period. A different approach can be found in [12],
where the recalculation of - is executed every Global-Virtual-Time (GVT) evaluation 2 .
Recently, two papers ([16, 17]) have shown that it is possible to reduce the overhead due to
checkpointing and state recovery by carefully selecting the positions of checkpoints, instead of
taking them periodically. The method in [16] takes the checkpoint decision on the basis of the
observation of differences between timestamps of two consecutive events. Whenever the execution
of an event is going to determine a large simulated time increment then a checkpoint is taken prior
to the execution of that event. This solution implicitly assumes that if the LP moves from the
state S to the state S 0 , then the probability that S will have to be restored due to rollback inThe GVT is defined as the lowest value among the timestamps of events either not yet executed or currently being
executed or carried on messages still in transit. The GVT value represents the commitment horizon of the simulation
because no rollback to a simulated time preceding GVT can ever occur. The GVT notion is used to reclaim memory
allocated for obsolete messages and state information, and to allow operations that cannot be undone (e.g., I/Os,
displaying of intermediate simulation results, etc. The memory reclaiming procedure is known as fossil collection.
the future of the execution is proportional to the simulated time increment while moving to S 0 .
Although this assumption is suited for several simulations ([3, 16]), it has never been extensively
tested; this limits the generality of such solution. The method in [17] is based on a notion of
probabilistic checkpointing which works as follows. For any state S an estimate of the probability
that it will have to be restored due to rollback is performed, namely P e (S). Then, before moving
from S to S 0 , a value ff uniformly distributed in the interval [0,1] is extracted and a checkpoint of
S is taken if ff recorded with probability equal to P e (S); therefore the higher
the probability that S will have to be restored, the higher the probability that it is recorded as a
checkpoint). What we noted in this method is that the probabilistic decision is actually memoryless
as it does not take into account the position of the last taken checkpoint to establish if S must be
recorded or not. If a checkpoint has been taken just few events ago, then S can be reconstructed
through coasting forward without incurring a significant time penalty (this is true especially in
the case of small grained coasting forward events). In this case there is no need to record S as a
checkpoint even if the probability P e (S) is not minimal.
The checkpointing technique we propose in this paper solves latter problem as the cost model
it relies on takes into account the position of the last taken checkpoint. In addition, as already
pointed out in the Introduction, the recovery overhead associated to any state is computed by
explicitly considering the granularity of any event involved in a (possible) coasting forward (and
not just a mean granularity value). Latter feature allows our solution to be highly general and to
have the potential for providing good performance in case of both small and large variance of the
event granularity.
3 Selecting Checkpoint Positions
In this section we present the cost model and the associated policy for selecting the positions of
checkpoints. Then a method to estimate probability values needed for the solution of the cost
model is introduced. Finally, we discuss the problem of memory usage which is characteristic of
any sparse checkpointing method (it is due to memory space allocated for obsolete messages which
cannot be discarded during the execution of the fossil collection procedure) and we show how to
solve this problem in our checkpointing technique with the introduction of additional (rare) periodic
checkpoints.
3.1 The Cost Model and the Selection Policy
The LP moves from one state to another due to the execution of simulation events. An example
of this is shown in Figure 1, where the arrow extending toward the right-end represents simulated
time, black circles represent event timestamps and labeled boxes represent state values at given
execution of the event e
with timestamp T
simulated time
event timestamps
LP states
e

Figure

1: The LP Moves from S to S 0 due to the Execution of e.
points in the simulated time (i.e., those points corresponding to event timestamps). In our example,
the LP moves from the state S to S 0 due to the execution of the event e with timestamp T . To
each state S passed through by the LP in the course of the simulation execution, we associate a
probability value, namely P (S), which is the probability that S will have to be restored due to
a (future) rollback. The value of P (S) will be used in the construction of the cost model which
expresses the checkpointing-recovery overhead associated to S.
Denoting with ffi s the time to save or reload a whole LP state, which is therefore assumed to be
constant as in most previous analyses (see [11, 13, 19, 21, 22]), the checkpointing overhead C(S)
associated to the state S can be expressed as follows ( 3
recorded
0 if S is not recorded
(1)
Expression (1) points out that if S is recorded as a checkpoint then there is a checkpointing
overhead associated to it which is quantified by the time to take a checkpoint ffi s .
Let us now model the recovery overhead associated to S. Before proceeding in the discussion
we remark that this overhead expresses only the latency to recover to the state S as a function of
the checkpointing activity of the LP; it does not take into account the effects of sending antievents
(recall that latter overhead is not directly dependent on checkpointing and state recovery actions,
which are those actions we are interested in). We denote as E(S) the set of all the events which
move the LP from the latest checkpointed state preceding S to S. For the example shown in Figure
2.a we have that the latest checkpointed state preceding S is X, and g. Instead,
for the example in Figure 2.b we have that the latest checkpointed state preceding S is Y , and
g. Denoting with ffi e the execution time for an event e 2 E(S), then we can associate
3 In the present analysis we use the same value ffi s for both the state saving time and the time to reload a recorded
state into the current state buffer as this is a common and realistic assumption. However, the analysis can be easily
extended to the cases where this assumption is not verified.
Y
simulated
time
checkpoint
E(S)
simulated
time
E(S)
checkpoint
(a) (b)

Figure

2: Two Examples for E(S).
the following recovery overhead R(S) to the state S ( 4
recorded
S is not recorded
(2)
Expression (2) states that, in case of rollback to S (this happens with probability P (S)), if S is
recorded as a checkpoint then the recovery overhead consists only of the time to reload S into the
current state buffer, namely ffi s . Otherwise, it consists of the time ffi s to reload the latest checkpoint
preceding S, plus the time to replay all the events in E(S) (i.e., the coasting forward time). Note
that while defining R(S) we have implicitly assumed that the probability P (S) does not change
depending on whether S is recorded or not. More technically, it is assumed that the checkpointing
actions do not affect the rollback behavior; this is a typical assumption which is common to most
analytical models (see [19, 21, 22]). Note that this assumption is not so distant from the real
behavior as usually the thrashing and throttling phenomena pointed out in [14], which are due to
variations of the checkpointing actions, are not so significant.
By combining (1) and (2) we get the following expression for the checkpointing-recovery overhead
CR(S) associated to the state S (note that CR(S) is the sum of C(S) and R(S)):
recorded
S is not recorded
Expression (3) represents our cost model. Using this model, we introduce the following selection
policy for determining the positions of checkpoints. Basically, the selection policy is such that the
state S is recorded as a checkpoint before the execution of the next event (i.e., the one which moves
the LP from S to its subsequent state) if such recording results in the minimization of the value of
CR(S). More technically, denoting with CR(S) y the value of CR(S) in case S is recorded, and with
4 Recall that ffi e keeps into account only the time to execute the event e; it does take into account the time to
send-out new events possibly scheduled during the execution of e. Therefore, ffi e expresses exactly the time to replay
e in a coasting forward, as the only purpose of coasting forward is to re-update state variables (i.e., no event is sent
out in such phase).
CR(S) n the value of CR(S) in case S is not recorded, then the selection policy can be synthesized
by the following expression:
Selection-Policy
before moving from S:
if CR(S) y - CR(S) n
then record S
else do not record S
Computing the value CR(S) y requires the knowledge of ffi s and P (S). The parameter ffi s is
usually known upon the execution of the simulation as it depends on the size (number of bytes)
of the state and on the time per byte needed for recording it ( 5 ). Instead, P (S) is unknown as
it depends on several parameters such as features proper of the simulation model and number of
processors used, among others. The presentation of a solution to estimate the value of P (S) at low
cost is delayed to Section 3.2.
Computing the value of CR(S) n requires (in addition to ffi s and P (S)) also the knowledge of
the execution time (granularity) of the events executed since the last checkpoint preceding S was
taken. In almost all simulations this granularity is determined by the type of the event. So, in
order to compute CR(S) n the LP needs to keep track of the type of the events in E(S). For the
case of simulations where the granularity of simulation events cannot be determined by their type,
the LP needs to monitor the CPU time actually used for the execution of the events in E(S).
Note that from among several parameters, the cost model determines the convenience of recording
S as a checkpoint prior to the execution of the next event basing also on:
(i) the position of the last taken checkpoint (which determines the events that are in E(S));
(ii) the exact granularity of the events executed from the last taken checkpoint (i.e., the granularity
of the events in E(S)).
We remark that the information in points (i) and (ii) actually encodes the maximal knowledge
related to the portion of the simulation already executed and to past checkpointing actions which
is relevant to establish the amount of recovery overhead associated to S in case S is not recorded
and a rollback to it occurs. More precisely, the positions of the checkpoints other than the latest
one preceding S, and the granularity of any event out of the set E(S) do not affect the time to
reconstruct S in case it is not recorded and a rollback to it occurs.
We would like to discuss next a fundamental point. The discussion is preceded by a simple
introductory example. Let us consider the portion of the simulation execution shown in Figure 3.
5 Recall that the recording of S can be done either via software (this is the typical solution) or through the use of
special purpose hardware [8].
checkpoint
checkpoint
E(S)
simulated simulated
checkpoint
(a) (b)
e

Figure

3: Effects of the Recording of S on CR(S 0 ).
immediately follows S and the event which moves the LP from S to S 0 is - e. In case S is recorded as
a checkpoint (see Figure 3.a), the set E(S 0 ) contains only the event - e so the checkpointing-recovery
overhead CR(S 0 ) associated to the state S 0 is:
recorded
recorded
Instead, if S is not recorded as a checkpoint (see Figure 3.b), then the set E(S 0 ) contains the
same events as the set E(S) (i.e., e 1 and e 2 in our example) plus the event -
e. Therefore, the
checkpointing-recovery overhead CR(S 0 ) becomes as follows:
recorded
recorded
(note that also to derive expressions (4) and (5) we suppose P (S 0 ) independent of checkpointing
actions).
The previous example points out that the outcoming decision of the selection policy on whether
the state S must be recorded or not, determines the shape of the function CR associated to the
states that will follow S in the simulation execution. This implies that taking the checkpoint
decision basing only on the minimization of the checkpointing-recovery overhead associated to
the current state of the LP could not lead to the minimization of the whole checkpointing-recovery
overhead of the simulation (i.e., that resulting from the sum of the checkpointing-recovery overheads
associated to all the states passed through in the course of the simulation). However, we recall
that such (global) minimization requires the knowledge of the exact sequence of states that will be
passed through in the course of the simulation execution (i.e., the exact sequence of events that
will be executed), which is unknown to any LP. Furthermore, even if such sequence is known, a
selection policy based on that minimization would require enormous computational effort to take
the checkpoint decision, which would dramatically decrease the execution speed of the simulation.
In conclusion, the selection policy here introduced selects the best checkpoint positions with respect
to the portion of the simulation already executed which is known by any LP.
3.2 Estimating Probability Values
As pointed out in Section 3.1, for any state S the solution of the cost model (i.e., computing the
values of CR(S) y and CR(S) n ) needs the knowledge of the probability P (S). In this section we
present a method to estimate this value. The method has resemblances to those presented in [3, 17].
Before entering the description, we recall that the method must be such that the CPU time and
the memory space needed for keeping track of statistical data must approach to zero, and that
the CPU time to compute the estimate of P (S) must approach to zero as well. If this does not
happen, the method could severely decrease the execution speed of the simulation. Note that if
the method uses a large amount of memory, then two negative effects on performance may occur:
(i) the management of large memory may lead to poor locality of reference in the virtual memory
system; (ii) the amount of memory destined to record messages and state information is reduced,
which may require more frequent GVT calculation and fossil collection execution.
Let st(S) denote the value of the simulated time associated to the state S and let e, with
timestamp t(e), be the event which moves the LP from S to its subsequent state. The execution
of the event e produces an increment in the simulated time of the LP, moving it from st(S) to
t(e). Then, to any state S we can associate a simulated time interval, namely I(S), whose length
is which is delimited as follows:
The probability P (S) that the state S will have to be restored due to a (future) rollback
corresponds to the probability that a rollback will occur in the simulated time interval I(S). Recall
that a rollback in the interval I(S) occurs either because events are scheduled later with timestamps
in that interval (i.e., after e is executed, an event e 0 such that st(S) ! t(e scheduled for
the LP) or because the LP that scheduled the event e rolls back revoking e (i.e., the antievent of e
arrives after e is executed).
We estimate the probability P (S) basing on the length of the interval I(S) and on the monitoring
of the frequency of rollback occurrence in simulated time intervals of a specified length. We define
simulated time points t i such
the simulated time positive semi-axis into intervals I For each state S, there exists an
interval I i such that the length of I(S), namely L(I(S)), is within that interval (i.e., t i -
For each interval I i the LP keeps a variable R i , initially set to zero, which counts the amount
of rollback occurrences in simulated time intervals I(X), such that t i -
whenever a rollback occurs to a state X such that t i - the variable R i is increased
by one; recall that computing the length of I(X) in order to identify the corresponding counter
R i to be updated is a quite simple operation, it only requires to compute the difference between
two simulated time values: one is the simulated time of the state X, the other is the timestamp
of the event which moved the LP from X to its subsequent state). Then, for any state S such
that estimated as R i =N , where N is a local variable which counts the
number of states passed through (i.e., the number of events executed by the LP 6 ).
Overall, the sequence of steps to take the checkpoint decision before moving from S is as follows.
Upon (but before) the execution of the event e which moves the LP from S to its subsequent state,
the length L(I(S)) of the interval I(S) is computed and the corresponding variable R i is identified.
Then, the estimate of P (S) is computed as the ratio between R i and N and the outcoming value is
used to solve the cost model; finally, the selection policy (see Section 3.1) determines the convenience
of recording S prior to the execution of the event e basing on the solution of the cost model.
A simple uniform decomposition of the simulated time positive semi-axis can be obtained by
imposing length equal to \Delta on each interval I i and by defining a value t max such that I
In this case the value max determines the number of intervals of the decomposition
(i.e., the amount of memory destined to the counters R i ). Furthermore, the value of \Delta can be chosen
depending on the average values of the distribution functions of the timestamp increment. In this
way, the individuation of the counter to be updated each time a rollback occurs, or the individuation
of the counters to estimate probability values is quite simple and introduces negligible overhead.
For example, when a rollback occurs to a state X, the index i of the counter R i to be updated is
easily computed as follows (recall again that L(I(X)) is computed by simply taking the difference
between to simulated time values):
Note that previous estimation method can be modified in order to cope with non-stationary
probability values which can be caused, for example, by variations of either the load on the processors
or the behavior of the LPs in the simulated time. In particular, basing on the common belief
that in most simulations the near past behavior is a good approximation of the near future behavior,
then probability values can be estimated by using statistical data on rollback occurrences which
are related to a temporal window (instead of those collected from the beginning of the execution).
Few hundred of events usually constitute a window length producing reliable results [4, 17, 19].
6 The events executed in coasting forward are not counted by N . They are not real simulation events as they are
actually an artefact of the state recovery procedure. Therefore, states passed through in any coasting forward are
not real simulation states of the LP.
CRy (S)
Pr (S)
Pe (S)
(b)
CRy (S)
(a)
Pr (S)
Pe (S)
interval for Pe (S) where the
selection policy produces a
interval for Pe (S) where the
selection policy produces a
correct decision correct decision

Figure

4: General Cases for the Functions CR y (S) and CR n (S).
3.2.1 A Discussion on the Effectiveness of the Estimation Method
The method we have proposed to estimate P (S) has the advantage that it can be implemented at
very low cost (in terms of both CPU time and memory space). On the other hand, it shows the
drawback that the estimated probability value might not be quite close to the real one (note that no
control on the trust of the estimate performed). In order to solve this problem, complex statistical
methods should be used which might have negative impact on performance, thus, in general, this
is not a feasible solution. We will show, however, that the effects of an estimate of probability
values which is not quite good are significant only for particular states (i.e., for a subset of the
states passed through in the course of the simulation). So the simple method here introduced is,
in general, enough refined to represent an effective solution for our specific problem.
Before proceeding in the discussion, we introduce the following simple notion. We say that the
selection policy introduced in Section 3.1 leads to a wrong decision anytime the checkpoint decision
based on the estimated value of P (S) is different from the one that would have been obtained by
considering the real value of P (S); otherwise we say that the selection policy produces a correct
decision.
In

Figure

4.a and in Figure 4.b we show two cases for the linear functions CR(S) y and CR(S) n
versus the value of P (S). Recall that when P (S) is equal to zero, CR n (S) is equal to zero as well, and
CR y (S) is equal to ffi s . The cases shown are general as the two functions have an intersection point
within the interval [0,1) for P (S) (a more particular situation is obtained when CR
in the whole interval do not intersect or, at best,
they intersect when P 1). We denote as b
P the value of P (S) corresponding to the intersection
point; in addition, we denote as P r (S) the real value of P (S) and with P e (S) the corresponding
estimated value.
Suppose
(see

Figure

4.a), in this case CR y (S) ? CR n (S), so there is no real
convenience of recording S as a checkpoint. The same decision is taken by the selection policy for any
estimated value P e (S) less than b
therefore, for any value P e
P the selection policy produces
always a correct decision. Suppose P r (S) - b
(see

Figure

4.b), in this case, CR y (S) - CR n (S) so
there is a real convenience of recording S. The same decision is taken by the selection policy for any
estimated value P e (S) larger than or equal to b
therefore, for any value P e (S) - b
P the selection
policy produces always a correct decision. Overall, we have that the selection policy produces a
correct decision anytime one of the following two cases occurs:
are lower than b
C2: both P r (S) and P e (S) are higher than or equal to b
Instead, it produces a wrong decision anytime one of the following two cases occurs:
Case C3 or C4 may occur if:
(i) the value of P r (S) is quite close to b
P (in this case, we may get a wrong decision even with
a small distance between P r (S) and P e (S); anyway the distance must be such that it moves
e (S) to the opposite side of P r (S) with respect to the value b
(ii) the value or P r (S) is quite far from b
P and a very large distance exists between P r (S) and
(anyway the distance must be such that it moves P e (S) to the opposite side of P r (S)
with respect to the value b
From previous considerations, we argue that in order for the selection policy to produce a
wrong decision (cases C3 and C4), then a set of conditions must be satisfied (i.e., those producing
situations (i) or (ii)). So the states for which these conditions are actually satisfied will be, in
general, a (small) subset of all the states passed through in the course of the simulation. Therefore,
for the majority of the states, the selection policy will produce correct decisions ( 7 ). This feature
derives from the fact that the selection policy actually maps values of a continuous function (i.e.,
the difference between CR y (S) and CR n (S)) into a boolean domain. This mapping into such a
discrete domain removes the effects of "noise" (i.e., the effects of an estimate of probability values
which is not good) unless the noise itself over-steps a threshold.
7 Recall, in addition, that there exists a set of states for which cases C3 and C4 can never occur independently of the
distance between the real and the estimated probability values. These are all the states S such that CRn (S) ! CRy (S)
in the whole interval [0,1) for P (S). For any of these states either the two functions CRn (S) and CRy (S) do not
intersect or they intersect in the point b
cases C3 and C4 cannot occur as neither Pr (S) nor Pe (S) can be
higher than one. For all these states the selection policy always produces a correct decision.
3.3 Adding Periodic Checkpoints to Cope with Memory Usage
Any sparse checkpointing solution suffers from a problem which is known as the memory usage
problem. A brief description of this problem is provided in this section. Then a solution allowing
our checkpointing technique to cope with this problem is presented.
Basically, the memory usage problem is related to the notion of GVT and to the fossil collection
procedure (which recovers memory allocated for obsolete state information and messages). Specif-
ically, as rollback to a simulated time equal to GVT is possible, then, in order to correctly support
state recovery, each LP must retain the latest recorded state (i.e., the latest checkpoint) with simulated
time T less than or equal to GVT and also all the messages carrying events with timestamp
larger than T ; therefore, that checkpoint and all those massages cannot be discarded during the
execution of the fossil collection procedure. If very few states are recorded in the course of the
simulation, then it is possible for the number of messages which must be retained to be very large.
The drawback incurred is that the amount of memory recovered during any fossil collection may be
small, thus the fossil collection procedure is invoked frequently (as memory saturates frequently).
This may have detrimental effects on performance.
Our checkpointing technique allows the possibility that very few states are recorded in the
course of the simulation execution. This may happen whenever for any state S, the value of the
probability P (S) approaches to zero. As an extreme case, if P (S) is exactly equal to zero for any
state S, then the selection policy of Section 3.1 will never induce the LP to take a checkpoint. This
pushes our technique to incur the memory usage problem. In order to prevent this problem, we
allow the LP to take (rare) periodic checkpoints. To this purpose, the LP maintains two integer
variables, namely max dist and event ex. The variable max dist records the maximum number
of event executions allowed between two consecutive checkpoint operations. The variable event ex
represents the actual distance, in terms of events, from the last checkpoint operation. By using
these two variables, the selection policy is modified as follows:
Modified-Selection-Policy
before moving from S:
then record S
else do not record S
The modified selection policy does not allow the distance between two consecutive checkpoints
to be larger than max dist events (i.e., max dist state transitions), thus avoiding the memory
usage problem. Checkpointing techniques based on periodic checkpoints tackle the memory usage
problem adopting defaults for the maximum value of the checkpoint interval - max which usually
are between 15 and 30 (see [4, 19]). Any value within that interval will be well suited for max dist.
3.4 A Final Description of the Checkpointing Technique
There is just another point to be fixed in order to provide a final, complete description of our
checkpointing technique. The modified selection policy introduced in Section 3.3 (just as the
original one) relies on the solution of the cost model which, in turn, needs the estimate of probability
values. This means that the policy cannot be applied if at least few statistical data are not available
(note that the problem of the absence of statistical data for the selection of the initial value of the
proper of the checkpointing technique is a common problem to almost all existing
techniques [4, 16, 17, 19]). To overcome this problem, we partition the execution of the LP into two
phases. Phase-1 starts at the beginning of the simulation execution and consists of few hundred
events. During this phase, the LP collect statistical data to estimate probability values, and records
as checkpoints all the states passed through (this can be easily done by adopting the modified
selection policy with max dist initially set to one). During the second phase, namely Phase-2,
the LP continues to collect statistical data (possibly using a windowing mechanism) and takes
the checkpoint decision basing on the modified selection policy with a value for max dist selected
within the interval [15,30]. In Figure 5, the complete behavior of the LP is reported.
(few hundred events)
settings: dist := 1
actions: collect statistical data; select checkpoint positions basing on the modified selection policy
Phase-2 (till the end of the simulation)
settings: select x 2 [15; 30]; max dist := x
actions: collect statistical data; select checkpoint positions basing on the modified selection policy

Figure

5: The Complete LP Behavior (only those Actions Relevant to the Checkpointing Technique
are Shown).
4 A Performance Study
In this section experimental results are reported to compare the performance achievable by using
the checkpointing technique proposed in this paper (hereafter CT1) to the one of previous solutions.
We have considered three previous checkpointing techniques for the comparison: the one presented
by Ronngren and Ayani (CT2) [19]; the one presented by Fleischmann and Wilsey (CT3) [4] and
the one presented by Quaglia (CT4) [17]. Both CT2 and CT3 induce the LP to take checkpoints
on a periodic basis. CT2 is based on an analytical model which defines the value of the time-optimal
checkpoint interval (the assumptions underlying the model have been already discussed
in Section 2). The model is used to recalculate the value of the checkpoint interval - basing on
the observed variations of the rollback frequency. CT3 is actually a heuristic algorithm for the
dynamic recalculation of - which has been derived basing on extensive profiling and analysis of
parallel optimistic simulation of digital systems. It is based on the monitoring of a cost function
which equals the sum of checkpointing and coasting forward overheads. The value one and an
adaptation direction towards increasing values is initially selected for - (the adaptation step is one,
i.e., at each adaptation point - is increased by one). Then, the adaptation direction is inverted
each time the monitored value of the cost function shows a significant increase. CT4 relies on the
probabilistic checkpoint decision already discussed in Section 2.
We did not consider any incremental state saving method in our comparison. This is because
previous studies ([13, 18, 20]) have already pointed out that incremental state saving and sparse
checkpointing outperform each other in distinct classes of simulation problems (so the two approaches
are effective each in a distinct domain). Specifically, incremental methods are preferable
for simulations with very large state size, very small portions of the state updated by event execution
and quite short rollback distances. For any other simulation setting, sparse checkpointing
provides better performance.
Before showing the results of the comparative analysis, we describe the main features of the used
hardware/software architecture, present the selected benchmark and introduce the performance
parameters we have measured.
4.1 The Hardware/Software Architecture and the Benchmark
As hardware architecture we used a cluster of machines (Pentium II 300 MHz - 128 Mbytes RAM)
connected via Ethernet. The number of machines in the cluster is four. Inter-processor communication
relies on message passing supported by PVM [24]. There is an instance of the Time Warp
kernel on each processor. The kernel schedules LPs for event execution according to the Smallest-
Timestamp-First policy; antievents are sent aggressively (i.e., as soon as the LP rolls back [9]);
fossil collection is executed periodically each one second.
We tested the performance of the checkpointing techniques using the synthetic benchmark
known as PHOLD model, originally presented in [7]. It consists of a fixed number of LPs and of a
constant number of jobs circulating among the LPs (that is referred to as job population). Both
the routing of jobs among the LPs and the timestamp increments are taken from some stochastic
distributions. We have chosen this benchmark for two main reasons: (i) its parameters (e.g., event
execution time, size of the state, etc.) can be easily modified, (ii) it is one of the most used
benchmarks for testing performance of checkpointing techniques [1, 16, 19, 21]. In addition, it is
important to remark that this benchmark usually shows a rollback behavior similar to many other
synthetic benchmarks and to several real world models. For this benchmark, we considered three
different configurations, with progressively more complex features concerning both the execution
time (i.e., the granularity) of simulation events and the behavior of the LPs (i.e., how they route jobs
among each other). In the third configuration, the benchmark actually models a complex system.
These configurations are separately described in details in each of the following paragraphs.
First Configuration (CONF-1). In this configuration, the PHOLD model is composed of 64
homogeneous LPs. The timestamp increment is exponentially distributed with mean 10 simulated
time units for all the LPs. The execution time (granularity) for any event is fixed at 140 microsec-
onds. The job population is one job per LP and jobs are equally likely to be forwarded to any other
LP. Two distinct cases for the size of the LP state were considered: (i) each LP has a fictitious
state of 2 Kbytes; in this case the time for recording the entire state is approximately
microseconds; (ii) each LP has a fictitious state of 8 Kbytes; in this case the time for recording the
entire state is approximately microseconds. In both cases, the fictitious state consists of
an array of integers, and the times reported above were obtained recording the state by copying all
its entries, one by one. The case 2 Kbytes state size models simulations with medium/small state
granularity (with respect to the event granularity), whereas, the case 8 Kbytes state size models
simulations with large state granularity.
Second Configuration (CONF-2). This configuration has the same features of CONF-1 except
for what concerns the granularity of simulation events. There are three distinct types of jobs (i.e.,
of simulation events), namely a, b and c. The three types have granularity
respectively. The job population is one job
per LP (the type of the job is selected from among the three job types according to an uniform
distribution). After a job is served (but before it is forwarded to another LP), the job type is
redefined by uniformly selecting it in the set fa; b; cg; so there is a probability of 1/3 that the
type of the job remains unchanged when it is forwarded to another LP. For this configuration we
considered the same two distinct state sizes as those of CONF-1.
Third Configuration (CONF-3). This configuration has the same features of CONF-2, except
for what concerns the routing of jobs among the LPs. There are 8 hot spot LPs to which 30% of
all jobs must be routed. The hot spot LPs change in the course of the simulation (they change
each 3 \Theta 10 4 simulated time units and the sequence of the changes is defined prior to the simulation
execution by randomly picking up new hot spots among all the LPs). This configuration possibly
gives rise to simulations which do not reach steady state for what concerns the rollback behavior;
furthermore, it is complex from both the point of view of the event granularity and the point of
view of the routing decisions which determine how simulation events are distributed among the
LPs. These features allow CONF-3 to nicely approximate simulation models of complex systems.
The same two state sizes of previous configurations were considered for CONF-3.
The three configurations of the benchmark were run using all the four machines of the cluster.
Each machine runs 16 LP (no other user load runs on any machine). For the checkpointing technique
CT1, probability values are estimated by using an uniform decomposition of the simulated time
positive semi-axis with
windowing mechanism is used in order to compute the estimate basing on statistical data which
refer to the last 500 executed events at most). The same decomposition is adopted for CT4. Finally,
for both CT2 and CT3 the recalculation of the value of the checkpoint interval - is executed each
500 events (i.e., the observation period is fixed at 500 events for both the techniques).
4.2 Performance Parameters
We report measures related to the following parameters:
ffl the event rate (ER), that is the number of committed events per second; this parameter
indicates how fast is the simulation execution with a given checkpointing technique;
ffl the efficiency (EFF), that is the ration between the number of committed events and the
total number of executed events (excluding coasting forward ones); this parameter indicates
how the percentage of CPU time spent executing productive simulation work (i.e., committed
events) is affected by the checkpointing technique;
ffl the average checkpointing overhead (ACO) per state, that is the average time spent for check-pointing
operations per each state passed through in the course of the simulation (note that
the number of states passed through is actually equal to the number of executed events, so
ACO also expresses the checkpointing overhead per event) ( 8 );
ffl the average recovery latency (ARL), that is the average time for state recovery in case of
rollback.
In addition, we also report some data to point out the memory utilization (MU) under different
checkpointing techniques. We recall that the average memory utilization cannot be observed without
interfering with the simulation execution. Instead, the maximum memory utilization (i.e., the
8 States which are passed through during the execution of any coasting forward are not taken into account
in the calculation of ACO. Therefore ACO expresses the checkpointing overhead per event computed overall the
committed/rolled-back events. As already pointed out in a previous note, coasting forward events are actually an
artefact of the state recovery procedure, so they are not real simulation events.
maximum amount of memory destined for keeping checkpoints and messages) can be easily measured
Note that the memory utilization must take into account also the memory destined to
messages carrying the events as this is an indicator for the memory usage problem pointed out
in Section 3.3. For each configuration of the benchmark we report the average observed values of
previous parameters, computed over 20 runs that were all done with different seeds for the random
number generation. At least 5 \Theta 10 6 committed event were simulated in each run.
4.3 Experimental Results
In the following paragraphs we report the obtained results for all the selected configurations of
the benchmark. Then, a final discussion on the results is presented. Note that we report also the
parameter values measured for the case of checkpoint before the execution of each simulation event
(this checkpointing technique is often referred to as copy state saving - CSS). A comparison with
results obtained under CSS is important to point out the real performance gain achievable through
sparse checkpointing techniques (so the simulations with CSS act as control simulations).
Case 2 Kbyte State Size
Checkpointing ACO ARL EFF ER maximum MU
Technique (microsec.) (microsec.) ([%]) (committed events per sec.) (Mbytes)
CSS 70 70 71:74 8544 19.7
CT4 22 178 73:82 10423 8.3
Case 8 Kbyte State Size
Checkpointing ACO ARL EFF ER maximum MU
Technique (microsec.) (microsec.) ([%]) (committed events per sec.) (Mbytes)
CSS 280 280 72:95 5981 54.9
44 663 74:54 8304 12.2
CT4 43 584 73:34 8617 11.5

Figure

CONF-1. The obtained results are reported in Figure 6 for both the case of 2 Kbytes and the
case 8 Kbytes state size. As general consideration, we have that the techniques from CT1 to CT4
show around the same values for EFF, which indicates that they affect the percentage of CPU
time spent executing productive simulation work almost in the same way. Instead, CSS originates
9 In our simulations the content of a message has size 32 bytes.
smaller values for EFF. This phenomenon is supposed to derive from the longer average recovery
latency, namely ARL, of CT1-CT4, which, as pointed out in [14], may give rise to a throttled
execution of the simulation (i.e., an execution with slightly less rollbacks). This indicates that,
compared to CSS, sparse checkpointing techniques not only show the advantage of a better balance
between checkpointing and recovery overheads, but, usually, also allow a reduction of the negative
effects of rollback on performance 10 .
For the case 2 Kbytes state size, we have that the performance under CT2 and that under CT3
are quite similar, with CT2 allowing slightly faster execution of the simulation (i.e., a higher value
for ER). Also, the amounts of memory used by the techniques are similar (CT3 shows a slightly
larger value of maximum MU). Compared to CSS, both these techniques allow faster execution, up
to 18% and 17% respectively. In addition, they reduce the amount of used memory of around 2.3
times.
and CT4 perform better than the other sparse checkpointing techniques (the values of ER
under CT1 and CT4 are larger than those observed for CT2 and CT3), with CT1 allowing faster
execution, up to 3%, compared to CT4. This phenomenon can be explained by looking at data
concerning ACO and ARL. The values of ACO under CT1 and CT4 are less than those under CT2
and CT3 (this is true especially for the CT1 technique which compared to CT2 and CT3 exhibits ER
which is between 6% and 7% higher). Furthermore, both CT1 and CT4 show values for ARL similar
to those of CT2 and CT3, thus allowing, on the average, fast state recovery with less checkpointing
overhead. This points out that an appropriate selection of checkpoint positions actually allows a
reduction of the checkpointing-recovery overhead. The reported values of maximum MU indicate
that all the techniques from CT1 to CT4 use around the same amount of memory.
The results obtained for the case of 8 Kbytes state size are quite similar to the previous ones.
The main difference is that, compared to CSS, all the techniques CT1-CT4 show a performance
gain which is further amplified. This is because ACO under CSS in the case of 8 Kbytes state
size is notably larger, up to 4 times, that that in the case of 2 Kbytes state size; instead, sparse
checkpointing techniques allow ACO in the case of 8 Kbytes state size to be less than 2 times larger
compared to that of the case 2 Kbytes state size.
CONF-2. Results reported in this section (see Figure 7) allow us to point out how the different
checkpointing techniques tackle the high variance of the event granularity (recall that CONF-2 is
such that there are three different event types with three distinct granularities). The data show that
the performance provided by CT2 and CT4 for CONF-2 is worse that that observed for CONF-1.
CT3 shows around the same performance. CT1 performs slightly better than under CONF-1 (it
shows a value of ACO which less than that observed for CONF-1). The consequence is that the
This is confirmed by results reported in [21].
Case 2 Kbytes State Size
Checkpointing ACO ARL EFF ER maximum MU
Technique (microsec.) (microsec.) ([%]) (committed events per sec.) (Mbytes)
CSS 70 70 70:48 8421 18.9
CT4 22 182 73:85 10226 7.1
Case 8 Kbytes State Size
Checkpointing ACO ARL EFF ER maximum MU
Technique (microsec.) (microsec.) ([%]) (committed events per sec.) (Mbytes)
CSS 280 280 74:46 6096 54.0

Figure

7: Results for CONF-2
performance gain of CT1 over the other techniques is slightly amplified compared to CONF-1. This
behavior directly derives form the high variance of the event granularity of CONF-2. As CT1 takes
into account the granularity of any event while selecting the positions of checkpoints, then CT1
will recognize a sequence of large grained events executed from the last taken checkpoint, and will
not allow this sequence to be long (i.e., it will break the sequence through a checkpoint). This will
happen especially if the sequence pushes the LP to pass through a state that has high (estimated)
probability to be restored due to a future rollback. Such sequences of events are not recognized
(and thus not broken) by the other techniques which may originate long recovery latency. So, in
order to bound that latency, these techniques induce the LPs to take more checkpoints. Finally,
we note that also for this configuration, the amounts of memory used by the different techniques
(except for the case of CSS) is quite similar.
CONF-3. The results for this configuration (see Figure 8) point out how the checkpointing
techniques tackle both the high variance of the event granularity and a complex (and also variable)
behavior for the routing of jobs among the LPs. Recall that this configuration pushes the benchmark
to exhibits features quite close to those of the simulation model of a complex system. It must be
noted that CONF-3 gives rise to simulations with higher efficiency compared to CONF-1 and
CONF-2; this is because the presence of the hot spot LPs allows the simulation to advance less
"chaotically" as a good percentage of the jobs are routed towards the hot spots (i.e., jobs are free
to move everywhere with lower probability). Basically, the performance gain shown by CT1 for the
previous configurations is confirmed. This indicates that the windowing approach for the collection
Case 2 Kbytes State Size
Checkpointing ACO ARL EFF ER maximum MU
Technique (microsec.) (microsec.) ([%]) (committed events per sec.) (Mbytes)
CSS 70 70 78:43 10654 25.1
CT3 19 262 82:54 11932 7.1
Case 8 Kbytes State Size
Checkpointing ACO ARL EFF ER maximum MU
Technique (microsec.) (microsec.) ([%]) (committed events per sec.) (Mbytes)
CSS 280 280 80:16 7846 68.6

Figure

8: Results for CONF-3
of statistical data to estimate probability values actually allows CT1 to get the potential to react to
dynamic changes in the rollback behavior originated by the variable routing of jobs in the lifetime of
the simulation. In particular, for the case 2 Kbytes state size, CT1 allows faster execution, between
3% and 10%, compared to all the other sparse checkpointing techniques. For the case 8 Kbytes
state size, the gain is between 3% and 8%. This gain derives especially from the much lower ACO
of CT1 compared to the other techniques.
4.3.1 General Comments
The performance data collected in this study indicate that there is a real advantage of an appropriate
selection of the positions of checkpoints. This advantage is actually amplified for the case of
simulation models exhibiting complex features. For these models, the checkpointing technique
must treat each state passed through in a specific way (i.e., the decision on whether that state
must be recorded as a checkpoint has to be taken by looking at features proper of the state, namely
probability to be restored due to rollback, position of the last taken checkpoint and granularity of
intermediate events). If this does not happen, there is the risk that a state which has very high
probability to be restored due to rollback is not recorded even if: (i) the last checkpoint was taken
several event executions ago and (ii) the intermediate events were large grained. This may have a
detrimental effect on performance in the case a rollback to that state really occurs, as the latency
to recover to that state through coasting forward might be quite long.
Checkpointing techniques in which the checkpoint decision is taken on a periodic basis do not
have the potential to tackle previous problem directly. The only way for these techniques to bound
the recovery latency is to select an "adequately small" value of the checkpoint interval, which in
turn may push the checkpointing overhead to be non minimal. The same recovery latency can be
obtained at the expense of less checkpointing overhead if an adequate selection of the checkpoint
positions is adopted.
Another important point which has been highlighted by our study is that a checkpointing
technique for an appropriate selection of the positions of checkpoints (like CT1) can be designed and
implemented basing on very simple statistical methods, which introduce quite negligible overhead
for being implemented (this is a basic requirement to be satisfied in order for the technique to not
over-charge the simulation program). Nevertheless, the technique itself has the potential to provide
quite good performance.

Summary

In this paper we have presented a general solution for tackling the checkpoint problem in Time Warp
simulations. The checkpointing technique we have proposed selects the positions of the checkpoints
basing on a cost model which expresses the checkpointing-recovery overhead associated to any
state passed through in the course of the simulation. The cost model determines the convenience
of recording the current state before the execution of the next event. This requires an estimate of
the probability that the current state will have to be restored due to rollback. We propose a low-overhead
simple solution for this problem and discuss its effectiveness for this specific application.
Simulation results are also reported to quantify the performance achievable by our checkpointing
technique. To this purpose a classical benchmark in several different configurations has been used.
The data show that the selection of the positions of checkpoints induced by our technique improves
performance compared to existing approaches, including conventional periodic checkpointing tech-
niques. This happens especially when the benchmark parameters are selected in order to let it
represent a simulation model with complex behavior. This indicates that the presented solution is
highly general, having the potential to allow faster execution in a wide class of simulations.

Acknowledgments

The author would like to thank Bruno Ciciani for many interesting discussions on the checkpoint
problem in Time Warp simulators. Special thank goes to Vittorio Cortellessa for his help in the
preparation of the simulation code.



--R

"Run-Time Selection of the Checkpoint Interval in Time Warp Simulations"
"Reducing Rollback Overhead in Time Warp Based Distributed Simulation with Optimized Incremental State Saving"
"Estimating Rollback Overhead for Optimism Control in Time Warp"
"Comparative Analysis of Periodic State Saving Techniques in Time Warp Simulators"
"State Saving for Interactive Optimistic Simulation"
"Parallel Discrete Event Simulation"
"Performance of Time Warp Under Synthetic Workloads"
"Design and Evaluation of the Rollback Chip: Special Purpose Hardware for Time Warp"
"Space Management and Cancellation Mechanisms for Time Warp"
"Virtual Time"
"Selecting the Checkpoint Interval in Time Warp Simulation"
"Adaptive Checkpoint Intervals in an Optimistically Synchronized Parallel Digital System Simulator"
"An Analytical Comparison of Periodic Checkpointing and Incremental State Saving"
"Effects of the Checkpoint Interval on Time and Space in Time Warp"
"Rollback-Based Parallel Discrete Event Simulation by Using Hybrid State Saving"
"Event History Based Sparse State Saving in Time Warp"
"Combining Periodic and Probabilistic Checkpointing in Optimistic Simulation"
"Fast-Software-Checkpointing in Optimistic Simulation: Embedding State Saving into the Event Routine Instructions"
"Adaptive Checkpointing in Time Warp"
"A Comparative Study of State Saving Mechanisms for Time Warp Synchronized Parallel Discrete Event Simulation"
"Event Sensitive State Saving in Time Warp Parallel Discrete Event Simu- lations"
"An Analytical Model for Hybrid Checkpointing in Time Warp Distributed Simulation"
"Incremental State Saving in SPEEDES Using C Plus Plus"
"A Framework for Parallel Distributed Computing"
"External State Management System for Optimistic Parallel Simulation"
--TR

--CTR
Francesco Quaglia , Andrea Santoro , Bruno Ciciani, Conditional checkpoint abort: an alternative semantic for re-synchronization in CCL, Proceedings of the sixteenth workshop on Parallel and distributed simulation, May 12-15, 2002, Washington, D.C.
Andrea Santoro , Francesco Quaglia, Communications and network: benefits from semi-asynchronous checkpointing for time warp simulations of a large state PCS model, Proceedings of the 33nd conference on Winter simulation, December 09-12, 2001, Arlington, Virginia
Andrea Santoro , Francesco Quaglia, Transparent State Management for Optimistic Synchronization in the High Level Architecture, Simulation, v.82 n.1, p.5-20, January   2006
Francesco Quaglia , Andrea Santoro, Modeling and optimization of non-blocking checkpointing for optimistic simulation on myrinet clusters, Journal of Parallel and Distributed Computing, v.65 n.6, p.667-677, June 2005
Diego Cucuzzo , Stefano D'Alessio , Francesco Quaglia , Paolo Romano, A Lightweight Heuristic-based Mechanism for Collecting Committed Consistent Global States in Optimistic Simulation, Proceedings of the 11th IEEE International Symposium on Distributed Simulation and Real-Time Applications, p.227-234, October 22-26, 2007
Moon Jung Chung , Jinsheng Xu, An overhead reducing technique for time Warp, Journal of Parallel and Distributed Computing, v.65 n.1, p.65-73, January 2005
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
Francesco Quaglia , Andrea Santoro, Modeling and optimization of non-blocking checkpointing for optimistic simulation on myrinet clusters, Proceedings of the 17th annual international conference on Supercomputing, June 23-26, 2003, San Francisco, CA, USA
Francesco Quaglia , Andrea Santoro, Nonblocking Checkpointing for Optimistic Parallel Simulation: Description and an Implementation, IEEE Transactions on Parallel and Distributed Systems, v.14 n.6, p.593-610, June
rollback-recovery;checkpointing;time warp;performance optimization;optimistic synchronization;cost models;parallel discrete-event simulation