Locality approximation using time

ABSTRACT

Reuse distance (i.e. LRU stack distance) precisely characterizes program locality and has been a basic tool for memory system research since the 1970s. However, the high cost of measuring has restricted its practical uses in performance debugging, locality analysis and optimizations of long-running applications.In this work, we improve the efficiency by exploring the connection between time and locality. We propose a statistical model that converts cheaply obtained time distance to the more costly reuse distance. Compared to the state-of-the-art technique, this approach reduces measuring time by a factor of 17, and approximates cache line reuses with over 99% accuracy and the cache miss rate with less than 0.4% average error for 12 SPEC 2000 integer and floating-point benchmarks. By exploiting the strong correlations between time and locality, this work makes precise locality as easy to obtain as data access frequency, and opens new opportunities for program optimizations.

REFERENCES

• 1: George Almási , Cǎlin Caşcaval , David A. Padua, Calculating stack distances efficiently, Proceedings of the 2002 workshop on Memory system performance, p.37-43, June 16-16, 2002, Berlin, Germany
• 2: Matthew Arnold , Barbara G. Ryder, A framework for reducing the cost of instrumented code, Proceedings of the ACM SIGPLAN 2001 conference on Programming language design and implementation, p.168-179, June 2001, Snowbird, Utah, United States
• 3: B. T. Bennett and V. J. Kruskal. LRU stack processing. IBM Journal of Research and Development, pages 353--357, 1975.
• 4: K. Beyls and E. D'Hollander. Reuse distance as a metric for cache behavior. In Proceedings of the IASTED Conference on Parallel and Distributed Computing and Systems, August 2001.
• 5: Kristof Beyls , Erik H. D'Hollander, Generating cache hints for improved program efficiency, Journal of Systems Architecture: the EUROMICRO Journal, v.51 n.4, p.223-250, April 2005 [doi>10.1016/j.sysarc.2004.09.004]
• 6: K. Beyls and E. D'Hollander. Discovery of locality-improving refactoring by reuse path analysis. In Proceedings of HPCC. Springer. Lecture Notes in Computer Science Vol. 4208, pages 220--229, 2006.
• 7: Calin Cascaval , Evelyn Duesterwald , Peter F. Sweeney , Robert W. Wisniewski, Multiple Page Size Modeling and Optimization, Proceedings of the 14th International Conference on Parallel Architectures and Compilation Techniques, p.339-349, September 17-21, 2005 [doi>10.1109/PACT.2005.32]
• 8: Dhruba Chandra , Fei Guo , Seongbeom Kim , Yan Solihin, Predicting Inter-Thread Cache Contention on a Chip Multi-Processor Architecture, Proceedings of the 11th International Symposium on High-Performance Computer Architecture, p.340-351, February 12-16, 2005 [doi>10.1109/HPCA.2005.27]
• 9: Trishul M. Chilimbi , Martin Hirzel, Dynamic hot data stream prefetching for general-purpose programs, Proceedings of the ACM SIGPLAN 2002 Conference on Programming language design and implementation, June 17-19, 2002, Berlin, Germany
• 10: Chen Ding , Maksim Orlovich, The Potential of Computation Regrouping for Improving Locality, Proceedings of the 2004 ACM/IEEE conference on Supercomputing, p.13, November 06-12, 2004 [doi>10.1109/SC.2004.58]
• 11: Chen Ding , Yutao Zhong, Predicting whole-program locality through reuse distance analysis, Proceedings of the ACM SIGPLAN 2003 conference on Programming language design and implementation, June 09-11, 2003, San Diego, California, USA
• 12: Changpeng Fang , Steve Carr , Soner Onder , Zhenlin Wang, Instruction Based Memory Distance Analysis and its Application, Proceedings of the 14th International Conference on Parallel Architectures and Compilation Techniques, p.27-37, September 17-21, 2005 [doi>10.1109/PACT.2005.26]
• 13: Andrew S. Huang , John Paul Shen, The intrinsic bandwidth requirements of ordinary programs, Proceedings of the seventh international conference on Architectural support for programming languages and operating systems, p.105-114, October 01-04, 1996, Cambridge, Massachusetts, United States
• 14: Yul H. Kim , Mark D. Hill , David A. Wood, Implementing stack simulation for highly-associative memories, Proceedings of the 1991 ACM SIGMETRICS conference on Measurement and modeling of computer systems, p.212-213, May 21-24, 1991, San Diego, California, United States
• 15: Z. Li, J. Gu, and G. Lee. An evaluation of the potential benefits of register allocation for array references. In Workshop on Interaction between Compilers and Computer Architectures in conjunction with the HPCA-2, San Jose, California, February 1996.
• 16: Chi-Keung Luk , Robert Cohn , Robert Muth , Harish Patil , Artur Klauser , Geoff Lowney , Steven Wallace , Vijay Janapa Reddi , Kim Hazelwood, Pin: building customized program analysis tools with dynamic instrumentation, Proceedings of the 2005 ACM SIGPLAN conference on Programming language design and implementation, June 12-15, 2005, Chicago, IL, USA
• 17: Gabriel Marin , John Mellor-Crummey, Cross-architecture performance predictions for scientific applications using parameterized models, Proceedings of the joint international conference on Measurement and modeling of computer systems, June 10-14, 2004, New York, NY, USA
• 18: R. L. Mattson, J. Gecsei, D. Slutz, and I. L. Traiger. Evaluation techniques for storage hierarchies. IBM System Journal, 9(2):78--117, 1970.
• 19: F. Olken. Efficient methods for calculating the success function of fixed space replacement policies. Technical Report LBL-12370, Lawrence Berkeley Laboratory, 1981.
• 20: X. Shen, J. Shaw, and B. Meeker. Accurate approximation of locality from time distance histograms. Technical Report TR902, Computer Science Department, University of Rochester, 2006.
• 21: X. Shen, J. Shaw, B. Meeker, and C. Ding. Locality approximation using time. Technical Report TR901, Computer Science Department, University of Rochester, 2006.
• 22: Xipeng Shen , Yutao Zhong , Chen Ding, Locality phase prediction, Proceedings of the 11th international conference on Architectural support for programming languages and operating systems, October 07-13, 2004, Boston, MA, USA
• 23: Alan Jay Smith, On the effectiveness of set associative page mapping and its application to main memory management, Proceedings of the 2nd international conference on Software engineering, p.286-292, October 13-15, 1976, San Francisco, California, United States
• 24: R. A. Sugumar and S. G. Abraham. Multi-configuration simulation algorithms for the evaluation of computer architecture designs. Technical report, University of Michigan, 1993.
• 25: Y. Zhong, S. G. Dropsho, X. Shen, A. Studer, and C. Ding. Miss rate prediction across program inputs and cache configurations. IEEE Transactions on Computers, to appear.
• 26: Yutao Zhong , Maksim Orlovich , Xipeng Shen , Chen Ding, Array regrouping and structure splitting using whole-program reference affinity, Proceedings of the ACM SIGPLAN 2004 conference on Programming language design and implementation, June 09-11, 2004, Washington DC, USA

INDEX TERMS

Primary Classification:
  D. Software
  D.3 PROGRAMMING LANGUAGES
      D.3.4 Processors
          Subjects: Optimization

Additional Classification:
  D. Software
  D.3 PROGRAMMING LANGUAGES
      D.3.4 Processors
          Subjects: Compilers

General Terms:
Algorithms, Measurement, Performance

Keywords:
performance prediction, program locality, reference affinity, reuse distance, time distance, trace generator