Static analysis for fast and accurate design space exploration of caches

ABSTRACT

Application-specific system-on-chip platforms create the opportunity to customize the cache configuration for optimal performance with minimal chip estate. Simulation, in particular trace-driven simulation, is widely used to estimate cache hit rates. However, simulation is too slow to be deployed in the design space exploration, specially when it involves hundreds of design points and huge traces or long program execution. In this paper, we propose a novel static analysis technique for rapid and accurate design space exploration of instruction caches. Given the program control flow graph (CFG) annotated only with basic block and control flow edge execution counts, our analysis estimates the hit rates for multiple cache configurations in one pass. We achieve this by modeling the cache states at each node of the CFG in probabilistic manner and exploiting the structural similarities among related cache configurations. Experimental results indicate that our analysis is 24--3,855 times faster compared to the fastest known cache simulator while maintaining high accuracy (0.7% average error), in predicting hit rates for popular embedded benchmarks.

REFERENCES

• 1: Todd Austin , Eric Larson , Dan Ernst, SimpleScalar: An Infrastructure for Computer System Modeling, Computer, v.35 n.2, p.59-67, February 2002 [doi>10.1109/2.982917]
• 2: Thomas Ball, Efficiently counting program events with support for on-line queries, ACM Transactions on Programming Languages and Systems (TOPLAS), v.16 n.5, p.1399-1410, Sept. 1994 [doi>10.1145/186025.186027]
• 3: 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
• 4: Arijit Ghosh , Tony Givargis, Analytical Design Space Exploration of Caches for Embedded Systems, Proceedings of the conference on Design, Automation and Test in Europe, p.10650, March 03-07, 2003
• 5: M. R. Guthaus , J. S. Ringenberg , D. Ernst , T. M. Austin , T. Mudge , R. B. Brown, MiBench: A free, commercially representative embedded benchmark suite, Proceedings of the Workload Characterization, 2001. WWC-4. 2001 IEEE International Workshop, p.3-14, December 02-02, 2001 [doi>10.1109/WWC.2001.15]
• 6: 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]
• 7: Andhi Janapsatya , Aleksandar Ignjatovic , Sri Parameswaran , Joerg Henkel, Instruction trace compression for rapid instruction cache simulation, Proceedings of the conference on Design, automation and test in Europe, April 16-20, 2007, Nice, France
• 8: S. Laha , J. H. Patel , R. K. Iyer, Accurate Low-Cost Methods for Performance Evaluation of Cache Memory Systems, IEEE Transactions on Computers, v.37 n.11, p.1325-1336, November 1988 [doi>10.1109/12.8699]
• 9: Yanbing Li , Tim Callahan , Ervan Darnell , Randolph Harr , Uday Kurkure , Jon Stockwood, Hardware-software co-design of embedded reconfigurable architectures, Proceedings of the 37th conference on Design automation, p.507-512, June 05-09, 2000, Los Angeles, California, United States [doi>10.1145/337292.337559]
• 10: Yun Liang , Tulika Mitra, Cache modeling in probabilistic execution time analysis, Proceedings of the 45th annual conference on Design automation, June 08-13, 2008, Anaheim, California [doi>10.1145/1391469.1391551]
• 11: R. L. Mattson et al. Evaluation techniques for storage hierarchies. IBM Systems Journal, 9(2), 1970.
• 12: Gokul Rajaram , V. Rajaraman, A probabilistic method for calculating hit ratios in direct mapped caches, Journal of Network and Computer Applications, v.19 n.3, p.309-319, July 1996 [doi>10.1006/jnca.1996.0021]
• 13: Rabin A. Sugumar , Santosh G. Abraham, Set-associative cache simulation using generalized binomial trees, ACM Transactions on Computer Systems (TOCS), v.13 n.1, p.32-56, Feb. 1995 [doi>10.1145/200912.200918]
• 14: Wen-Hann Wang , Jean-Loup Baer, Efficient trace-driven simulation method for cache performance analysis, Proceedings of the 1990 ACM SIGMETRICS conference on Measurement and modeling of computer systems, p.27-36, April 1990, Univ. of Colorado, Boulder, Colorado, United States
• 15: Zhao Wu , Wayne Wolf, Iterative cache simulation of embedded CPUs with trace stripping, Proceedings of the seventh international workshop on Hardware/software codesign, p.95-99, March 1999, Rome, Italy [doi>10.1145/301177.301496]

INDEX TERMS

Primary Classification:
  B. Hardware
  B.3 MEMORY STRUCTURES
      B.3.2 Design Styles
          Subjects: Cache memories

General Terms:
Algorithms, Design, Performance

Keywords:
cache, design space exploration, probabilistic cache states