Discrete-event simulation and the event horizon part 2: event list management

ABSTRACT

The event horizon is a very important concept that applies to both parallel and sequential discrete-event simulations. By exploiting the event horizon, parallel simulations can processes events optimistically in a risk-free manner (i.e., without requiring antimessages) using adaptable "breathing" time cycles with variable time widths. Additionally, exploiting the event horizon can significantly reduce the overhead of event list management that is common to virtually all discrete-event simulations. This paper is a continuation of work previously reported at PADS94. In that report, a complete mathematical formulation of the event horizon was derived under equilibrium conditions using the hold model. Various forms of the beta density function were consequently used to verify the predicted results of the analytic model. This second report describes how the concept of the event horizon can also be applied to event list management. By exploiting the event horizon, the performance of several priority queue data structures are improved including: linked lists, various binary trees, and heaps. A somewhat detailed description of these modified data structures along with other relevant background information is provided for completeness. Performance results for each of these priority queue data structure is provided.

REFERENCES

• 1: Steven Bellenot, Performance of a riskfree Time Warp operating system, Proceedings of the seventh workshop on Parallel and distributed simulation, p.155-158, May 16-19, 1993, San Diego, California, United States
• 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: Chien-Chun Chou , Steven C. Bruell , Douglas W. Jones , Wen Zhang, A generalized hold model, Proceedings of the 25th conference on Winter simulation, p.756-761, December 12-15, 1993, Los Angeles, California, United States [doi>10.1145/256563.256838]
• 4: Kehsiung Chung , Janche Sang , Vernon Rego, A performance comparison of event calendar algorithms: an empirical approach, Software—Practice & Experience, v.23 n.10, p.1107-1138, Oct. 1993 [doi>10.1002/spe.4380231005]
• 5: Crane C., 1972. "Linear Lists and Priority Queues as Balanced Binary Trees." STAN-CS-72-259, Computer Science Department, Stanford University.
• 6: Damitio M., et. at., 1994. "Comparing the Breathing Time Buckets Algorithm and the Time Warp Operating System on a Transputer Architecture." In proceedings of the SCS European Simulation Multiconference, Pages 141-145.
• 7: Horowitz E. and Sahni S., 1976. "Fundamentals of Data Structures." Computer Science Press, Inc.
• 8: 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]
• 9: Theodore G. Lewis , M. Z. Smith, Applying Data Structures, Houghton Mifflin Co., Boston, MA, 1982
• 10: Papoulis A. 1965. "Probability, Random Variables, and Stochastic Processes." McGraw-Hill Series in System Science, New York, pages 104, 147.
• 11: Sushil K. Prasad , Basem Naqib, Effectiveness of global event queues in rollback reduction and load balancing, Proceedings of the ninth workshop on Parallel and distributed simulation, p.187-190, June 13-16, 1995, Lake Placid, New York, United States
• 12: William H. Press , Brian P. Flannery , Saul A. Teukolsky , William T. Vetterling, Numerical recipes in C: the art of scientific computing, Cambridge University Press, New York, NY, 1988
• 13: Robert Rönngren , Jens Riboe , Rassul Ayani, Lazy queue: an efficient implementation of the pending-event set, Proceedings of the 24th annual symposium on Simulation, p.194-204, April 1991, New Orleans, Louisiana, United States
• 14: Robert Rönngren , Rassul Ayani , Richard M. Fujimoto , Samir R. Das, Efficient implementation of event sets in Time Warp, Proceedings of the seventh workshop on Parallel and distributed simulation, p.101-108, May 16-19, 1993, San Diego, California, United States
• 15: Saumyendra Sengupta , Carl Phillip Korobkin, C++ object-oriented data structures, Springer-Verlag New York, Inc., New York, NY, 1994
• 16: 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]
• 17: Steinman J., 1992. "SPEEDES: A MultipIe-Synchronization Environment for Parallel Discrete-Event Simulation." International Journal in Computer Simulation. Vol. 2, No. 3. Pages 251-286.
• 18: Jeff S. Steinman, Breathing Time Warp, ACM SIGSIM Simulation Digest, v.23 n.1, p.109-118, July 1993
• 19: Jeff S. Steinman, Discrete-event simulation and the event horizon, Proceedings of the eighth workshop on Parallel and distributed simulation, p.39-49, July 06-08, 1994, Edinburgh, Scotland, United Kingdom

INDEX TERMS

Primary Classification:
  I. Computing Methodologies
  I.6 SIMULATION AND MODELING
      I.6.8 Types of Simulation
          Subjects: Discrete event

General Terms:
Measurement, Performance, Theory

Keywords:
SPEEDES, Parallel Simulation, Event List Management, Priority Queues, SPEEDES Qheap, Event Horizon