Calendar queues: a fast 0(1) priority queue implementation for the simulation event set problem

Subscribe (Full Service)


	Search: The ACM Digital Library The Guide

	Feedback

Calendar queues: a fast 0(1) priority queue implementation for the simulation event set problem

Full text

Pdf (1.25 MB)

Source

Communications of the ACM archive
Volume 31 , Issue 10 (October 1988) table of contents

Pages: 1220 - 1227

Year of Publication: 1988

ISSN:0001-0782

Author

R. Brown

Publisher

ACM New York, NY, USA

Bibliometrics

Downloads (6 Weeks): 35, Downloads (12 Months): 236, Citation Count: 72

Additional Information:

abstract references cited by index terms

Tools and Actions:	Request Permissions Review this Article Save this Article to a Binder Display Formats: BibTeX EndNote ACM Ref

DOI Bookmark:	Use this link to bookmark this Article: http://doi.acm.org/10.1145/63039.63045 What is a DOI?

ABSTRACT

A new priority queue implementation for the future event set problem is described in this article. The new implementation is shown experimentally to be O(1) in queue size for the priority increment distributions recently considered by Jones in his review article. It displays hold times three times shorter than splay trees for a queue size of 10,000 events. The new implementation, called a calendar queue, is a very simple structure of the multiple list variety using a novel solution to the overflow problem.

REFERENCES

Note: OCR errors may be found in this Reference List extracted from the full text article. ACM has opted to expose the complete List rather than only correct and linked references.

	1	John H. Blackstone, Jr. , Gary L. Hogg , Don T. Phillips, A two-list synchronization procedure for discrete event simulation, Communications of the ACM, v.24 n.12, p.825-829, Dec. 1981 [doi>10.1145/358800.358805]
	2	Brown, M.R. Implementation and analysis of binomial queue algorithms. SIAM }. Comput. 7, 3 (Aug. 1978), 298-319.
	3	Davey, D., and Vaucher, J. Self-optimizing partitioned sequencing sets for discrete event simulation. Infor 18, I (Feb. 1980), 41-61.
	4	Francon, J., Viennot, G., and Vuillemin, J. Description and analysis of an efficient priority queue representation. In Proceedings of the 19th Annual Symposium on Foundations of Computer Science (Ann Arbor, Mich., Oct. 16-18}. IEEE, Piscataway, N.J., 1978, pp. 1-7.
	5	W. R. Franta , Kurt Maly, An efficient data structure for the simulation event set, Communications of the ACM, v.20 n.8, p.596-602, Aug. 1977 [doi>10.1145/359763.359801]
	6	W. R. Franta , Kurt Maly, A comparison of heaps and the TL structure for the simulation event set, Communications of the ACM, v.21 n.10, p.873-875, Oct. 1978 [doi>10.1145/359619.359637]
	7	Fredman, M.L., Sedgewick, R., Sleator, D., and Tarjan, R. The pairing heap: A new form of self-adjusting heap. Submitted for publication.
	8	James O. Henriksen, An improved events list algorithm, Proceedings of the 9th conference on Winter simulation, p.546-557, December 05-07, 1977, Gaitersburg, MD
	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	Kingston, J. H. Analysis of algorithms for the simulation event list. Ph.D. thesis, Basser Dept. of Computer Science, Univ. of Sydney, Australia, July 1984.
	11	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]
	12	Nix, R. An evaluation of pagodas. Res. Rep. 164, Dept. of Computer Science, Yale Univ., New Haven, Conn., no date.
	13	Daniel Dominic Sleator , Robert Endre Tarjan, Self-adjusting binary trees, Proceedings of the fifteenth annual ACM symposium on Theory of computing, p.235-245, December 1983 [doi>10.1145/800061.808752]
	14	Daniel Dominic Sleator , Robert Endre Tarjan, Self adjusting heaps, SIAM Journal on Computing, v.15 n.1, p.52-69, Feb. 1986 [doi>10.1137/0215004]
	15	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]
	16	Ernst G. Ulrich, Event manipulation for discrete simulations requiring large numbers of events, Communications of the ACM, v.21 n.9, p.777-785, Sept. 1978 [doi>10.1145/359588.359611]
	17	Jean Vuillemin, A data structure for manipulating priority queues, Communications of the ACM, v.21 n.4, p.309-315, April 1978 [doi>10.1145/359460.359478]

