Feedback-directed memory disambiguation through store distance analysis

ABSTRACT

Feedback-directed optimization has developed into an increasingly important tool in designing optimizing compilers. Based upon profiling, memory distance analysis has shown much promise in predicting data locality and memory dependences, and has seen use in locality based optimizations and memory disambiguation. In this paper, we apply a form of memory distance, called store distance, to the problem of memory disambiguation in out-of-order issue processors. Store distance is defined as the number of store references between a load and the previous store accessing the same memory location. By generating a representative store distance for each load instruction, we can apply a compiler/micro-architecture cooperative scheme to direct run-time load speculation. Using store distance, the processor can, in most cases, accurately determine on which specific store instruction a load depends according to its store distance annotation. Our experiments show that the proposed store distance method performs much better than the previous distance based memory disambiguation scheme, and yields a performance very close to perfect memory disambiguation. The store distance based scheme also outperforms the store set technique with a relatively small predictor space and achieves performance comparable to that of a 16K-entry store set implementation for both floating point and integer programs.

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: 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, 2001.
• 3: 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
• 4: 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]
• 5: George Z. Chrysos , Joel S. Emer, Memory dependence prediction using store sets, Proceedings of the 25th annual international symposium on Computer architecture, p.142-153, June 27-July 02, 1998, Barcelona, Spain
• 6: Chen Ding , Ken Kennedy, Improving effective bandwidth through compiler enhancement of global and dynamic cache reuse, 2000
• 7: 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
• 8: Changpeng Fang , Steve Carr , Soner Önder , Zhenlin Wang, Reuse-distance-based miss-rate prediction on a per instruction basis, Proceedings of the 2004 workshop on Memory system performance, June 08-08, 2004, Washington, D.C. [doi>10.1145/1065895.1065906]
• 9: 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]
• 10: Gina Goff , Ken Kennedy , Chau-Wen Tseng, Practical dependence testing, Proceedings of the ACM SIGPLAN 1991 conference on Programming language design and implementation, p.15-29, June 24-28, 1991, Toronto, Ontario, Canada
• 11: J. Hesson, J. LeBlanc, and S. Ciavaglia. Apparatus to dynamically control the Out-Of-Order execution of Load-Store instructions. US. Patent 5, 615, 350, Filed Dec. 1995, Issued Mar. 1997.
• 12: 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
• 13: 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
• 14: R. L. Mattson, J. Gecsei, D. Slutz, and I. L. Traiger. Evaluation techniques for storage hierarchies. IBM Systems Journal, 9(2):78--117, 1970.
• 15: Andreas Ioannis Moshovos , Gurindar S. Sohi, Memory dependence prediction, 1998
• 16: Andreas Moshovos , Scott E. Breach , T. N. Vijaykumar , Gurindar S. Sohi, Dynamic speculation and synchronization of data dependences, Proceedings of the 24th annual international symposium on Computer architecture, p.181-193, June 01-04, 1997, Denver, Colorado, United States
• 17: Soner Önder, Cost Effective Memory Dependence Prediction using Speculation Levels and Color Sets, Proceedings of the 2002 International Conference on Parallel Architectures and Compilation Techniques, p.232, September 22-25, 2002
• 18: Soner Önder , Rajiv Gupta, Automatic Generation of Microarchitecture Simulators, Proceedings of the 1998 International Conference on Computer Languages, p.80, May 14-16, 1998
• 19: S. Onder and R. Gupta. Dynamic memory disambiguation in the presence of out-of-order store issuing. Journal of Instruction Level Parallelism, Volume 4, June 2002. (www.microarch.org/vol4).
• 20: Glenn Reinman , Brad Calder , Dean Tullsen , Gary Tyson , Todd Austin, Classifying load and store instructions for memory renaming, Proceedings of the 13th international conference on Supercomputing, p.399-407, June 20-25, 1999, Rhodes, Greece [doi>10.1145/305138.305218]
• 21: 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
• 22: 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
• 23: S. Steely, D. Sager, and D. Fite. Memory reference tagging. US. Patent 5, 619, 662, Filed Aug. 1994, Issued Apr. 1997.
• 24: Rabin A. Sugumar , Santosh G. Abraham, Efficient simulation of caches under optimal replacement with applications to miss characterization, Proceedings of the 1993 ACM SIGMETRICS conference on Measurement and modeling of computer systems, p.24-35, May 10-14, 1993, Santa Clara, California, United States
• 25: Zhenlin Wang , Kathryn S. Mckinley, Cooperative hardware/software caching for next-generation memory systems, 2004
• 26: Adi Yoaz , Mattan Erez , Ronny Ronen , Stephan Jourdan, Speculation techniques for improving load related instruction scheduling, Proceedings of the 26th annual international symposium on Computer architecture, p.42-53, May 01-04, 1999, Atlanta, Georgia, United States
• 27: Y Zhong, C. Ding, and K. Kennedy. Reuse distance analysis for scientific programs. In Proceedings of Workshop on Language, Compilers, and Runtime Systems for Scalable Compilers, Washington, DC, 2002.
• 28: Yutao Zhong , Steven G. Dropsho , Chen Ding, Miss Rate Prediction across All Program Inputs, Proceedings of the 12th International Conference on Parallel Architectures and Compilation Techniques, p.79, September 27-October 01, 2003
• 29: 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.1 PROCESSOR ARCHITECTURES
      C.1.1 Single Data Stream Architectures

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

General Terms:
Languages, Performance

Keywords:
memory disambiguation, store distance