Grain sensitive event scheduling in time warp parallel discrete event simulation

Several scheduling algorithms have been proposed to determine the ne,rr 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 ty,pes of events has large variance. In this paper 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 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 ally good candidate event for the scheduling falls in. if the window length is set to Zeta, 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 LTE These results demonstrate the effectiveness of our algorithm.