Non-Preemptive Time Warp Scheduling Algorithms

The Time Warp multiprocessing scheme promises speed-up for object-oriented discrete-event simulation. The Concurrent Processing for Advanced Simulation project has constructed a LISP-based Time Warp system for implementing simulations with many large, complex objects. Since object events are not preempted, the authors are scheduling which objects have events process rather than CPU time per object. They developed approaches to scheduling, ranging from a simple round-robin mechanism to complex ones involving queue length. The authors developed ten different scheduling algorithms which they named Worst Case, Conventional Round Robin, Lowest Local Virtual Time (LVT) First, Priority LVT, Largest Queue Priority, Bradford/Fitch, Anti-Penalty, Queue Anti-Penalty, Queue Cycle, and Positive Infinity. Results show that LVT, anti-messages, rollbacks, returned messages, and anti-reminders are good parameters for scheduling of system resources. Input queue size is also an important factor, but when taken with or without LVT, it does not produce results as good as using LVT alone. The round-robin scheduler was one of the worst performers. The poor performance of the simple round-robin scheduler indicates the advantages of using state information to determine the scheduling order in the Time Warp system. Benchmarks of the schedulers showed that the Anti-Penalty scheduler performed better than the others. The Anti-Penalty algorithm is based on a composite measure of simulation advance rate, flow control, and the appearance of specific message types. The benchmark simulation executed on a five-processor Time Warp system.