Fast priority queues for cached memory

ABSTRACT

The cache hierarchy prevalent in todays high performance processors has to be taken into account in order to design algorithms that perform well in practice. This paper advocates the adaption of external memory algorithms to this purpose. This idea and the practical issues involved are exemplified by engineering a fast priority queue suited to external memory and cached memory that is based on <i>k</i>-way merging. It improves previous external memory algorithms by constant factors crucial for transferring it to cached memory. Running in the cache hierarchy of a workstation the algorithm is at least two times faster than an optimized implementation of binary heaps and 4-ary heaps for large inputs.

REFERENCES

• 1: Lars Arge, The Buffer Tree: A New Technique for Optimal I/O-Algorithms (Extended Abstract), Proceedings of the 4th International Workshop on Algorithms and Data Structures, p.334-345, August 16-18, 1995
• 2: Rakesh D. Barve , Edward F. Grove , Jeffrey Scott Vitter, Simple randomized mergesort on parallel disks, Parallel Computing, v.23 n.4-5, p.601-631, June 1, 1997 [doi>10.1016/S0167-8191(97)00015-X]
• 3: Klaus Brengel , Andreas Crauser , Paolo Ferragina , Ulrich Meyer, An Experimental Study of Priority Queues in External Memory, Proceedings of the 3rd International Workshop on Algorithm Engineering, p.345-359, July 19-21, 1999
• 4: Gerth Stølting Brodal , Jyrki Katajainen, Worst-Case External-Memory Priority Queues, Proceedings of the 6th Scandinavian Workshop on Algorithm Theory, p.107-118, July 08-10, 1998
• 5: 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]
• 6: Thomas T. Cormen , Charles E. Leiserson , Ronald L. Rivest, Introduction to algorithms, MIT Press, Cambridge, MA, 1990
• 7: FADEL, R., JAKOBSEN, K. V., KATAJAINEN, J., AND TEUHOLA, J. 1997. External heaps combined with effective buffering. In <i>4th Australasian Theory Symposium</i>, Volume 19-2 of <i>Australian Computer Science Communications</i> (1997), pp. 72-78. Springer.
• 8: Michael J. Fischer , Michael S. Paterson, Fishspear: a priority queue algorithm, Journal of the ACM (JACM), v.41 n.1, p.3-30, Jan. 1994 [doi>10.1145/174644.174645]
• 9: John L. Hennessy , David A. Patterson, Computer architecture (2nd ed.): a quantitative approach, Morgan Kaufmann Publishers Inc., San Francisco, CA, 1996
• 10: Intel Corporation. 1997. <i>Intel Architecture Software Developer's Manual. Volume I: Basic Architecture</i>. P.O. Box 5937, Denver, CO, 80217-9808, http://www.intel.com: Intel Corporation. Ordering Number 243190.
• 11: 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]
• 12: KELLER, J. 1996. The 21264: A superscalar alpha processor with out-of-order execution. In <i>Microprocessor Forum</i> (October 1996).
• 13: KNUTH, D. E. 1973. <i>The Art of Computer Programming--Sorting and Searching</i>, Volume 3. Addison Wesley.
• 14: Anthony LaMarca , Richard Ladner, The influence of caches on the performance of heaps, Journal of Experimental Algorithmics (JEA), 1, p.4-es, 1996 [doi>10.1145/235141.235145]
• 15: Anthony LaMarca , Richard E. Ladner, The influence of caches on the performance of sorting, Proceedings of the eighth annual ACM-SIAM symposium on Discrete algorithms, p.370-379, January 05-07, 1997, New Orleans, Louisiana, United States
• 16: MIPS Technologies, Inc. 1998. <i>R10000 Microprocessor User's Manual</i> (2.0 ed.). MIPS Technologies, Inc. http://www.mips.com.
• 17: John von Newmann, First draft of a report on the EDVAC, 1945
• 18: Peter Sanders, Accessing Multiple Sequences Through Set Associative Caches, Proceedings of the 26th International Colloquium on Automata, Languages and Programming, p.655-664, July 11-15, 1999
• 19: Sun Microsystems. 1997. <i>UltraSPARC-IIi User's Manual</i>. Sun Microsystems.
• 20: VENGROFF, D. E. 1995. <i>TPIE User Manual and Reference</i>. Duke University. http://www. cs.duke.edu/~dev/tpie_home_page.html.
• 21: Jeffrey Scott Vitter, External Memory Algorithms, Proceedings of the 6th Annual European Symposium on Algorithms, p.1-25, August 24-26, 1998
• 22: VITTER, J. S. AND SHRIVER, E. A. M. 1994. Algorithms for parallel memory I: Two level memories. <i>Algorithmica 12</i>, 2-3, 110-147.
• 23: Ingo Wegener, BOTTOM-UP-HEAPSORT, a new variant of HEAPSORT beating, on an average, QUICKSORT (if n is not very small), Theoretical Computer Science, v.118 n.1, p.81-98, Sept. 13, 1993
• 24: L. M. Wegner , J. I. Teuhola, The External Heapsort, IEEE Transactions on Software Engineering, v.15 n.7, p.917-925, July 1989 [doi>10.1109/32.29490]

INDEX TERMS

Primary Classification:
  G. Mathematics of Computing
  G.3 PROBABILITY AND STATISTICS
      Subjects: Queueing theory

Additional Classification:
  D. Software
  D.4 OPERATING SYSTEMS
      D.4.2 Storage Management
          Subjects: Distributed memories
      D.4.8 Performance
          Subjects: Queueing theory

General Terms:
Algorithms, Design, Performance

Keywords:
cache, cache efficiency, data structure, external memory, heap, implementation, multi way merging, priority queue, secondary storage