Channel based sequential simulation

ABSTRACT

Sequential discrete event simulation is widely employed to study the behavior of many systems. Events are typically managed in a central event list which is implemented as a priority queue ordered by event timestamps. Most research to improve sequential simulation performance has focused on improving the priority queue implementations. Recent work has demonstrated that asynchronous conservative parallel discrete event simulation systems can achieve better sequential performance under some conditions, but worse performance under other conditions. This paper introduces a new sequential discrete event simulation algorithm that can exhibit some of the same performance advantages of asynchronous conservative parallel discrete event simulation algorithms and has complexity no more than that of central event list algorithms in the worst case.

REFERENCES

• 1: T. D. Blanchard , T. W. Lake , S. J. Turner, Cooperative acceleration: robust conservative distributed discrete event simulation, Proceedings of the eighth workshop on Parallel and distributed simulation, p.58-64, July 06-08, 1994, Edinburgh, Scotland, United Kingdom
• 2: R. Brown, Calendar queues: a fast 0(1) priority queue implementation for the simulation event set problem, Communications of the ACM, v.31 n.10, p.1220-1227, Oct. 1988 [doi>10.1145/63039.63045]
• 3: R. E. Bryant, SIMULATION OF PACKET COMMUNICATION ARCHITECTURE COMPUTER SYSTEMS, Massachusetts Institute of Technology, Cambridge, MA, 1977
• 4: Cai, W., and S. J. Turner. 1990. An algorithm for distributed discrete-event simulation - the "carrier null message" approach. In Proceedings of the SCS Multiconference on Distributed Simulation, Volume 22 of SCS Simulation Series, 3--8.
• 5: Chandy, K. M., and J. Misra. 1979. Distributed simulation: A case study in design and verification of distributed programs. IEEE Transactions on Software Engineering SE-5 (5): 440--452.
• 6: Roger Curry , Cameron Kiddle , Rob Simmonds , Brian Unger, Sequential Performance of Asynchronous Conservative PDES Algorithms, Proceedings of the 19th Workshop on Principles of Advanced and Distributed Simulation, p.217-226, June 01-03, 2005 [doi>10.1109/PADS.2005.25]
• 7: Richard M. Fujimoto, Parallel and Distribution Simulation Systems, John Wiley & Sons, Inc., New York, NY, 1999
• 8: David R. Jefferson, Virtual time, ACM Transactions on Programming Languages and Systems (TOPLAS), v.7 n.3, p.404-425, July 1985 [doi>10.1145/3916.3988]
• 9: Douglas W. Jones, An empirical comparison of priority-queue and event-set implementations, Communications of the ACM, v.29 n.4, p.300-311, April 1986 [doi>10.1145/5684.5686]
• 10: William M. McCormack , Robert G. Sargent, Analysis of future event set algorithms for discrete event simulation, Communications of the ACM, v.24 n.12, p.801-812, Dec. 1981 [doi>10.1145/358800.358803]
• 11: Daniel Dominic Sleator , Robert Endre Tarjan, Self-adjusting binary search trees, Journal of the ACM (JACM), v.32 n.3, p.652-686, July 1985 [doi>10.1145/3828.3835]
• 12: Jean G. Vaucher , Pierre Duval, A comparison of simulation event list algorithms, Communications of the ACM, v.18 n.4, p.223-230, April 1975 [doi>10.1145/360715.360758]