Call graph prefetching for database applications

ABSTRACT

With the continuing technological trend of ever cheaper and larger memory, most data sets in database servers will soon be able to reside in main memory. In this configuration, the performance bottleneck is likely to be the gap between the processing speed of the CPU and the memory access latency. Previous work has shown that database applications have large instruction and data footprints and hence do not use processor caches effectively. In this paper, we propose Call Graph Prefetching (CGP), an N instruction prefetching technique that analyzes the call graph of a database system and prefetches instructions from the function that is deemed likely to be called next. CGP capitalizes on the highly predictable function call sequences that are typical of database systems. CGP can be implemented either in software or in hardware. The software-based CGP (CGP_S) uses profile information to build a call graph, and uses the predictable call sequences in the call graph to determine which function to prefetch next. The hardware-based CGP(CGP_H) uses a hardware table, called the Call Graph History Cache (CGHC), to dynamically store sequences of functions invoked during program execution, and uses that stored history when choosing which functions to prefetch.We evaluate the performance of CGP on sets of Wisconsin and TPC-H queries, as well as on CPU-2000 benchmarks. For most CPU-2000 applications the number of instruction cache (I-cache) misses were very few even without any prefetching, obviating the need for CGP. On the other hand, the database workloads do suffer a significant number of I-cache misses; CGP_S improves their performance by 23% and CGP_H by 26% over a baseline system that has already been highly tuned for efficient I-cache usage by using the OM tool. CGP, with or without OM, reduces the I-cache miss stall time by about 50% relative to O5+OM, taking us about half way from an already highly tuned baseline system toward perfect I-cache performance.

REFERENCES

