Program locality analysis using reuse distance

ABSTRACT

On modern computer systems, the memory performance of an application depends on its locality. For a single execution, locality-correlated measures like average miss rate or working-set size have long been analyzed using reuse distance—the number of distinct locations accessed between consecutive accesses to a given location. This article addresses the analysis problem at the program level, where the size of data and the locality of execution may change significantly depending on the input.

The article presents two techniques that predict how the locality of a program changes with its input. The first is approximate reuse-distance measurement, which is asymptotically faster than exact methods while providing a guaranteed precision. The second is statistical prediction of locality in all executions of a program based on the analysis of a few executions. The prediction process has three steps: dividing data accesses into groups, finding the access patterns in each group, and building parameterized models. The resulting prediction may be used on-line with the help of distance-based sampling. When evaluated on fifteen benchmark applications, the new techniques predicted program locality with good accuracy, even for test executions that are orders of magnitude larger than the training executions.

The two techniques are among the first to enable quantitative analysis of whole-program locality in general sequential code. These findings form the basis for a unified understanding of program locality and its many facets. Concluding sections of the article present a taxonomy of related literature along five dimensions of locality and discuss the role of reuse distance in performance modeling, program optimization, cache and virtual memory management, and network traffic analysis.

REFERENCES

• 1: Vikram Adve , John Mellor-Crummey, Using integer sets for data-parallel program analysis and optimization, Proceedings of the ACM SIGPLAN 1998 conference on Programming language design and implementation, p.186-198, June 17-19, 1998, Montreal, Quebec, Canada
• 2: Ken Kennedy , John R. Allen, Optimizing compilers for modern architectures: a dependence-based approach, Morgan Kaufmann Publishers Inc., San Francisco, CA, 2001
• 3: 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
• 4: Virgílio Almeida , Azer Bestavros , Mark Crovella , Adriana de Oliveira, Characterizing reference locality in the WWW, Proceedings of the fourth international conference on on Parallel and distributed information systems, p.92-107, December 18-20, 1996, Miami Beach, Florida, United States
• 5: Noga Alon , Yossi Matias , Mario Szegedy, The space complexity of approximating the frequency moments, Proceedings of the twenty-eighth annual ACM symposium on Theory of computing, p.20-29, May 22-24, 1996, Philadelphia, Pennsylvania, United States [doi>10.1145/237814.237823]
• 6: 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
• 7: Utpal K. Banerjee, Dependence Analysis for Supercomputing, Kluwer Academic Publishers, Norwell, MA, 1988
• 8: Batson, A. P. and Madison, A. W. 1976. Measurements of major locality phases in symbolic reference strings. In Proceedings of the International Conference on Measurement and Modeling of Computer Systems.
• 9: Bennett, B. T. and Kruskal, V. J. 1975. LRU stack processing. IBM J. Resear. Devel. 353--357.
• 10: E. Berg , E. Hagersten, StatCache: a probabilistic approach to efficient and accurate data locality analysis, Proceedings of the 2004 IEEE International Symposium on Performance Analysis of Systems and Software, p.20-27, March 10-12, 2004
• 11: 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
• 12: Kristof Beyls , Erik H. D'Hollander, Reuse Distance-Based Cache Hint Selection, Proceedings of the 8th International Euro-Par Conference on Parallel Processing, p.265-274, August 27-30, 2002
• 13: 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]
• 14: Beyls, K. and D'Hollander, E. 2006a. Discovery of locality-improving refactoring by reuse path analysis. In Proceedings of the High-Performance Computing and Communications Council. Springer. Lecture Notes in Computer Science, vol. 4208. 220--229.
• 15: Kristof Beyls , Erik H. D'Hollander, Intermediately executed code is the key to find refactorings that improve temporal data locality, Proceedings of the 3rd conference on Computing frontiers, May 03-05, 2006, Ischia, Italy [doi>10.1145/1128022.1128071]
• 16: 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]
• 17: Michael Burke , Ron Cytron, Interprocedural dependence analysis and parallelization, Proceedings of the 1986 SIGPLAN symposium on Compiler construction, p.162-175, June 25-27, 1986, Palo Alto, California, United States
• 18: 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
• 19: David Callahan , Ken Kennedy, Analysis of interprocedural side effects in a parallel programming environment, Journal of Parallel and Distributed Computing, v.5 n.5, p.517-550, October 1988 [doi>10.1016/0743-7315(88)90011-1]
• 20: David Callahan , John Cocke , Ken Kennedy, Estimating interlock and improving balance for pipelined architectures, Journal of Parallel and Distributed Computing, v.5 n.4, p.334-358, August 1988 [doi>10.1016/0743-7315(88)90002-0]
• 21: Steve Carr , Ken Kennedy, Improving the ratio of memory operations to floating-point operations in loops, ACM Transactions on Programming Languages and Systems (TOPLAS), v.16 n.6, p.1768-1810, Nov. 1994 [doi>10.1145/197320.197366]
• 22: Calin CaΒcaval , David A. Padua, Estimating cache misses and locality using stack distances, Proceedings of the 17th annual international conference on Supercomputing, June 23-26, 2003, San Francisco, CA, USA [doi>10.1145/782814.782836]
• 23: 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]
• 24: Siddhartha Chatterjee , Erin Parker , Philip J. Hanlon , Alvin R. Lebeck, Exact analysis of the cache behavior of nested loops, Proceedings of the ACM SIGPLAN 2001 conference on Programming language design and implementation, p.286-297, June 2001, Snowbird, Utah, United States
• 25: Song Jiang , Feng Chen , Xiaodong Zhang, CLOCK-Pro: an effective improvement of the CLOCK replacement, Proceedings of the annual conference on USENIX Annual Technical Conference, p.35-35, April 10-15, 2005, Anaheim, CA
• 26: Cheng, R. and Ding, C. 2005. Measuring temporal locality variation across program inputs. Tech. rep. TR 875, Department of Computer Science, University of Rochester.
• 27: 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
• 28: Trishul M. Chilimbi, On the Stability of Temporal Data Reference Profiles, Proceedings of the 2001 International Conference on Parallel Architectures and Compilation Techniques, p.151, September 08-12, 2001
• 29: Trishul M. Chilimbi , Mark D. Hill , James R. Larus, Cache-conscious structure layout, Proceedings of the ACM SIGPLAN 1999 conference on Programming language design and implementation, p.1-12, May 01-04, 1999, Atlanta, Georgia, United States
• 30: 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
• 31: 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
• 32: Cocke, J. and Kennedy, K. 1974. Profitability computations on program flow graphs. Tech. rep. RC 5123, IBM.
• 33: Raja Das , Mustafa Uysal , Joel Saltz , Yuan-Shin Hwang, Communication optimizations for irregular scientific computations on distributed memory architectures, Journal of Parallel and Distributed Computing, v.22 n.3, p.462-478, Sept. 1994 [doi>10.1006/jpdc.1994.1104]
• 34: Mayur Datar , Aristides Gionis , Piotr Indyk , Rajeev Motwani, Maintaining Stream Statistics over Sliding Windows, SIAM Journal on Computing, v.31 n.6, p.1794-1813, 2002 [doi>10.1137/S0097539701398363]
• 35: P. J. Denning, Working Sets Past and Present, IEEE Transactions on Software Engineering, v.6 n.1, p.64-84, January 1980 [doi>10.1109/TSE.1980.230464]
• 36: Chen Ding , Ken Kennedy, Improving cache performance in dynamic applications through data and computation reorganization at run time, Proceedings of the ACM SIGPLAN 1999 conference on Programming language design and implementation, p.229-241, May 01-04, 1999, Atlanta, Georgia, United States
• 37: Chen Ding , Ken Kennedy, Improving effective bandwidth through compiler enhancement of global cache reuse, Journal of Parallel and Distributed Computing, v.64 n.1, p.108-134, January 2004 [doi>10.1016/j.jpdc.2003.09.005]
• 38: Chen Ding , Yutao Zhong, Compiler-directed run-time monitoring of program data access, Proceedings of the 2002 workshop on Memory system performance, p.1-12, June 16-16, 2002, Berlin, Germany
• 39: Lieven Eeckhout , Hans Vandierendonck , Koenraad De Bosschere, Workload Design: Selecting Representative Program-Input Pairs, Proceedings of the 2002 International Conference on Parallel Architectures and Compilation Techniques, p.83-94, September 22-25, 2002
• 40: 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]
• 41: Jeanne Ferrante , Vivek Sarkar , W. Thrash, On Estimating and Enhancing Cache Effectiveness, Proceedings of the Fourth International Workshop on Languages and Compilers for Parallel Computing, p.328-343, August 07-09, 1991
• 42: Philippe Flajolet , G. Nigel Martin, Probabilistic counting, Proceedings of the 24th Annual Symposium on Foundations of Computer Science, p.76-82, November 07-09, 1983 [doi>10.1109/SFCS.1983.46]
• 43: Somnath Ghosh , Margaret Martonosi , Sharad Malik, Cache miss equations: a compiler framework for analyzing and tuning memory behavior, ACM Transactions on Programming Languages and Systems (TOPLAS), v.21 n.4, p.703-746, July 1999 [doi>10.1145/325478.325479]
• 44: Xiaoming Gu , Ian Christopher , Tongxin Bai , Chengliang Zhang , Chen Ding, A component model of spatial locality, Proceedings of the 2009 international symposium on Memory management, June 19-20, 2009, Dublin, Ireland [doi>10.1145/1542431.1542446]
• 45: 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]
• 46: P. Havlak , K. Kennedy, An Implementation of Interprocedural Bounded Regular Section Analysis, IEEE Transactions on Parallel and Distributed Systems, v.2 n.3, p.350-360, July 1991 [doi>10.1109/71.86110]
• 47: M. D. Hill , A. J. Smith, Evaluating Associativity in CPU Caches, IEEE Transactions on Computers, v.38 n.12, p.1612-1630, December 1989 [doi>10.1109/12.40842]
• 48: Wei Chung Hsu , Howard Chen , Pen Chung Yew , Dong-Yuan Chen, On the Predictability of Program Behavior Using Different Input Data Sets, Proceedings of the Sixth Annual Workshop on Interaction between Compilers and Computer Architectures, p.45, February 03-03, 2002
• 49: Song Jiang , Xiaodong Zhang, LIRS: an efficient low inter-reference recency set replacement policy to improve buffer cache performance, Proceedings of the 2002 ACM SIGMETRICS international conference on Measurement and modeling of computer systems, June 15-19, 2002, Marina Del Rey, California
• 50: Yunlian Jiang , Xipeng Shen , Jie Chen , Rahul Tripathi, Analysis and approximation of optimal co-scheduling on chip multiprocessors, Proceedings of the 17th international conference on Parallel architectures and compilation techniques, October 25-29, 2008, Toronto, Ontario, Canada [doi>10.1145/1454115.1454146]
• 51: Mahmut Taylan Kandemir, Improving whole-program locality using intra-procedural and inter-procedural transformations, Journal of Parallel and Distributed Computing, v.65 n.5, p.564-582, May 2005 [doi>10.1016/j.jpdc.2004.12.004]
• 52: Kelly, T., Cohen, I., Goldszmidt, M., and Keeton, K. 2004. Inducing models of black-box storage arrays. Tech. rep. HPL-2004-108, HP Laboratories Palo Alto, CA.
• 53: Wayne Kelly , Vadim Maslov , William Pugh , Evan Rosser , Tatiana Shpeisman , David Wonnacott, The Omega Library interface guide, University of Maryland at College Park, College Park, MD, 1995
• 54: 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]
• 55: 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
• 56: A J KleinOsowski , David J. Lilja, MinneSPEC: A New SPEC Benchmark Workload for Simulation-Based Computer Architecture Research, IEEE Computer Architecture Letters, v.1 n.1, p.7, January 2002 [doi>10.1109/L-CA.2002.8]
• 57: Kathleen Knobe , Vivek Sarkar, Array SSA form and its use in parallelization, Proceedings of the 25th ACM SIGPLAN-SIGACT symposium on Principles of programming languages, p.107-120, January 19-21, 1998, San Diego, California, United States [doi>10.1145/268946.268956]
• 58: Knuth, D. 1971. An empirical study of FORTRAN programs. Softw. Pract. Exper. 1, 105--133.
• 59: Induprakas Kodukula , Nawaaz Ahmed , Keshav Pingali, Data-centric multi-level blocking, Proceedings of the ACM SIGPLAN 1997 conference on Programming language design and implementation, p.346-357, June 16-18, 1997, Las Vegas, Nevada, United States
• 60: Z. Li , P. C. Yew , C. Q. Zhu, An Efficient Data Dependence Analysis for Parallelizing Compilers, IEEE Transactions on Parallel and Distributed Systems, v.1 n.1, p.26-34, January 1990 [doi>10.1109/71.80122]
• 61: Liu, J., Chen, H., Yew, P.-C., and Hsu, W.-C. 2004. Design and implementation of a lightweight dynamic optimization system. J. Instruct.-Level Paral. 6.
• 62: 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
• 63: Marin, G. and Mellor-Crummey, J. 2005. Scalable cross-architecture predictions of memory hierarchy response for scientific applications. In Proceedings of the Symposium of the Las Alamos Computer Science Institute.
• 64: Mattson, R. L., Gecsei, J., Slutz, D., and Traiger, I. L. 1970. Evaluation techniques for storage hierarchies. IBM Syst. J. 9, 2, 78--117.
• 65: 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]
• 66: John Mellor-Crummey , David Whalley , Ken Kennedy, Improving Memory Hierarchy Performance for Irregular Applications Using Data and Computation Reorderings, International Journal of Parallel Programming, v.29 n.3, p.217-247, June 2001 [doi>10.1023/A:1011119519789]
• 67: Olken, F. 1981. Efficient methods for calculating the success function of fixed space replacement policies. Tech. rep. LBL-12370, Lawrence Berkeley Laboratory.
• 68: 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
• 69: Porterfield, A. 1989. Software methods for improvement of cache performance. Ph.D. thesis, Department of Computer Science, Rice University.
• 70: Rawlings, J. O. 1988. Applied Regression Analysis: A Research Tool. Wadsworth and Brooks.
• 71: Edward Rothberg , Jaswinder Pal Singh , Anoop Gupta, Working sets, cache sizes, and node granularity issues for large-scale multiprocessors, Proceedings of the 20th annual international symposium on Computer architecture, p.14-26, May 16-19, 1993, San Diego, California, United States
• 72: 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
• 73: 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]
• 74: 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
• 75: Xipeng Shen , Michael L. Scott , Chengliang Zhang , Sandhya Dwarkadas , Chen Ding , Mitsunori Ogihara, Analysis of input-dependent program behavior using active profiling, Proceedings of the 2007 workshop on Experimental computer science, p.5-es, June 13-14, 2007, San Diego, California [doi>10.1145/1281700.1281705]
• 76: 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
• 77: Shen, X., Zhong, Y., and Ding, C. 2004b. Phase-based miss rate prediction. In Proceedings of the International Workshop on Languages and Compilers for Parallel Computing.
• 78: Xipeng Shen , Yutao Zhong , Chen Ding, Predicting locality phases for dynamic memory optimization, Journal of Parallel and Distributed Computing, v.67 n.7, p.783-796, July, 2007 [doi>10.1016/j.jpdc.2007.01.010]
• 79: 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]
• 80: Yannis Smaragdakis , Scott Kaplan , Paul Wilson, The EELRU adaptive replacement algorithm, Performance Evaluation, v.53 n.2, p.93-123, July 2003 [doi>10.1016/S0166-5316(02)00226-2]
• 81: 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
• 82: Byoungro So , Mary W. Hall , Pedro C. Diniz, A compiler approach to fast hardware design space exploration in FPGA-based systems, Proceedings of the ACM SIGPLAN 2002 Conference on Programming language design and implementation, June 17-19, 2002, Berlin, Germany
• 83: Yonghong Song , Zhiyuan Li, New tiling techniques to improve cache temporal locality, Proceedings of the ACM SIGPLAN 1999 conference on Programming language design and implementation, p.215-228, May 01-04, 1999, Atlanta, Georgia, United States
• 84: 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
• 85: 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
• 86: Rabin Andrew Sugumar, Multi-configuration simulation algorithms for the evaluation of computer architecture designs, University of Michigan, Ann Arbor, MI, 1993
• 87: G. Edward Suh , Srinivas Devadas , Larry Rudolph, Analytical cache models with applications to cache partitioning, Proceedings of the 15th international conference on Supercomputing, p.1-12, June 2001, Sorrento, Italy [doi>10.1145/377792.377797]
• 88: Khalid Omar Thabit, Cache management by the compiler, Rice University, Houston, TX, 1982
• 89: James G. Thompson , Alan Jay Smith, Efficient (stack) algorithms for analysis of write-back and sector memories, ACM Transactions on Computer Systems (TOCS), v.7 n.1, p.78-117, Feb. 1989 [doi>10.1145/58564.59296]
• 90: Rémi Triolet , Francois Irigoin , Paul Feautrier, Direct parallelization of call statements, Proceedings of the 1986 SIGPLAN symposium on Compiler construction, p.176-185, June 25-27, 1986, Palo Alto, California, United States
• 91: David W. Wall, Predicting program behavior using real or estimated profiles, Proceedings of the ACM SIGPLAN 1991 conference on Programming language design and implementation, p.59-70, June 24-28, 1991, Toronto, Ontario, Canada
• 92: 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]
• 93: 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
• 94: Michael Joseph Wolfe , Carter Shanklin , Leda Ortega, High Performance Compilers for Parallel Computing, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1995
• 95: David Wonnacott, Achieving Scalable Locality with Time Skewing, International Journal of Parallel Programming, v.30 n.3, p.181-221, June 2002 [doi>10.1023/A:1015460304860]
• 96: Jingling Xue , Xavier Vera, Efficient and Accurate Analytical Modeling of Whole-Program Data Cache Behavior, IEEE Transactions on Computers, v.53 n.5, p.547-566, May 2004 [doi>10.1109/TC.2004.1275296]
• 97: Ting Yang , Emery D. Berger , Scott F. Kaplan , J. Eliot B. Moss, CRAMM: virtual memory support for garbage-collected applications, Proceedings of the 7th symposium on Operating systems design and implementation, November 06-08, 2006, Seattle, Washington
• 98: Qing Yi , Vikram Adve , Ken Kennedy, Transforming loops to recursion for multi-level memory hierarchies, Proceedings of the ACM SIGPLAN 2000 conference on Programming language design and implementation, p.169-181, June 18-21, 2000, Vancouver, British Columbia, Canada
• 99: 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
• 100: Peng Zhao , Shimin Cui , Yaoqing Gao , Raúl Silvera , José Nelson Amaral, Forma: A framework for safe automatic array reshaping, ACM Transactions on Programming Languages and Systems (TOPLAS), v.30 n.1, p.2-es, November 2007 [doi>10.1145/1290520.1290522]
• 101: Yutao Zhong , Wentao Chang, Sampling-based program locality approximation, Proceedings of the 7th international symposium on Memory management, June 07-08, 2008, Tucson, AZ, USA [doi>10.1145/1375634.1375648]
• 102: Zhong, Y., Ding, C., and Kennedy, K. 2002. Reuse distance analysis for scientific programs. In Proceedings of Workshop on Languages, Compilers, and Runtime Systems for Scalable Computers.
• 103: 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]
• 104: 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
• 105: Pin Zhou , Vivek Pandey , Jagadeesan Sundaresan , Anand Raghuraman , Yuanyuan Zhou , Sanjeev Kumar, Dynamic tracking of page miss ratio curve for memory management, Proceedings of the 11th international conference on Architectural support for programming languages and operating systems, October 07-13, 2004, Boston, MA, USA
• 106: Yuanyuan Zhou , James Philbin , Kai Li, The Multi-Queue Replacement Algorithm for Second Level Buffer Caches, Proceedings of the General Track: 2002 USENIX Annual Technical Conference, p.91-104, June 25-30, 2001

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, Languages, Measurement

Keywords:
Program locality, reuse distance, stack distance, training-based analysis