Rick Siow Mong Goh
Abstract
Priority queues are essential function blocks in numerous applications such as discrete event simulations. This paper describes and exemplifies the ease of obtaining high performance priority queues using a two-tier list-based structure. This new implementation, called the Twol structure, is amalgamated with three priority queues, namely, the Henriksen's queue, splay tree and skew heap, to enhance the efficiency of these basal priority queue structures. Using a model that combines traditional average case and amortized complexity analysis, Twol-amalgamated priority queues that maintain N active events are theoretically proven to offer O(1) expected amortized complexity under reasonable assumptions. They are also demonstrated empirically to offer stable near O(1) performance for widely varying priority increment distributions and for queue sizes ranging from 10 to 10 million. Extensive empirical results show that the Twol-amalgamated priority queues consistently outperform those basal structures (i.e., without the Twol structure) with an average speedup of about three to five times on widely different hardware architectures. These results provide testimony that the Twol-amalgamated priority queues are suitable for implementation in sizeable application scenarios such as, but not limited to, large-scale discrete event simulation.
- Bentley, J. 1985. Thanks, heaps. Commun. ACM 28, 3 (Mar.), 245--250.]] Google Scholar
- Brown, R. 1988. Calendar queues: A fast O(1) priority queue implementation for the simulation event set problem. Commun. ACM 24, 12 (Dec.), 825--829.]] Google Scholar
- Comfort, J. C. 1984. The simulation of a master-slave event set processor. Simulation 42, 3 (Mar.), 117--124.]]Google Scholar
- Das, S., Fujimoto, R., Panesar, K., Allison, D., and Hybinette, M. 1994. GTW: A time warp system for shared memory multiprocessors. In Proceedings of the 1994 Winter Simulation Conference, 1332--1339.]] Google Scholar
- Erickson, K. B., Ladner, R. E., and LaMarca, A. 2000. Optimizing static calendar queues. ACM Trans. Model. Comput. Simul. 10, 3 (July) 179--214.]] Google Scholar
- Fall, K. and Varadhan, K. 2002. The ns Manual. UCB/LBNL/VINT Network simulator v2. http://www.isi.edu/nsnam/ns/.]]Google Scholar
- Gomes, F., Franks, S., Unger, B., Xiao, Z., Cleary, J., and Covington, A.. 1995. SimKit: A high performance logical process simulation class library in C++. In Proceedings of the 1995 Winter Simulation Conference, 706--713.]] Google Scholar
- Hagai, A. and Patt-Shamir, B. 2001. Multiple priority, per flow, dual GCRA rate controller for ATM switches. In IEEE Workshop on High Performance Switching and Routing, 169--174.]]Google Scholar
- Henriksen, J. O. 1977. An improved events list algorithm. In Proceedings of the 1977 Winter Simulation Conference, 547--557.]] Google Scholar
- Henriksen, J. O. and Crain, R. C. 1996. GPSS/H Reference Manual, 4th ed. Wolverine Software Corporation, Annandale, VA.]]Google Scholar
- Henriksen, J. O. 1997. An introduction to SLX. In Proceedings of the 1997 Winter Simulation Conference, 559--566.]] Google Scholar
- Jones, D. W. 1986. An empirical comparison of priority-queue and event-set implementations. Commun. ACM 29, 4 (Apr.), 300--311.]] Google Scholar
- Jones, D. W. 1989. Concurrent operations on priority queues. Commun. ACM 32, 1 (Jan.), 132--137.]] Google Scholar
- Kingston, J. 1986. Analysis of Henriksen's queue for the simulation event set. SIAM J. Comput. 15, 3 (Aug.), 887--902.]] Google Scholar
- L'Ecuyer, P. and Champoux, Y. 2001. Estimating small cell-loss ratios in ATM switches via importance sampling. ACM Trans. Model. Comput. Simul. 11, 1 (Jan.), 76--105.]] Google Scholar
- Narlikar, G. and Zane, F. 2001. Performance modeling for fast IP lookups. In Proceedings of the 2001 ACM SIGMETRICS International Conference on Measurement and Modeling of Computer Systems, 1--12.]] Google Scholar
- Oh, S. and Ahn, J. 1998. Dynamic calendar queue. In Proceedings of the 32nd Annual Simulation Symposium, 20--25.]] Google Scholar
- Park, S. K. and Miller, K. W. 1988. Random number generators: Good ones are hard to find. Commun. ACM 31, 10 (Oct.), 1192--1201.]] Google Scholar
- Pritsker, A. and Pegden, C. 1979. Introduction to Simulation and SLAM, 3rd ed. Wiley, New York.]] Google Scholar
- 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.]]Google Scholar
- Rönngren, R. and Ayani, R. 1997. A comparative study of parallel and sequential priority queue algorithms. ACM Trans. Model. Comput. Simul. 7, 2 (Apr.), 157--209.]] Google Scholar
- Schwetman, H. 1996. CSIM18 User's Guide. Mesquite Software, Inc, Austin, TX.]]Google Scholar
- Sleator, D. D. and Tarjan, R. E. 1985. Self-adjusting binary search trees. J. ACM 32, 3 (July), 652--686.]] Google Scholar
- Sleator, D. D. and Tarjan, R. E. 1986. Self-adjusting heaps. SIAM J. Comput. 15, 1 (Feb.), 52--69.]] Google Scholar
- Stoica, I., Zhang, H., and Ng, T. S. E. 2000. A hierarchical fair service curve algorithm for link-sharing, real-time, and priority services. IEEE/ACM Trans. Networking 8, 2 (Apr.), 185--199.]] Google Scholar
- Tarjan, R. E. 1985. Amortized computational complexity. SIAM J. Algebraic Discrete Meth. 6, 2 (Apr.), 306--318.]]Google Scholar
- Thng, I. L. J. and Goh, R. S. M. 2004. Swan---Simulator without a name. http://swan.nus.edu.sg/.]]Google Scholar
- Yugo, K. I. R., Moffat, A., and Ngai, C. H. A. 2002. Enhanced word-based block-sorting text compression. In Proceedings of the 25th Australasian Conference on Computer Science, 129--137.]] Google Scholar
Index Terms
- Twol-amalgamated priority queues
Recommendations
Optimizing static calendar queues
The calendar queue is an important implementation of a priority queue that is particularly useful in discrete event simulators. We investigate the performance of the static calendar queue that maintains N active events. The main contribution of this ...
Revisiting priority queues for image analysis
Many algorithms in image analysis require a priority queue, a data structure that holds pointers to pixels in the image, and which allows efficiently finding the pixel in the queue with the highest priority. However, very few articles describing such ...
Waiting time and queue length analysis of Markov-modulated fluid priority queues
AbstractThis paper considers a multi-type fluid queue with priority service. The input fluid rates are modulated by a Markov chain, which is common for all fluid types. The service rate of the queue is constant. Various performance measures are derived, ...
Comments