Exact analysis of the cache behavior of nested loops

ABSTRACT

We develop from first principles an exact model of the behavior of loop nests executing in a memory hicrarchy, by using a nontraditional classification of misses that has the key property of composability. We use Presburger formulas to express various kinds of misses as well as the state of the cache at the end of the loop nest. We use existing tools to simplify these formulas and to count cache misses. The model is powerful enough to handle imperfect loop nests and various flavors of non-linear array layouts based on bit interleaving of array indices. We also indicate how to handle modest levels of associativity, and how to perform limited symbolic analysis of cache behavior. The complexity of the formulas relates to the static structure of the loop nest rather than to its dynamic trip count, allowing our model to gain efficiency in counting cache misses by exploiting repetitive patterns of cache behavior. Validation against cache simulation confirms the exactness of our formulation. Our method can serve as the basis for a static performance predictor to guide program and data transformations to improve performance.

REFERENCES

• 1: A. Agarwal , J. Hennessy , M. Horowitz, An analytical cache model, ACM Transactions on Computer Systems (TOCS), v.7 n.2, p.184-215, May 1989 [doi>10.1145/63404.63407]
• 2: Nawaaz Ahmed , Keshav Pingali, Locality enhancement of imperfectly nested loop nests, 2000
• 3: Nawaaz Ahmed , Nikolay Mateev , Keshav Pingali, Tiling Imperfectly-nested Loop Nests (REVISED), Cornell University, Ithaca, NY, 2000
• 4: Nawaaz Ahmed , Keshav Pingali, Automatic Generation of Block-Recursive Codes, Proceedings from the 6th International Euro-Par Conference on Parallel Processing, p.368-378, August 29-September 01, 2000
• 5: Martin Alt , Christian Ferdinand , Florian Martin , Reinhard Wilhelm, Cache Behavior Prediction by Abstract Interpretation, Proceedings of the Third International Symposium on Static Analysis, p.52-66, September 24-26, 1996
• 6: Tod Amon , Gaetano Borriello , Taokuan Hu , Jiwen Liu, Symbolic timing verification of timing diagrams using Presburger formulas, Proceedings of the 34th annual conference on Design automation, p.226-231, June 09-13, 1997, Anaheim, California, United States [doi>10.1145/266021.266071]
• 7: Tod Amon , Gaetano Borriello , Jiwen Liu, Making complex timing relationships readable: Presburger formula simplicication using don't cares, Proceedings of the 35th annual conference on Design automation, p.586-590, June 15-19, 1998, San Francisco, California, United States [doi>10.1145/277044.277198]
• 8: Pierre Wolper , Bernard Boigelot, An Automata-Theoretic Approach to Presburger Arithmetic Constraints (Extended Abstract), Proceedings of the Second International Symposium on Static Analysis, p.21-32, September 25-27, 1995
• 9: Alexandre Boudet , Hubert Comon, Diophantine Equations, Presburger Arithmetic and Finite Automata, Proceedings of the 21st International Colloquium on Trees in Algebra and Programming, p.30-43, April 22-24, 1996
• 10: P. Boulet and X. Redon. SPPoC: fonctionnemen et applications. Research Report 00-04, LIFL (Laboratoire de Recherche en Informatique de l'Universite des Sciences et Technologies de Lille), 2000. In French. Also see http://www.lifl.fr/west/sppoc/.
• 11: M. Brehob and R. Enbody. A mathematical model of locality and caching. Technical Report TR-MSU-CPS-96-TBD, Michigan State University, Nov. 1996.
• 12: Gheorghe Calin Cascaval , David A Padua, Compile-time performance prediction of scientific programs, 2000
• 13: 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
• 14: 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]
• 15: Siddhartha Chatterjee , Alvin R. Lebeck , Praveen K. Patnala , Mithuna Thottethodi, Recursive array layouts and fast parallel matrix multiplication, Proceedings of the eleventh annual ACM symposium on Parallel algorithms and architectures, p.222-231, June 27-30, 1999, Saint Malo, France [doi>10.1145/305619.305645]
• 16: S. Chatterjee and S. Sen. Cache-efficient matrix transposition. In Proceedings of HPCA-6, pages 195-205, Toulouse, France, Jan. 2000.
• 17: 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
• 18: 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]
• 19: 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
• 20: P. Feautrier. Dataflow analysis of array and scalar references. International Journal of Parallel Programming, 20(1):23-54, 1991.
• 21: Jeremy D. Frens , David S. Wise, Auto-blocking matrix-multiplication or tracking BLAS3 performance from source code, Proceedings of the sixth ACM SIGPLAN symposium on Principles and practice of parallel programming, p.206-216, June 18-21, 1997, Las Vegas, Nevada, United States
• 22: Christine Fricker , Olivier Temam , William Jalby, Influence of cross-interferences on blocked loops: a case study with matrix-vector multiply, ACM Transactions on Programming Languages and Systems (TOPLAS), v.17 n.4, p.561-575, July 1995 [doi>10.1145/210184.210185]
• 23: Somnath Ghosh , Margaret Martonosi, Cache miss equations: compiler analysis framework for tuning memory behavior, 1999
• 24: Somnath Ghosh , Margaret Martonosi , Sharad Malik, Cache miss equations: an analytical representation of cache misses, Proceedings of the 11th international conference on Supercomputing, p.317-324, July 07-11, 1997, Vienna, Austria [doi>10.1145/263580.263657]
• 25: 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
• 26: 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]
• 27: Philip J. Hanlon , Dean Chung , Siddhartha Chatterjee , Daniela Genius , Alvin R. Lebeck , Erin Parker, The combinatorics of cache misses during matrix multiplication, Journal of Computer and System Sciences, v.63 n.1, p.80-126, August 2001 [doi>10.1006/jcss.2001.1756]
• 28: John S. Harper , Darren J. Kerbyson , Graham R. Nudd, Analytical Modeling of Set-Associative Cache Behavior, IEEE Transactions on Computers, v.48 n.10, p.1009-1024, October 1999 [doi>10.1109/12.805152]
• 29: Mark D. Hill , James R. Larus , Alvin R. Lebeck , Madhusudhan Talluri , David A. Wood, Wisconsin Architectural Research Tool Set, ACM SIGARCH Computer Architecture News, v.21 n.4, p.8-10, Sept. 1993 [doi>10.1145/165496.165500]
• 30: 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]
• 31: John E. Hopcroft , Jeffrey D. Ullman, Introduction To Automata Theory, Languages, And Computation, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1990
• 32: 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]
• 33: W. Kelly, V. Maslov, W. Pugh, E. Rosser, T. Shpeisman, and D. Wonnacott. The Omega Calculator and Library, version 1.1.0, Nov. 1996.
• 34: W. Kelly, V. Maslov, W. Pugh, E. Rosser, T. Shpeisman, and D. Wonnacott. The Omega Library Version 1.1.0 Interface Guide, Nov. 1996.
• 35: Wayne Kelly , William Pugh, A framework for unifying reordering transformations, University of Maryland at College Park, College Park, MD, 1993
• 36: W. Kelly and W. Pugh. Finding legal reordering transformations using mappings. Technical Report CS-TR-3297, Department of Compute Science, University of Maryland, College Park, MD, June 1994.
• 37: R. E. Kessler , Mark D. Hill, Page placement algorithms for large real-indexed caches, ACM Transactions on Computer Systems (TOCS), v.10 n.4, p.338-359, Nov. 1992 [doi>10.1145/138873.138876]
• 38: 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
• 39: 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]
• 40: Alvin R. Lebeck , David A. Wood, Active memory: a new abstraction for memory system simulation, ACM Transactions on Modeling and Computer Simulation (TOMACS), v.7 n.1, p.42-77, Jan. 1997 [doi>10.1145/244804.244806]
• 41: Amy W. Lim , Monica S. Lam, Maximizing parallelism and minimizing synchronization with affine transforms, Proceedings of the 24th ACM SIGPLAN-SIGACT symposium on Principles of programming languages, p.201-214, January 15-17, 1997, Paris, France [doi>10.1145/263699.263719]
• 42: V. Loechner. PolyLib: A Library for Manipulating Parameterized Polyhedra, Mar. 1999.
• 43: 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
• 44: Kathryn S. McKinley , Olivier Temam, Quantifying loop nest locality using SPEC'95 and the perfect benchmarks, ACM Transactions on Computer Systems (TOCS), v.17 n.4, p.288-336, Nov. 1999 [doi>10.1145/329466.329484]
• 45: Nicholas Mitchell , Larry Carter , Jeanne Ferrante , Karin Högstedt, Quantifying the Multi-level Nature of Tiling Interactions, Proceedings of the 10th International Workshop on Languages and Compilers for Parallel Computing, p.1-15, August 07-09, 1997
• 46: D. C. Oppen. A 2 2 2 pn upper bound on the complexity of Presburger arithmetic. J. Comput. Syst. Sci., 16(3):323-332, July 1978.
• 47: Yunheung Paek , Jay Hoeflinger , David Padua, Simplification of array access patterns for compiler optimizations, Proceedings of the ACM SIGPLAN 1998 conference on Programming language design and implementation, p.60-71, June 17-19, 1998, Montreal, Quebec, Canada
• 48: Allan Kennedy Porterfield , K. W. Kennedy, Software methods for improvement of cache performance on supercomputer applications, 1989
• 49: 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
• 50: 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
• 51: Gabriel Rivera , Chau-Wen Tseng, Eliminating conflict misses for high performance architectures, Proceedings of the 12th international conference on Supercomputing, p.353-360, July 1998, Melbourne, Australia [doi>10.1145/277830.277917]
• 52: U. Sch~ning. Complexity of Presburger arithmetic with fixed quantifier dimension. Theory of Computing Systems, 30:423-428, 1997.
• 53: N. Shibata, K. Okana, T. Higashino, and K. Taniguchi. A decision algorithm dor prenex form rational Presburger sentences based on combinatorial geometry. In Proceedings of the 2nd International Conference on Discrete Mathematics and Theoretical Computer Science and the 5th Australasian Theory Symposium (DMTCS'99+CATS'99), pages 344-359, Jan. 1999.
• 54: 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
• 55: The Stanford Compiler Group. SUIF: An Infrastructure for Research on Parallelizing and Optimizing Compilers. http://suif.stanford.edu.
• 56: R. A. Sugumar and S. G. Abraham. Efficient simulation of multiple cache configurations using binomial trees. Technical Report CSE-TR-111-91, 1991.
• 57: Dominique Thiebaut , Harold S. Stone, Footprints in the cache, ACM Transactions on Computer Systems (TOCS), v.5 n.4, p.305-329, Nov. 1987 [doi>10.1145/29868.32979]
• 58: D. Weikle , S. McKee , W. Wulf, Caches as Filters: A New Approach to Cache Analysis, Proceedings of the 6th International Symposium on Modeling, Analysis and Simulation of Computer and Telecommunication Systems, p.2, July 19-24, 1998
• 59: Dee A. B. Weikle , Kevin Skadron , Sally A. McKee , Wm Wulf, Caches As Filters: A Unifying Model for Memory Hierarchy Analysis, University of Virginia, Charlottesville, VA, 2000
• 60: Volker Weispfenning, Complexity and uniformity of elimination in Presburger arithmetic, Proceedings of the 1997 international symposium on Symbolic and algebraic computation, p.48-53, July 21-23, 1997, Kihei, Maui, Hawaii, United States [doi>10.1145/258726.258746]
• 61: 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
• 62: M. Wolfe, More iteration space tiling, Proceedings of the 1989 ACM/IEEE conference on Supercomputing, p.655-664, November 12-17, 1989, Reno, Nevada, United States [doi>10.1145/76263.76337]
• 63: David A. Wood , Mark D. Hill , R. E. Kessler, A model for estimating trace-sample miss ratios, Proceedings of the 1991 ACM SIGMETRICS conference on Measurement and modeling of computer systems, p.79-89, May 21-24, 1991, San Diego, California, United States
• 64: H. Zhang and M. Martonosi. Mathematical cache miss analysis for pointer data structures. In Proceedings of the SIAM Conference on Parallel Processing for Scientific Computing, Portsmouth, VA, Mar. 2001. CD-ROM.

INDEX TERMS

Primary Classification:
  D. Software
  D.3 PROGRAMMING LANGUAGES
      D.3.3 Language Constructs and Features
          Subjects: Concurrent programming structures

General Terms:
Design, Languages, Measurement, Performance, Reliability, Theory