Scheduling Algorithms for Time Warp Parallel Discrete Event Simulation

Abstract

In parallel discrete event simulation, each part of the simulated system is modeled by distinct logical process (LP). The time warp synchronization protocol lets the LPs schedule simulation events whenever they are available and uses rollback to recover from out of order computations. Usually we have several LPs executing on the same processor, so it is important to use proper scheduling algorithm to determine the order in which LPs should execute on a processor. Scheduling algorithm affects the amount of rollbacks which directly influences the simulation execution time. Therefore, the term “good” for a scheduling algorithm is interpreted as the capability of the algorithm to allow fast completion of the simulation by producing a low amount of rollback.

The following two scheduling algorithms for time warp parallel discrete event simulation will be presented:

• Grain Sensitive Scheduling Algorithm

• Service Oriented Scheduling Algorithm

Each of these algorithms improves simulation performance, when it is used for simulations with specific characteristics, by reducing the number of rollbacks.