A component model of spatial locality

ABSTRACT

Good spatial locality alleviates both the latency and bandwidth problem of memory by boosting the effect of prefetching and improving the utilization of cache. However, conventional definitions of spatial locality are inadequate for a programmer to precisely quantify the quality of a program, to identify causes of poor locality, and to estimate the potential by which spatial locality can be improved.

This paper describes a new, component-based model for spatial locality. It is based on measuring the change of reuse distances as a function of the data-block size. It divides spatial locality into components at program and behavior levels. While the base model is costly because it requires the tracking of the locality of every memory access, the overhead can be reduced by using small inputs and by extending a sampling-based tool. The paper presents the result of the analysis for a large set of benchmarks, the cost of the analysis, and the experience of a user study, in which the analysis helped to locate a data-layout problem and improve performance by 7% with a 6-line change in an application with over 2,000 lines.

REFERENCES

• 1: Glenn Ammons , Thomas Ball , James R. Larus, Exploiting hardware performance counters with flow and context sensitive profiling, Proceedings of the ACM SIGPLAN 1997 conference on Programming language design and implementation, p.85-96, June 16-18, 1997, Las Vegas, Nevada, United States
• 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: Erik Berg , Erik Hagersten, Fast data-locality profiling of native execution, Proceedings of the 2005 ACM SIGMETRICS international conference on Measurement and modeling of computer systems, June 06-10, 2005, Banff, Alberta, Canada
• 4: 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.
• 5: Richard B. Bunt , Jennifer M. Murphy, The measurement of locality and the behaviour of programs, The Computer Journal, v.27 n.3, p.238-253, Aug. 1984 [doi>10.1093/comjnl/27.3.238]
• 6: Brad Calder , Chandra Krintz , Simmi John , Todd Austin, Cache-conscious data placement, Proceedings of the eighth international conference on Architectural support for programming languages and operating systems, p.139-149, October 02-07, 1998, San Jose, California, United States
• 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: Trishul M. Chilimbi, Efficient representations and abstractions for quantifying and exploiting data reference locality, Proceedings of the ACM SIGPLAN 2001 conference on Programming language design and implementation, p.191-202, June 2001, Snowbird, Utah, United States
• 9: 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
• 10: 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]
• 11: Hwansoo Han , Chau-Wen Tseng, Exploiting Locality for Irregular Scientific Codes, IEEE Transactions on Parallel and Distributed Systems, v.17 n.7, p.606-618, July 2006 [doi>10.1109/TPDS.2006.88]
• 12: M. Hirzel and T. M. Chilimbi. Bursty tracing: A framework for low-overhead temporal profiling. In Proceedings of ACM Workshop on Feedback-Directed and Dynamic Optimization, Dallas, Texas, 2001.
• 13: Kirk Kelsey , Tongxin Bai , Chen Ding , Chengliang Zhang, Fast Track: A Software System for Speculative Program Optimization, Proceedings of the 2009 International Symposium on Code Generation and Optimization, p.157-168, March 22-25, 2009 [doi>10.1109/CGO.2009.18]
• 14: Kim-Hung Li, Reservoir-sampling algorithms of time complexity O(n(1 + log(N/n))), ACM Transactions on Mathematical Software (TOMS), v.20 n.4, p.481-493, Dec. 1994 [doi>10.1145/198429.198435]
• 15: 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
• 16: G. Marin and J. Mellor-Crummey. Scalable cross-architecture predictions of memory hierarchy response for scientific applications. In Proceedings of the Symposium of the Las Alamos Computer Science Institute, Sante Fe, New Mexico, 2005.
• 17: R. L. Mattson, J. Gecsei, D. Slutz, and I. L. Traiger. Evaluation techniques for storage hierarchies. IBM System Journal, 9(2):78--117, 1970.
• 18: Kathryn S. McKinley , Steve Carr , Chau-Wen Tseng, Improving data locality with loop transformations, ACM Transactions on Programming Languages and Systems (TOPLAS), v.18 n.4, p.424-453, July 1996 [doi>10.1145/233561.233564]
• 19: Richard C. Murphy , Peter M. Kogge, On the Memory Access Patterns of Supercomputer Applications: Benchmark Selection and Its Implications, IEEE Transactions on Computers, v.56 n.7, p.937-945, July 2007 [doi>10.1109/TC.2007.1039]
• 20: Nicholas Nethercote , Julian Seward, Valgrind: a framework for heavyweight dynamic binary instrumentation, Proceedings of the 2007 ACM SIGPLAN conference on Programming language design and implementation, June 10-13, 2007, San Diego, California, USA
• 21: Erez Petrank , Dror Rawitz, The hardness of cache conscious data placement, Proceedings of the 29th ACM SIGPLAN-SIGACT symposium on Principles of programming languages, p.101-112, January 16-18, 2002, Portland, Oregon
• 22: Matthew L. Seidl , Benjamin G. Zorn, Segregating heap objects by reference behavior and lifetime, Proceedings of the eighth international conference on Architectural support for programming languages and operating systems, p.12-23, October 02-07, 1998, San Jose, California, United States
• 23: Xipen Shen , Yaoqing Gao , Chen Ding , Roch Archambault, Lightweight reference affinity analysis, Proceedings of the 19th annual international conference on Supercomputing, June 20-22, 2005, Cambridge, Massachusetts [doi>10.1145/1088149.1088167]
• 24: Xipeng Shen , Jonathan Shaw, Scalable Implementation of Efficient Locality Approximation, Languages and Compilers for Parallel Computing: 21th International Workshop, LCPC 2008, Edmonton, Canada, July 31 - August 2, 2008, Revised Selected Papers, Springer-Verlag, Berlin, Heidelberg, 2008 [doi>10.1007/978-3-540-89740-8_14]
• 25: Xipeng Shen , Jonathan Shaw , Brian Meeker , Chen Ding, Locality approximation using time, Proceedings of the 34th annual ACM SIGPLAN-SIGACT symposium on Principles of programming languages, January 17-19, 2007, Nice, France
• 26: X. Shen, Y. Zhong, and C. Ding. Regression-based multi-model prediction of data reuse signature. In Proceedings of the 4th Annual Symposium of the Las Alamos Computer Science Institute, Sante Fe, New Mexico, November 2003.
• 27: 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
• 28: Spec cpu benchmarks. http://www.spec.org/benchmarks.html\#cpu.
• 29: Michelle Mills Strout , Larry Carter , Jeanne Ferrante, Compile-time composition of run-time data and iteration reorderings, Proceedings of the ACM SIGPLAN 2003 conference on Programming language design and implementation, June 09-11, 2003, San Diego, California, USA
• 30: Jonathan Weinberg , Michael O. McCracken , Erich Strohmaier , Allan Snavely, Quantifying Locality In The Memory Access Patterns of HPC Applications, Proceedings of the 2005 ACM/IEEE conference on Supercomputing, p.50, November 12-18, 2005 [doi>10.1109/SC.2005.59]
• 31: Brian S. White , Sally A. McKee , Bronis R. de Supinski , Brian Miller , Daniel Quinlan , Martin Schulz, Improving the computational intensity of unstructured mesh applications, Proceedings of the 19th annual international conference on Supercomputing, June 20-22, 2005, Cambridge, Massachusetts [doi>10.1145/1088149.1088195]
• 32: Chengliang Zhang , Chen Ding , Mitsunori Ogihara , Yutao Zhong , Youfeng Wu, A hierarchical model of data locality, Conference record of the 33rd ACM SIGPLAN-SIGACT symposium on Principles of programming languages, p.16-29, January 11-13, 2006, Charleston, South Carolina, USA
• 33: Hao Zhang , Daniel Gildea, Stochastic lexicalized inversion transduction grammar for alignment, Proceedings of the 43rd Annual Meeting on Association for Computational Linguistics, p.475-482, June 25-30, 2005, Ann Arbor, Michigan [doi>10.3115/1219840.1219899]
• 34: Yutao Zhong , Steven G. Dropsho , Xipeng Shen , Ahren Studer , Chen Ding, Miss Rate Prediction Across Program Inputs and Cache Configurations, IEEE Transactions on Computers, v.56 n.3, p.328-343, March 2007 [doi>10.1109/TC.2007.50]
• 35: 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:
  C. Computer Systems Organization
  C.4 PERFORMANCE OF SYSTEMS
      Subjects: Measurement techniques

General Terms:
Measurement, Performance

Keywords:
reuse distance, spatial locality