Grain sensitive event scheduling in time warp parallel discrete event simulation

Several scheduling algorithms have been proposed to determine the next event to be executed on a processor in a time warp parallel discrete event simulation. However none of them is specifically designed for simulations where the execution time (or granularity) for different types of events has large variance. We present a grain sensitive scheduling algorithm which addresses this problem. In our solution, the scheduling decision depends on both timestamp and granularity values with the aim at giving higher priority to small grain events even if their timestamp is not the lowest one (i.e. the closest one to the commitment horizon of the simulation). This implicitly limits the optimism of the execution of large grain events that, if rolled back, would produce a large waste of CPU time. The algorithm is adaptive in that it relies on the dynamic recalculation of the length of a simulated time window within which the timestamp of any good candidate event for the scheduling falls in. If the window length is set to zero, then the algorithm behaves like the standard Lowest-Timestamp-First (LTF) scheduling algorithm. Simulation results of a classical benchmark in several different configurations are reported for a performance comparison with LTF: these results demonstrate the effectiveness of our algorithm.