A fast and accurate framework to analyze and optimize cache memory behavior

ABSTRACT

The gap between processor and main memory performance increases every year. In order to overcome this problem, cache memories are widely used. However, they are only effective when programs exhibit sufficient data locality. Compile-time program transformations can significantly improve the performance of the cache. To apply most of these transformations, the compiler requires a precise knowledge of the locality of the different sections of the code, both before and after being transformed.Cache miss equations (CMEs) allow us to obtain an analytical and precise description of the cache memory behavior for loop-oriented codes. Unfortunately, a direct solution of the CMEs is computationally intractable due to its NP-complete nature.This article proposes a fast and accurate approach to estimate the solution of the CMEs. We use sampling techniques to approximate the absolute miss ratio of each reference by analyzing a small subset of the iteration space. The size of the subset, and therefore the analysis time, is determined by the accuracy selected by the user. In order to reduce the complexity of the algorithm to solve CMEs, effective mathematical techniques have been developed to analyze the subset of the iteration space that is being considered. These techniques exploit some properties of the particular polyhedra represented by CMEs.

REFERENCES

• 1: Jaume Abella, Near-Optimal Loop Tiling by Means of Cache Miss Equations and Genetic Algorithms, Proceedings of the 2002 International Conference on Parallel Processing Workshops, p.568, August 18-21, 2002
• 2: 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
• 3: 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
• 4: Ayguadé, E. et al. 1995. A uniform internal representation for high-level and instruction-level transformations. Tech rep. UPC-DAC-95-02. Universitat Politècnica de Catalunya, Barcelona, Spain.
• 5: Utpal K. Banerjee, Dependence Analysis for Supercomputing, Kluwer Academic Publishers, Norwell, MA, 1988
• 6: Utpal K. Banerjee, Loop Transformations for Restructuring Compilers: The Foundations, Kluwer Academic Publishers, Norwell, MA, 1993
• 7: Robert C. Bedichek, Talisman: fast and accurate multicomputer simulation, Proceedings of the 1995 ACM SIGMETRICS joint international conference on Measurement and modeling of computer systems, p.14-24, May 15-19, 1995, Ottawa, Ontario, Canada
• 8: S. Carr , K. Kennedy, Compiler blockability of numerical algorithms, Proceedings of the 1992 ACM/IEEE conference on Supercomputing, p.114-124, November 16-20, 1992, Minneapolis, Minnesota, United States
• 9: Steve Carr , Kathryn S. McKinley , Chau-Wen Tseng, Compiler optimizations for improving data locality, Proceedings of the sixth international conference on Architectural support for programming languages and operating systems, p.252-262, October 05-07, 1994, San Jose, California, United States
• 10: Siddhartha Chatterjee , Vibhor V. Jain , Alvin R. Lebeck , Shyam Mundhra , Mithuna Thottethodi, Nonlinear array layouts for hierarchical memory systems, Proceedings of the 13th international conference on Supercomputing, p.444-453, June 20-25, 1999, Rhodes, Greece [doi>10.1145/305138.305231]
• 11: 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
• 12: Philippe Clauss, Counting solutions to linear and nonlinear constraints through Ehrhart polynomials: applications to analyze and transform scientific programs, Proceedings of the 10th international conference on Supercomputing, p.278-285, May 25-28, 1996, Philadelphia, Pennsylvania, United States [doi>10.1145/237578.237617]
• 13: Stephanie Coleman , Kathryn S. McKinley, Tile size selection using cache organization and data layout, Proceedings of the ACM SIGPLAN 1995 conference on Programming language design and implementation, p.279-290, June 18-21, 1995, La Jolla, California, United States
• 14: DeGroot, M. 1998. Probability and Statistics. Addison-Wesley, Reading, MA.
• 15: Paul Feautrier, Automatic Parallelization in the Polytope Model, The Data Parallel Programming Model: Foundations, HPF Realization, and Scientific Applications, p.79-103, January 1996
• 16: Basilio B. Fraguela , Ramon Doallo , Emilio L. Zapata, Automatic Analytical Modeling for the Estimation of Cache Misses, Proceedings of the 1999 International Conference on Parallel Architectures and Compilation Techniques, p.221, October 12-16, 1999
• 17: Dennis Gannon , William Jalby , Kyle Gallivan, Strategies for cache and local memory management by global program transformation, Journal of Parallel and Distributed Computing, v.5 n.5, p.587-616, October 1988 [doi>10.1016/0743-7315(88)90014-7]
• 18: Jeffrey D. Gee , Mark D. Hill , Dionisios N. Pnevmatikatos , Alan Jay Smith, Cache Performance of the SPEC92 Benchmark Suite, IEEE Micro, v.13 n.4, p.17-27, July 1993 [doi>10.1109/40.229711]
• 19: Somnath Ghosh , Margaret Martonosi, Cache miss equations: compiler analysis framework for tuning memory behavior, 1999
• 20: Somnath Ghosh , Margaret Martonosi , Sharad Malik, Precise miss analysis for program transformations with caches of arbitrary associativity, Proceedings of the eighth international conference on Architectural support for programming languages and operating systems, p.228-239, October 02-07, 1998, San Jose, California, United States
• 21: 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]
• 22: Somnath Ghosh , Margaret Martonosi , Sharad Malik, Automated cache optimizations using CME driven diagnosis, Proceedings of the 14th international conference on Supercomputing, p.316-326, May 08-11, 2000, Santa Fe, New Mexico, United States [doi>10.1145/335231.335262]
• 23: Aaron J. Goldberg , John L. Hennessy, Performance debugging shared memory multiprocessor programs with MTOOL, Proceedings of the 1991 ACM/IEEE conference on Supercomputing, p.481-490, November 18-22, 1991, Albuquerque, New Mexico, United States [doi>10.1145/125826.126075]
• 24: Stephen R. Goldschmidt , John L. Hennessy, The accuracy of trace-driven simulations of multiprocessors, Proceedings of the 1993 ACM SIGMETRICS conference on Measurement and modeling of computer systems, p.146-157, May 10-14, 1993, Santa Clara, California, United States
• 25: Mohammad R. Haghighat , Constantine D. Polychronopoulos, Symbolic Analysis: A Basis for Parallelization, Optimization, and Scheduling of Programs, Proceedings of the 6th International Workshop on Languages and Compilers for Parallel Computing, p.567-585, August 12-14, 1993
• 26: Hill, M. n.d. DineroIII: a uniprocessor cache simulator (http://www.cs.wisc.edu/∼larus/warts.html).
• 27: Mahmut Kandemir , Alok Choudhary , Nagaraj Shenoy , Prithviraj Banerjee , J. Ramanujam, A Linear Algebra Framework for Automatic Determination of Optimal Data Layouts, IEEE Transactions on Parallel and Distributed Systems, v.10 n.2, p.115-135, February 1999 [doi>10.1109/71.752779]
• 28: David Callahan , Ken Kennedy , Allan Porterfield, Analyzing and visualizing performance of memory hierarchies, Parallel computer systems: performance instrumentation and visualization, ACM Press, New York, NY, 1990 [doi>10.1145/100215.100233]
• 29: Kreisel, G. and Krevine, J. L. 1967. Elements of Mathematical Logic. North-Holland, Amsterdam, The Netherlands.
• 30: Monica D. Lam , Edward E. Rothberg , Michael E. Wolf, The cache performance and optimizations of blocked algorithms, Proceedings of the fourth international conference on Architectural support for programming languages and operating systems, p.63-74, April 08-11, 1991, Santa Clara, California, United States
• 31: Alvin R. Lebeck , David A. Wood, Cache Profiling and the SPEC Benchmarks: A Case Study, Computer, v.27 n.10, p.15-26, October 1994 [doi>10.1109/2.318580]
• 32: Peter S. Magnusson, A Design for Efficient Simulation of a Multiprocessor, Proceedings of the International Workshop on Modeling, Analysis, and Simulation On Computer and Telecommunication Systems, p.69-78, January 17-20, 1993
• 33: Margaret Martonosi , Anoop Gupta , Thomas Anderson, MemSpy: analyzing memory system bottlenecks in programs, Proceedings of the 1992 ACM SIGMETRICS joint international conference on Measurement and modeling of computer systems, p.1-12, June 01-05, 1992, Newport, Rhode Island, United States
• 34: Margaret Martonosi , Anoop Gupta , Thomas Anderson, Effectiveness of trace sampling for performance debugging tools, Proceedings of the 1993 ACM SIGMETRICS conference on Measurement and modeling of computer systems, p.248-259, May 10-14, 1993, Santa Clara, California, United States
• 35: McCabe, M. 1989. Introduction to the Practice of Statistics. Freeman & Co., New York, NY.
• 36: Kathryn S. McKinley , Olivier Temam, A quantitative analysis of loop nest locality, Proceedings of the seventh international conference on Architectural support for programming languages and operating systems, p.94-104, October 01-04, 1996, Cambridge, Massachusetts, United States
• 37: MIPS. 1988. RISCompiler Languages Programmer's Guide. MIPS Computer Systems, Sunnyvale, CA.
• 38: Todd C. Mowry , Monica S. Lam , Anoop Gupta, Design and evaluation of a compiler algorithm for prefetching, Proceedings of the fifth international conference on Architectural support for programming languages and operating systems, p.62-73, October 12-15, 1992, Boston, Massachusetts, United States
• 39: Padua, D. et al. 1994. Polaris Developer's Document. Available online at http://polaris.is.uiuc.edu/polaris/polaris--developer/polaris--developer.html.
• 40: William Pugh, The Omega test: a fast and practical integer programming algorithm for dependence analysis, Proceedings of the 1991 ACM/IEEE conference on Supercomputing, p.4-13, November 18-22, 1991, Albuquerque, New Mexico, United States [doi>10.1145/125826.125848]
• 41: William Pugh, Counting solutions to Presburger formulas: how and why, Proceedings of the ACM SIGPLAN 1994 conference on Programming language design and implementation, p.121-134, June 20-24, 1994, Orlando, Florida, United States
• 42: Gabriel Rivera , Chau-Wen Tseng, Data transformations for eliminating conflict misses, Proceedings of the ACM SIGPLAN 1998 conference on Programming language design and implementation, p.38-49, June 17-19, 1998, Montreal, Quebec, Canada
• 43: Gabriel Rivera , Chau-Wen Tseng, A Comparison of Compiler Tiling Algorithms, Proceedings of the 8th International Conference on Compiler Construction, Held as Part of the European Joint Conferences on the Theory and Practice of Software, ETAPS'99, p.168-182, March 22-28, 1999
• 44: Sánchez, F. and González, A. 1998. Fast, flexible and accurate data locality analysis. In Proceedings of the International Conference on Parallel Architectures and Compilation Techniques (PACT'98).
• 45: Jesús Sánchez , Antonio González, Modulo scheduling for a fully-distributed clustered VLIW architecture, Proceedings of the 33rd annual ACM/IEEE international symposium on Microarchitecture, p.124-133, December 2000, Monterey, California, United States [doi>10.1145/360128.360142]
• 46: Rabin Andrew Sugumar, Multi-configuration simulation algorithms for the evaluation of computer architecture designs, University of Michigan, Ann Arbor, MI, 1993
• 47: O. Temam , C. Fricker , W. Jalby, Cache interference phenomena, Proceedings of the 1994 ACM SIGMETRICS conference on Measurement and modeling of computer systems, p.261-271, May 16-20, 1994, Nashville, Tennessee, United States
• 48: O. Temam , E. D. Granston , W. Jalby, To copy or not to copy: a compile-time technique for assessing when data copying should be used to eliminate cache conflicts, Proceedings of the 1993 ACM/IEEE conference on Supercomputing, p.410-419, December 1993, Portland, Oregon, United States [doi>10.1145/169627.169762]
• 49: Richard A. Uhlig , Trevor N. Mudge, Trace-driven memory simulation: a survey, ACM Computing Surveys (CSUR), v.29 n.2, p.128-170, June 1997 [doi>10.1145/254180.254184]
• 50: Eric van der Deijl , Gerco Kanbier , Olivier Temam , Elena D. Granston, A Cache Visualization Tool, Computer, v.30 n.7, p.71-78, July 1997 [doi>10.1109/2.596631]
• 51: Vera, X., Llosa, J., and González, A. 2002. Near-optimal padding for removing conflict misses. In Proceedings of the 15th Workshop on Languages and Compilers for Parallel Computers (LCPC'02).
• 52: Xavier Vera , Jingling Xue, Let's Study Whole-Program Cache Behaviour Analytically, Proceedings of the 8th International Symposium on High-Performance Computer Architecture, p.175, February 02-06, 2002
• 53: Wilde, D. 1993. A library for doing polyhedral operations. Tech. rep. 785, Oregon State University.
• 54: Emmett Witchel , Mendel Rosenblum, Embra: fast and flexible machine simulation, Proceedings of the 1996 ACM SIGMETRICS international conference on Measurement and modeling of computer systems, p.68-79, May 23-26, 1996, Philadelphia, Pennsylvania, United States
• 55: 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

INDEX TERMS

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

Additional Classification:
  C. Computer Systems Organization
  C.4 PERFORMANCE OF SYSTEMS
      Subjects: Measurement techniques

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

General Terms:
Design, Performance

Keywords:
Cache memories, optimization, sampling