Ladder queue: An O(1) priority queue structure for large-scale discrete event simulation

ABSTRACT

This article describes a new priority queue implementation for managing the pending event set in discrete event simulation. Extensive empirical results demonstrate that it consistently outperforms other current popular candidates. This new implementation, called Ladder Queue, is also theoretically justified to have O(1) amortized access time complexity, as long as the mean jump parameter of the priority increment distribution is finite and greater than zero, regardless of its variance. Many practical priority increment distributions satisfy this condition including unbounded variance distributions like the Pareto distribution. This renders the LadderQ the ideal discrete event queue structure for stable O(1) performance even under practical queue distributions with infinite variance. Numerical simulations ranging from 100 to 10 million events affirm the O(1) property of LadderQ and that it is a superior structure for large-scale discrete event simulation.

REFERENCES

• 1: 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]
• 2: Samir Das , Richard Fujimoto , Kiran Panesar , Don Allison , Maria Hybinette, GTW: a time warp system for shared memory multiprocessors, Proceedings of the 26th conference on Winter simulation, p.1332-1339, December 11-14, 1994, Orlando, Florida, United States
• 3: K. Bruce Erickson , Richard E. Ladner , Anthony Lamarca, Optimizing static calendar queues, ACM Transactions on Modeling and Computer Simulation (TOMACS), v.10 n.3, p.179-214, July 2000 [doi>10.1145/361026.361028]
• 4: Fall, K. and Varadhan, K. 2002. The NS Manual. UCB/LBNL/VINT Network simulator v2. http://www.isi.edu/nsnam/ns/.
• 5: 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]
• 6: Marin, M. 1997. An empirical comparison of priority queue algorithms. Tech. Rep., Oxford University.
• 7: S. K. Park , K. W. Miller, Random number generators: good ones are hard to find, Communications of the ACM, v.31 n.10, p.1192-1201, Oct. 1988 [doi>10.1145/63039.63042]
• 8: Robert Rönngren , Rassul Ayani, A comparative study of parallel and sequential priority queue algorithms, ACM Transactions on Modeling and Computer Simulation (TOMACS), v.7 n.2, p.157-209, April 1997 [doi>10.1145/249204.249205]
• 9: Rönngren, R., Riboe, J., and Ayani, R. 1993. Lazy queue: New approach to implementing the pending event set. Int. J. Comput. Simul. 3, 303--332.
• 10: Schwetman, H. 1996. CSIM18 User's Guide. Mesquite Software, Inc., Austin, TX.
• 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: Tarjan, R. E. 1985. Amortized computational complexity. SIAM J. Alg. Disc. Meth. 6, 2 (Apr.), 306--318.

INDEX TERMS

Primary Classification:
  E. Data
  E.1 DATA STRUCTURES

Additional Classification:
  F. Theory of Computation
  F.2 ANALYSIS OF ALGORITHMS AND PROBLEM COMPLEXITY

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

General Terms:
Algorithms, Performance

Keywords:
Pending event set implementations, calendar queue, priority queue