• 1: Anastassia Ailamaki , David J. DeWitt , Mark D. Hill , David A. Wood, DBMSs on a Modern Processor: Where Does Time Go?, Proceedings of the 25th International Conference on Very Large Data Bases, p.266-277, September 07-10, 1999
• 2: Murali Mohan Kumar Annavaram , Edward S. Davidson, Prefetch mechanisms that acquire and exploit application specific knowledge, 2001
• 3: Murali Annavaram , Jignesh M. Patel , Edward S. Davidson, Call Graph Prefetching for Database Applications, Proceedings of the 7th International Symposium on High-Performance Computer Architecture, p.281, January 20-24, 2001
• 4: Murali Annavaram , Jignesh M. Patel , Edward S. Davidson, Data prefetching by dependence graph precomputation, Proceedings of the 28th annual international symposium on Computer architecture, p.52-61, June 30-July 04, 2001, Göteborg, Sweden
• 5: Phil Bernstein , Michael Brodie , Stefano Ceri , David DeWitt , Mike Franklin , Hector Garcia-Molina , Jim Gray , Jerry Held , Joe Hellerstein , H. V. Jagadish , Michael Lesk , Dave Maier , Jeff Naughton , Hamid Pirahesh , Mike Stonebraker , Jeff Ullman, The Asilomar report on database research, ACM SIGMOD Record, v.27 n.4, p.74-80, Dec. 1998 [doi>10.1145/306101.306137]
• 6: Dina Bitton , David J. DeWitt , Carolyn Turbyfill, Benchmarking Database Systems A Systematic Approach, Proceedings of the 9th International Conference on Very Large Data Bases, p.8-19, October 31-November 02, 1983
• 7: Peter A. Boncz , Tim Rühl , Fred Kwakkel, The Drill Down Benchmark, Proceedings of the 24rd International Conference on Very Large Data Bases, p.628-632, August 24-27, 1998
• 8: Burger, D. and Austin, T. 1997. The SimpleScalar Tool Set. Tech. Rep. 1342, University of Wisconsin-Madison, Computer ScienceDepartment. June.
• 9: Michael J. Carey , David J. DeWitt , Michael J. Franklin , Nancy E. Hall , Mark L. McAuliffe , Jeffrey F. Naughton , Daniel T. Schuh , Marvin H. Solomon , C. K. Tan , Odysseas G. Tsatalos , Seth J. White , Michael J. Zwilling, Shoring up persistent applications, Proceedings of the 1994 ACM SIGMOD international conference on Management of data, p.383-394, May 24-27, 1994, Minneapolis, Minnesota, United States
• 10: Instruction prefetching using branch prediction information, Proceedings of the 1997 International Conference on Computer Design (ICCD '97), p.593, October 12-15, 1997
• 11: Z. Cvetanovic , D. Bhandarkar, Characterization of alpha AXP performance using TP and SPEC workloads, Proceedings of the 21ST annual international symposium on Computer architecture, p.60-70, April 18-21, 1994, Chicago, Illinois, United States
• 12: Richard J. Eickemeyer , Ross E. Johnson , Steven R. Kunkel , Mark S. Squillante , Shiafun Liu, Evaluation of multithreaded uniprocessors for commercial application environments, Proceedings of the 23rd annual international symposium on Computer architecture, p.203-212, May 22-24, 1996, Philadelphia, Pennsylvania, United States
• 13: M. T. Franklin , W. P. Alexander , R. Jauhari , A. M. G. Maynard , B. R. Olszewski, Commercial workload performance in the IBM POWER2 RISC System/6000 processor, IBM Journal of Research and Development, v.38 n.5, p.555-561, Sept. 1994
• 14: Nikolas Gloy , Trevor Blackwell , Michael D. Smith , Brad Calder, Procedure placement using temporal ordering information, Proceedings of the 30th annual ACM/IEEE international symposium on Microarchitecture, p.303-313, December 01-03, 1997, Research Triangle Park, North Carolina, United States
• 15: Amir H. Hashemi , David R. Kaeli , Brad Calder, Efficient procedure mapping using cache line coloring, Proceedings of the ACM SIGPLAN 1997 conference on Programming language design and implementation, p.171-182, June 16-18, 1997, Las Vegas, Nevada, United States
• 16: Wei-Chung Hsu , James E. Smith, A Performance Study of Instruction Cache Prefetching Methods, IEEE Transactions on Computers, v.47 n.5, p.497-508, May 1998 [doi>10.1109/12.677221]
• 17: Intel Web Site: http://www.developer.intel.com/drg/mmx/appnotes/perfmon.htm Survey of Pentium Processor Performance Monitoring Capabilities & Tools.
• 18: Doug Joseph , Dirk Grunwald, Prefetching using Markov predictors, Proceedings of the 24th annual international symposium on Computer architecture, p.252-263, June 01-04, 1997, Denver, Colorado, United States
• 19: Norman P. Jouppi, Improving direct-mapped cache performance by the addition of a small fully-associative cache and prefetch buffers, Proceedings of the 17th annual international symposium on Computer Architecture, p.364-373, May 28-31, 1990, Seattle, Washington, United States
• 20: J. Kalamatianos , D. Kaeli, Temporal-Based Procedure Reordering for Improved Instruction Cache Performance, Proceedings of the 4th International Symposium on High-Performance Computer Architecture, p.244, January 31-February 04, 1998
• 21: Jack L. Lo , Luiz André Barroso , Susan J. Eggers , Kourosh Gharachorloo , Henry M. Levy , Sujay S. Parekh, An analysis of database workload performance on simultaneous multithreaded processors, Proceedings of the 25th annual international symposium on Computer architecture, p.39-50, June 27-July 02, 1998, Barcelona, Spain
• 22: Architectural and compiler support for effective instruction prefetching: a cooperative approach, ACM Transactions on Computer Systems (TOCS), v.19 n.1, p.71-109, Feb. 2001 [doi>10.1145/367742.367786]
• 23: Ann Marie Grizzaffi Maynard , Colette M. Donnelly , Bret R. Olszewski, Contrasting characteristics and cache performance of technical and multi-user commercial workloads, Proceedings of the sixth international conference on Architectural support for programming languages and operating systems, p.145-156, October 05-07, 1994, San Jose, California, United States
• 24: Chris Nyberg , Tom Barclay , Zarka Cvetanovic , Jim Gray , Dave Lomet, AlphaSort: a RISC machine sort, Proceedings of the 1994 ACM SIGMOD international conference on Management of data, p.233-242, May 24-27, 1994, Minneapolis, Minnesota, United States
• 25: Karl Pettis , Robert C. Hansen, Profile guided code positioning, Proceedings of the ACM SIGPLAN 1990 conference on Programming language design and implementation, p.16-27, June 1990, White Plains, New York, United States
• 26: Jim Pierce , Trevor Mudge, Wrong-path instruction prefetching, Proceedings of the 29th annual ACM/IEEE international symposium on Microarchitecture, p.165-175, December 02-04, 1996, Paris, France
• 27: Glenn Reinman , Brad Calder , Todd Austin, Fetch directed instruction prefetching, Proceedings of the 32nd annual ACM/IEEE international symposium on Microarchitecture, p.16-27, November 16-18, 1999, Haifa, Israel
• 28: Romer, T., Voelker, G., Lee, D., Wolman, A., Wong, W., Levy, H., Bershad, B., and Chen, B. 1997. Instrumentation and Optimization of Win32/Intel Executables Using Etch. In USENIX Windows NT Workshop. 1--7.
• 29: Rupley, J., Annavaram, M., Devale, J., Diep, T., and Black, B. 2002. Comparing and Contrasting a Commercial OLTP Workload with CPU2000 on IPF. In the 5th Workshop on Workload Characterization.
• 30: Ambuj Shatdal , Chander Kant , Jeffrey F. Naughton, Cache Conscious Algorithms for Relational Query Processing, Proceedings of the 20th International Conference on Very Large Data Bases, p.510-521, September 12-15, 1994
• 31: Smith, A. 1978. Sequential Program Prefetching in Memory Hierarchies. IEEE Comput. 11, 2 (December), 7--21.
• 32: Viji Srinivasan , Edward S. Davidson , Gary S. Tyson, A Prefetch Taxonomy, IEEE Transactions on Computers, v.53 n.2, p.126-140, February 2004 [doi>10.1109/TC.2004.1261824]
• 33: Viji Srinivasan , Edward S. Davidson , Gary S. Tyson , Mark J. Charney , Thomas R. Puzak, Branch History Guided Instruction Prefetching, Proceedings of the 7th International Symposium on High-Performance Computer Architecture, p.291, January 20-24, 2001
• 34: Srivastava, A. and Eustace, A. 1994. ATOM: A System for Building Customized Program Analysis Tools. Tech. Rep. 94/2, Digital Western Research Laboratory. March.
• 35: Srivastava, A. and Wall, D. 1992. A Practical System for Intermodule Code Optimization at Link-Time. Tech. Rep. 92/6, Digital Western Research Laboratory. June.
• 36: Pedro Trancoso , Josep-L. Larriba-Pey , Zheng Zhang , Josep Torrellas, The Memory Performance of DSS Commercial Workloads in Shared-Memory Multiprocessors, Proceedings of the 3rd IEEE Symposium on High-Performance Computer Architecture, p.250, February 01-05, 1997
• 37: TPC. 1999. TPC Benchmark H Standard Specification (Decision Support). In Revision 1.1.0.

INDEX TERMS

Primary Classification:
  C. Computer Systems Organization
  C.4 PERFORMANCE OF SYSTEMS
      Subjects: Design studies

Additional Classification:
  C. Computer Systems Organization
  C.1 PROCESSOR ARCHITECTURES
      C.1.0 General

General Terms:
Design, Experimentation, Performance

Keywords:
Instruction cache prefetching, call graph, database