The influence of caches on the performance of heaps

ABSTRACT

As memory access times grow larger relative to processor cycle times, the cache performance of algorithms has an increasingly large impact on overall performance. Unfortunately, most commonly used algorithms were not designed with cache performance in mind. This paper investigates the cache performance of implicit heaps. We present optimizations which significantly reduce the cache misses that heaps incur and improve their overall performance. We present an analytical model called collective analysis that allows cache performance to be predicted as a function of both cache configuration and algorithm configuration. As part of our investigation, we perform an approximate analysis of the cache performance of both traditional heaps and our improved heaps in our model. In addition empirical data is given for five architectures to show the impact our optimizations have on overall performance. We also revisit a priority queue study originally performed by Jones [25]. Due to the increases in cache miss penalties, the relative performance results we obtain on today's machines differ greatly from the machines of only ten years ago. We compare the performance of implicit heaps, skew heaps and splay trees and discuss the difference between our results and Jones's.

REFERENCES

• 1: A. Agarwal , J. Hennessy , M. Horowitz, An analytical cache model, ACM Transactions on Computer Systems (TOCS), v.7 n.2, p.184-215, May 1989 [doi>10.1145/63404.63407]
• 2: R. C. Agarwal , F. G. Gustavson , M. Zubair, Exploiting functional parallelism of POWER2 to design high-performance numerical algorithms, IBM Journal of Research and Development, v.38 n.5, p.563-576, Sept. 1994
• 3: A. Aggarwal , B. Alpern , A. Chandra , M. Snir, A model for hierarchical memory, Proceedings of the nineteenth annual ACM conference on Theory of computing, p.305-314, January 1987, New York, New York, United States [doi>10.1145/28395.28428]
• 4: Alfred V. Aho , John E. Hopcroft, The Design and Analysis of Computer Algorithms, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1974
• 5: {5} B. Alpern, L. Carter, E. Feig, and T. Selker. The uniform memory hierarchy model of computation. <i>Algorithmica</i>, 12:2-3:72-109, 1994.
• 6: Jennifer M. Anderson , Monica S. Lam, Global optimizations for parallelism and locality on scalable parallel machines, Proceedings of the ACM SIGPLAN 1993 conference on Programming language design and implementation, p.112-125, June 21-25, 1993, Albuquerque, New Mexico, United States
• 7: Svante Carlsson, An optimal algorithm for deleting the roof of a heap, Information Processing Letters, v.37 n.2, p.117-120, Jan. 31, 1991 [doi>10.1016/0020-0190(91)90144-7]
• 8: Steve Carr , Kathryn S. McKinley , Chau-Wen Tseng, Compiler optimizations for improving data locality, Proceedings of the sixth international conference on Architectural support for programming languages and operating systems, p.252-262, October 05-07, 1994, San Jose, California, United States
• 9: Michał Cierniak , Wei Li, Unifying data and control transformations for distributed shared-memory machines, Proceedings of the ACM SIGPLAN 1995 conference on Programming language design and implementation, p.205-217, June 18-21, 1995, La Jolla, California, United States
• 10: Douglas W. Clark, Cache Performance in the VAX-11/780, ACM Transactions on Computer Systems (TOCS), v.1 n.1, p.24-37, Feb. 1983 [doi>10.1145/357353.357356]
• 11: Edward G. Coffman, Jr. , Peter J. Denning, Operating Systems Theory, Prentice Hall Professional Technical Reference, 1973
• 12: Thomas T. Cormen , Charles E. Leiserson , Ronald L. Rivest, Introduction to algorithms, MIT Press, Cambridge, MA, 1990
• 13: Jeannette M. de Graaf , Walter A. Kosters, Expected heights in heaps, BIT, v.32 n.4, p.570-579, 1992 [doi>10.1007/BF01994841]
• 14: {14} E. Doberkat. Inserting a new element into a heap. <i>BIT</i>, 21:225-269, 1981.
• 15: {15} E. Doberkat. Deleting the root of a heap. <i>Acta Informatica</i>, 17:245-265, 1982.
• 16: J. J. Dongarra , Orlie Brewer , James Arthur Kohl , Samuel Fineberg, A tool to aid in the design, implementation, and understanding of matrix algorithms for parallel processors, Journal of Parallel and Distributed Computing, v.9 n.2, p.185-202, June 1990 [doi>10.1016/0743-7315(90)90045-Q]
• 17: M. Farrens , G. Tyson , A. R. Pleszkun, A study of single-chip processor/cache organizations for large numbers of transistors, Proceedings of the 21ST annual international symposium on Computer architecture, p.338-347, April 18-21, 1994, Chicago, Illinois, United States
• 18: David M. Fenwick , Denis J. Foley , William B. Gist , Stephen R. VanDoren , Daniel Wissell, The AlphaServer 8000 series: high-end server platform development, Digital Technical Journal, v.7 n.1, p.43-65, Jan. 1995
• 19: {19} Robert W. Floyd. Treesort 3. <i>Communications of the ACM</i>, 7:12:701, 1964.
• 20: Dennis Gannon , William Jalby , Kyle Gallivan, Strategies for cache and local memory management by global program transformation, Journal of Parallel and Distributed Computing, v.5 n.5, p.587-616, October 1988 [doi>10.1016/0743-7315(88)90014-7]
• 21: Gaston H Gonnet , J Ian Munro, Heaps on heaps, SIAM Journal on Computing, v.15 n.4, p.964-971, Nov. 1986 [doi>10.1137/0215068]
• 22: Dirk Grunwald , Benjamin Zorn , Robert Henderson, Improving the cache locality of memory allocation, Proceedings of the ACM SIGPLAN 1993 conference on Programming language design and implementation, p.177-186, June 21-25, 1993, Albuquerque, New Mexico, United States
• 23: David A. Patterson , John L. Hennessy, Computer architecture: a quantitative approach, Morgan Kaufmann Publishers Inc., San Francisco, CA, 1990
• 24: {24} D.B. Johnson. Priority queues with update and finding minimum spanning trees. <i>Information Processing Letters</i>, 4, 1975.
• 25: 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]
• 26: Ken Kennedy , Kathryn S. McKinley, Optimizing for parallelism and data locality, Proceedings of the 6th international conference on Supercomputing, p.323-334, July 19-24, 1992, Washington, D. C., United States [doi>10.1145/143369.143427]
• 27: Donald E. Knuth, The art of computer programming, volume 3: (2nd ed.) sorting and searching, Addison Wesley Longman Publishing Co., Inc., Redwood City, CA, 1998
• 28: Anthony George Lamarca , Richard E. Ladner, Caches and algorithms, 1996
• 29: 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
• 30: Alvin R. Lebeck , David A. Wood, Cache Profiling and the SPEC Benchmarks: A Case Study, Computer, v.27 n.10, p.15-26, October 1994 [doi>10.1109/2.318580]
• 31: Margaret Martonosi , Anoop Gupta , Thomas Anderson, MemSpy: analyzing memory system bottlenecks in programs, Proceedings of the 1992 ACM SIGMETRICS joint international conference on Measurement and modeling of computer systems, p.1-12, June 01-05, 1992, Newport, Rhode Island, United States
• 32: D. Naor , C. U. Martel , N. S. Matloff, Performance of priority queue structures in a virtual memory environment, The Computer Journal, v.34 n.5, p.428-437, Oct. 1991 [doi>10.1093/comjnl/34.5.428]
• 33: Gururaj S. Rao, Performance Analysis of Cache Memories, Journal of the ACM (JACM), v.25 n.3, p.378-395, July 1978 [doi>10.1145/322077.322081]
• 34: Robert Sedgewick, Algorithms, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1984
• 35: Jaswinder Pal Singh , Harold S. Stone , Dominique F. Thiébaut, A Model of Workloads and its Use in Miss-Rate Prediction for Fully Associative Caches, IEEE Transactions on Computers, v.41 n.7, p.811-825, July 1992 [doi>10.1109/12.256450]
• 36: 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]
• 37: Amitabh Srivastava , Alan Eustace, ATOM: a system for building customized program analysis tools, Proceedings of the ACM SIGPLAN 1994 conference on Programming language design and implementation, p.196-205, June 20-24, 1994, Orlando, Florida, United States
• 38: O. Temam , C. Fricker , W. Jalby, Cache interference phenomena, Proceedings of the 1994 ACM SIGMETRICS conference on Measurement and modeling of computer systems, p.261-271, May 16-20, 1994, Nashville, Tennessee, United States
• 39: Richard Uhlig , David Nagle , Tim Stanley , Trevor Mudge , Stuart Sechrest , Richard Brown, Design tradeoffs for software-managed TLBs, ACM Transactions on Computer Systems (TOCS), v.12 n.3, p.175-205, Aug. 1994 [doi>10.1145/185514.185515]
• 40: Mark Allen Weiss, Data structures and algorithm analysis (2nd ed.), Benjamin-Cummings Publishing Co., Inc., Redwood City, CA, 1995
• 41: Wen-Hann Wang , Jean-Loup Baer, Efficient trace-driven simulation methods for cache performance analysis, ACM Transactions on Computer Systems (TOCS), v.9 n.3, p.222-241, Aug. 1991 [doi>10.1145/128738.128740]
• 42: {42} J. W. Williams. Heapsort. <i>Communications of the ACM</i>, 7:6:347-348, 1964.
• 43: Michael E. Wolf , Monica S. Lam, A data locality optimizing algorithm, Proceedings of the ACM SIGPLAN 1991 conference on Programming language design and implementation, p.30-44, June 24-28, 1991, Toronto, Ontario, Canada

INDEX TERMS

Primary Classification:
  E. Data
  E.1 DATA STRUCTURES
      Subjects: Trees

Additional Classification:
  F. Theory of Computation
  F.2 ANALYSIS OF ALGORITHMS AND PROBLEM COMPLEXITY
      F.2.2 Nonnumerical Algorithms and Problems
          Subjects: Sorting and searching

General Terms:
Algorithms, Experimentation, Performance, Theory