CITED BY 72

	David M. Nicol, Scalability, locality, partitioning and synchronization PDES, ACM SIGSIM Simulation Digest, v.28 n.1, p.5-11, July 1998
	Brian Unger , Zhonge Xiao , John Cleary , Jya-Jang Tsai , Carey Williamson, Parallel shared-memory simulator performance for large ATM networks, ACM Transactions on Modeling and Computer Simulation (TOMACS), v.10 n.4, p.358-391, Oct. 2000
	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
	Kaushik Ghosh , Richard M. Fujimoto , Karsten Schwan, PORTS: a parallel, optimistic, real-time simulator, ACM SIGSIM Simulation Digest, v.24 n.1, p.24-31, July 1994
	Jeffrey S. Steinman, Discrete-event simulation and the event horizon part 2: event list management, ACM SIGSIM Simulation Digest, v.26 n.1, p.170-178, July 1996
	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
	Christopher D. Carothers , Kalyan S. Perumalla , Richard M. Fujimoto, The effect of state-saving in optimistic simulation on a cache-coherent non-uniform memory access architecture, Proceedings of the 31st conference on Winter simulation: Simulation---a bridge to the future, p.1624-1633, December 05-08, 1999, Phoenix, Arizona, United States
	Alan T. Krantz, Analysis of an efficient algorithm for the hard-sphere problem, ACM Transactions on Modeling and Computer Simulation (TOMACS), v.6 n.3, p.185-209, July 1996
	Christopher D. Carothers , Richard M. Fujimoto, Background execution of time warp programs, ACM SIGSIM Simulation Digest, v.26 n.1, p.12-19, July 1996
	George Varghese , Anthony Lauck, Hashed and hierarchical timing wheels: efficient data structures for implementing a timer facility, IEEE/ACM Transactions on Networking (TON), v.5 n.6, p.824-834, Dec. 1997
	Ion Stoica , Hui Zhang , T. S. Eugene Ng, A hierarchical fair service curve algorithm for link-sharing, real-time and priority services, ACM SIGCOMM Computer Communication Review, v.27 n.4, p.249-262, Oct. 1997
	Frode B. Nilson, GMSim: a tool for compositional GSMP modeling, Proceedings of the 30th conference on Winter simulation, p.555-562, December 13-16, 1998, Washington, D.C., United States
	Mauricio Marín, Billiards and related systems on the bulk-synchronous parallel model, ACM SIGSIM Simulation Digest, v.27 n.1, p.164-171, July 1997
	Samir R. Das , Richard M. Fujimoto, A performance study of the cancelback protocol for Time Warp, ACM SIGSIM Simulation Digest, v.23 n.1, p.135-142, July 1993
	Sushil K. Prasad , Basem Naqib, Effectiveness of global event queues in rollback reduction and load balancing, ACM SIGSIM Simulation Digest, v.25 n.1, p.187-190, July 1995
	Jong Suk Ahn , Peter B. Danzig, Packet network simulation: speedup and accuracy versus timing granularity, IEEE/ACM Transactions on Networking (TON), v.4 n.5, p.743-757, Oct. 1996
	Christopher D. Carothers , Richard M. Fujimoto , Yi-Bing Lin, A case study in simulating PCS networks using Time Warp, ACM SIGSIM Simulation Digest, v.25 n.1, p.87-94, July 1995
	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
	David M. Nicol, The cost of conservative synchronization in parallel discrete event simulations, Journal of the ACM (JACM), v.40 n.2, p.304-333, April 1993
	Ion Stoica , Hui Zhang , T. S. Eugene Ng, A hierarchical fair service curve algorithm for link-sharing, real-time, and priority services, IEEE/ACM Transactions on Networking (TON), v.8 n.2, p.185-199, April 2000
	Christopher D. Carothers , Richard M. Fujimoto , Paul England, Effect of communication overheads on Time Warp performance: an experimental study, ACM SIGSIM Simulation Digest, v.24 n.1, p.118-125, July 1994
	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
	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
	Robert Rönngren , Rassul Ayani , Richard M. Fujimoto , Samir R. Das, Efficient implementation of event sets in Time Warp, ACM SIGSIM Simulation Digest, v.23 n.1, p.101-108, July 1993
	Hui Zhang , Srinivasan Keshav, Comparison of rate-based service disciplines, ACM SIGCOMM Computer Communication Review, v.21 n.4, p.113-121, Sept. 1991
	Boris V. Cherkassky , Andrew V. Goldberg , Craig Silverstein, Buckets, heaps, lists, and monotone priority queues, Proceedings of the eighth annual ACM-SIAM symposium on Discrete algorithms, p.83-92, January 05-07, 1997, New Orleans, Louisiana, United States
	Christopher D. Carothers , David Bauer , Shawn Pearce, ROSS: a high-performance, low memory, modular time warp system, Proceedings of the fourteenth workshop on Parallel and distributed simulation, p.53-60, May 28-31, 2000, Bologna, Italy
	Voon-Yee Vee , Wen-Jing Hsu, Pal: a new fossil collector for time warp, Proceedings of the sixteenth workshop on Parallel and distributed simulation, May 12-15, 2002, Washington, D.C.
	Samir R. Das , Richard M. Fujimoto, Adaptive memory management and optimism control in time warp, ACM Transactions on Modeling and Computer Simulation (TOMACS), v.7 n.2, p.239-271, April 1997
	Christopher D. Carothers , Yi-Bing Lin , Richard M. Fujimoto, Simulating population dependent PCS network models using time warp, Proceedings of the 27th conference on Winter simulation, p.555-562, December 03-06, 1995, Arlington, Virginia, United States
	Rohit Dube, Scalable hierarchical coarse-grained timers, ACM SIGOPS Operating Systems Review, v.34 n.1, p.11-20, January 2000
	Sung-Whan Moon , Kang G. Shin , Jennifer Rexford, Scalable Hardware Priority Queue Architectures for High-Speed Packet Switches, IEEE Transactions on Computers, v.49 n.11, p.1215-1227, November 2000
	Garrett R. Yaun , David Bauer , Harshad L. Bhutada , Christopher D. Carothers , Murat Yuksel , Shivkumar Kalyanaraman, Large-scale network simulation techniques: examples of TCP and OSPF models, ACM SIGCOMM Computer Communication Review, v.33 n.3, July 2003
	Ashvin Goel , Luca Abeni , Charles Krasic , Jim Snow , Jonathan Walpole, Supporting time-sensitive applications on a commodity OS, ACM SIGOPS Operating Systems Review, v.36 n.SI, Winter 2002
	Mutsumi Fujihara , Kiyoshi Yoneda, Simulation through explicit state description and its application to semiconductor fab operation, Proceedings of the 24th conference on Winter simulation, p.899-907, December 13-16, 1992, Arlington, Virginia, United States
	Eunmi Choi , Dugki Min, Event scheduling schemes for time warp on distributed systems, Proceedings of the 28th conference on Winter simulation, p.661-668, December 08-11, 1996, Coronado, California, United States
	Farokh Jamalyaria , Rori Rohlfs , Russell Schwartz, Queue-based method for efficient simulation of biological self-assembly systems, Journal of Computational Physics, v.204 n.1, p.100-120, 20 March 2005
	Sushil K. Prasad , Zhiyong Cao, Parallel distributed simulation and modeling methods: SyncSim: a synchronous simple optimistic simulation technique based on a global parallel heap event queue, Proceedings of the 35th conference on Winter simulation: driving innovation, December 07-10, 2003, New Orleans, Louisiana
	George F. Riley, Simulation of large scale networks II: large-scale network simulations with GTNetS, Proceedings of the 35th conference on Winter simulation: driving innovation, December 07-10, 2003, New Orleans, Louisiana
	Peter Sanders, Fast priority queues for cached memory, Journal of Experimental Algorithmics (JEA), 5, p.7-es, 2000
	Azzedine Boukerche , Sajal K. Das , Alessandro Fabbri, SWiMNet: a scalable parallel simulation testbed for wireless and mobile networks, Wireless Networks, v.7 n.5, p.467-486, September 2001
	Wai Teng Tang , Rick Siow Mong Goh , Ian Li-Jin Thng, Ladder queue: An O(1) priority queue structure for large-scale discrete event simulation, ACM Transactions on Modeling and Computer Simulation (TOMACS), v.15 n.3, p.175-204, July 2005
	Ashvin Goel , Luca Abeni , Charles Krasic , Jim Snow , Jonathan Walpole, Supporting time-sensitive applications on a commodity OS, Proceedings of the 5th symposium on Operating systems design and implementation Due to copyright restrictions we are not able to make the PDFs for this conference available for downloading , December 09-11, 2002, Boston, Massachusetts
	Lukasz Golab , M. Tamer Özsu, Update-pattern-aware modeling and processing of continuous queries, Proceedings of the 2005 ACM SIGMOD international conference on Management of data, June 14-16, 2005, Baltimore, Maryland
	Christopher D. Carothers , Richard M. Fujimoto, Efficient Execution of Time Warp Programs on Heterogeneous, NOW Platforms, IEEE Transactions on Parallel and Distributed Systems, v.11 n.3, p.299-317, March 2000
	Liron Yatziv , Alberto Bartesaghi , Guillermo Sapiro, O(N) implementation of the fast marching algorithm, Journal of Computational Physics, v.212 n.2, p.393-399, 1 March 2006
	G. Ciardo , R. L. Jones, III , A. S. Miner , R. I. Siminiceanu, Logic and stochastic modeling with SMART, Performance Evaluation, v.63 n.6, p.578-608, June 2006
	Daniel R. Figueiredo , Benyuan Liu , Yang Guo , Jim Kurose , Don Towsley, On the efficiency of fluid simulation of networks, Computer Networks: The International Journal of Computer and Telecommunications Networking, v.50 n.12, p.1974-1994, 24 August 2006
	Romain Brette, Exact simulation of integrate-and-fire models with synaptic conductances, Neural Computation, v.18 n.8, p.2004-2027, August 2006
	David W. Bauer, Jr. , Ernest H. Page, Optimistic parallel discrete event simulation of the event-based transmission line matrix method, Proceedings of the 39th conference on Winter simulation: 40 years! The best is yet to come, December 09-12, 2007, Washington D.C.
	N. Manjikian , W. M. Loucks, Using split event sets to form and schedule event combinations in discrete event simulation, Proceedings of the 25th annual symposium on Simulation, p.184-191, April 1992, Orlando, Florida, United States
	Darrin West , John Cleary , Jim Hofmann , Larry Mellon , Jim Ramsey, Infrastructure for rapid execution of strike-planning systems, Proceedings of the 27th conference on Winter simulation, p.1207-1214, December 03-06, 1995, Arlington, Virginia, United States
	Katerina Asdre , Stavros D. Nikolopoulos, P-tree structures and event horizon: efficient event-set implementations, Proceedings of the 37th conference on Winter simulation, December 04-07, 2005, Orlando, Florida
	Gerald Paul, A Complexity O(1) priority queue for event driven molecular dynamics simulations, Journal of Computational Physics, v.221 n.2, p.615-625, February, 2007
	David X. Wei , Pei Cao, NS-2 TCP-Linux: an NS-2 TCP implementation with congestion control algorithms from Linux, Proceeding from the 2006 workshop on ns-2: the IP network simulator, October 10-10, 2006, Pisa, Italy
	Mathieu Lacage , Thomas R. Henderson, Yet another network simulator, Proceeding from the 2006 workshop on ns-2: the IP network simulator, October 10-10, 2006, Pisa, Italy
	David W. Bauer, Jr. , Christopher D. Carothers, Eliminating remote message passing in optimistic simulation, Proceedings of the 37th conference on Winter simulation, December 03-06, 2006, Monterey, California
	G. Horn , A. Kvalbein , J. Blomskøld , E. Nilsen, An empirical comparison of generators for self similar simulated traffic, Performance Evaluation, v.64 n.2, p.162-190, February, 2007
	Aggelos Ioannou , Manolis G. H. Katevenis, Pipelined heap (priority queue) management for advanced scheduling in high-speed networks, IEEE/ACM Transactions on Networking (TON), v.15 n.2, p.450-461, April 2007
	Vern Paxson, Bro: a system for detecting network intruders in real-time, Proceedings of the 7th conference on USENIX Security Symposium, 1998, p.3-3, January 26-29, 1998, San Antonio, Texas
	Cameron Kiddle , Rob Simmonds , Brian Unger, Channel based sequential simulation, Proceedings of the 37th conference on Winter simulation, December 04-07, 2005, Orlando, Florida
	Don Carney , Uğur Çetintemel , Alex Rasin , Stan Zdonik , Mitch Cherniack , Mike Stonebraker, Operator scheduling in a data stream manager, Proceedings of the 29th international conference on Very large data bases, p.838-849, September 09-12, 2003, Berlin, Germany
	Samson Lee , John Leaney , Tim O'Neill , Mark Hunter, Performance Benchmark of a Parallel and Distributed Network Simulator, Proceedings of the 19th Workshop on Principles of Advanced and Distributed Simulation, p.101-108, June 01-03, 2005
	Garrett Yaun , Christopher D. Carothers , Shivkumar Kalyanaraman, Large-Scale TCP Models Using Optimistic Parallel Simulation, Proceedings of the seventeenth workshop on Parallel and distributed simulation, p.153, June 10-13, 2003
	P. M. Papazoglou , D. A. Karras , R. C. Papademetriou, On a new generation of event scheduling algorithms and evaluation techniques for efficient simulation modelling of large scale cellular networks bandwidth management based on multitasking theory, WSEAS TRANSACTIONS on COMMUNICATIONS, v.7 n.10, p.1024-1034, October 2008
	P. M. Papazoglou , D. A. Karras , R. C. Papademetriou, An efficient scheduling mechanism for simulating concurrent events in wireless communications based on an improved priority queue (PQ) TDM layered multi-threading approach, WSEAS TRANSACTIONS on COMMUNICATIONS, v.7 n.3, p.207-215, March 2008
	Yun Zeng , Dimitris Samaras , Wei Chen , Qunsheng Peng, Topology cuts: A novel min-cut/max-flow algorithm for topology preserving segmentation in N-D images, Computer Vision and Image Understanding, v.112 n.1, p.81-90, October, 2008
	Jan Himmelspach , Adelinde M. Uhrmacher, The event queue problem and PDevs, Proceedings of the 2007 spring simulation multiconference, March 25-29, 2007, Norfolk, Virginia
	Anthony Sulistio , Uros Cibej , Sushil K. Prasad , Rajkumar Buyya, GarQ: An efficient scheduling data structure for advance reservations of grid resources, International Journal of Parallel, Emergent and Distributed Systems, v.24 n.1, p.1-19, February 2009
	Jan Himmelspach , Roland Ewald , Adelinde M. Uhrmacher, A flexible and scalable experimentation layer, Proceedings of the 40th Conference on Winter Simulation, December 07-10, 2008, Miami, Florida
	Yi Sun , Xiaolin Hu, Performance Measurement of Dynamic Structure DEVS for Large-Scale Cellular Space Models, Simulation, v.85 n.5, p.335-351, May 2009
	P. M. Papazoglou , D. A. Karras , R. C. Papademetriou, Concurrent events scheduling for efficient simulation modelling of large scale cellular networks based on multitasking real time scheduling techniques and analysis, Proceedings of the 12th WSEAS international conference on Communications, p.347-355, July 23-25, 2008, Heraklion, Greece