Non-Preemptive Time Warp Scheduling Algorithms

by Christopher Burdorf, Jed B. Marti


Full Document

FormatFile SizeNotes
PDF file 0.7 MB

Use Adobe Acrobat Reader version 10 or higher for the best experience.


Purchase Print Copy

 FormatList Price Price
Add to Cart Paperback23 pages $20.00 $16.00 20% Web Discount

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.

Research conducted by

This report is part of the RAND Corporation Note series. The note was a product of the RAND Corporation from 1979 to 1993 that reported other outputs of sponsored research for general distribution.

Permission is given to duplicate this electronic document for personal use only, as long as it is unaltered and complete. Copies may not be duplicated for commercial purposes. Unauthorized posting of RAND PDFs to a non-RAND Web site is prohibited. RAND PDFs are protected under copyright law. For information on reprint and linking permissions, please visit the RAND Permissions page.

The RAND Corporation is a nonprofit institution that helps improve policy and decisionmaking through research and analysis. RAND's publications do not necessarily reflect the opinions of its research clients and sponsors.