Take a look at the new version of this page: [ beta version ]. Tell us what you think.

ABSTRACT

Cache miss characterization models such as the three Cs model are useful in developing schemes to reduce cache misses and their penalty. In this paper we propose the OPT model that uses cache simulation under optimal (OPT) replacement to obtain a finer and more accurate characterization of misses than the three Cs model. However, current methods for optimal cache simulation are slow and difficult to use. We present three new techniques for optimal cache simulation. First, we propose a limited lookahead strategy with error fixing, which allows one pass simulation of multiple optimal caches. Second, we propose a scheme to group entries in the OPT stack, which allows efficient tree based fully-associative cache simulation under OPT. Third, we propose a scheme for exploiting partial inclusion in set-associative cache simulation under OPT. Simulators based on these algorithms were used to obtain cache miss characterizations using the OPT model for nine SPEC benchmarks. The results indicate that miss ratios under OPT are substantially lower than those under LRU replacement, by up to 70% in fully-associative caches, and up to 32% in two-way set-associative caches.

REFERENCES

• 1: A. Agarwal, Analysis of cache performance for operating systems and multiprogramming, Stanford University, Stanford, CA, 1987
• 2: L. A. Belady. A study of replacement algorithms for a virtual-storage computer. IBM Systems Journal, 5(2):78-101, 1966.
• 3: B. T. Bennett and V. J. Kruskal. LRU stack processing. IBM J. of Research and Development, pages 353-357, July 1975.
• 4: 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]
• 5: David A. Patterson , John L. Hennessy, Computer architecture: a quantitative approach, Morgan Kaufmann Publishers Inc., San Francisco, CA, 1990
• 6: Mark D Hill, Aspects of Cache Memory and Instruction, University of California at Berkeley, Berkeley, CA, 1987
• 7: 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]
• 8: W. W. Hwu , P. P. Chang, Achieving high instruction cache performance with an optimizing compiler, Proceedings of the 16th annual international symposium on Computer architecture, p.242-251, April 1989, Jerusalem, Israel
• 9: W. W. Hwu and T. M. Conte. The susceptibility of programs to context switching. Technical Report CRHC- 91-14, Center for Reliable and High-Performance Computing, University of Illinois, Urbana, April 1991.
• 10: Norman P. Jouppi, Improving direct-mapped cache performance by the addition of a small fully-associative cache and prefetch buffers, Proceedings of the 17th annual international symposium on Computer Architecture, p.364-373, May 28-31, 1990, Seattle, Washington, United States
• 11: 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
• 12: R. L. Mattson, J. Gecsei, D. R. Slutz, and I. L. Traiger. Evaluation techniques for storage hierarchies. IBM Systems Journal, 9(2):78-117, 1970.
• 13: Scott Arthur McFarling, Program analysis and optimization for machines with instruction cache, Stanford University, Stanford, CA, 1992
• 14: S. McFarling, Program optimization for instruction caches, Proceedings of the third international conference on Architectural support for programming languages and operating systems, p.183-191, April 03-06, 1989, Boston, Massachusetts, United States
• 15: Trevor N. Mudge , Richard B. Brown , William P. Birmingham , Jeffrey A. Dykstra , Ayman I. Kayssi , Ronald J. Lomax , Oyekunle A. Olukotun , Karem A. Sakallah , Raymond A. Milano, The Design of a Microsupercomputer, Computer, v.24 n.1, p.57-64, January 1991
• 16: F. Olken. Efficient methods for calculating the success function of fixed space replacement policies. Technical Report LBL-12370, Lawrence Berkeley Laboratory, 1981.
• 17: 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]
• 18: Harold S. Stone, High-performance computer architecture, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1987
• 19: R. A. Sugumar and S. G. Abraham. Efficient simulation of multiple cache configurations using binomial trees. Technical Report CSE-TR-111-91, CSE Division, University of Michigan, 1991.
• 20: R. A. Suguma~ and S. G. Abraham. Efficient simulation of caches under optimal replacement with applications to miss characterization. Technical Report CSE-TR- 143-92, CSE Division, University of Michigan, 1992.
• 21: Dominique Thiébaut, On the Fractal Dimension of Computer Programs and its Application to the Prediction of the Cache Miss Ratio, IEEE Transactions on Computers, v.38 n.7, p.1012-1026, July 1989 [doi>10.1109/12.30852]
• 22: James Gordon Thompson , Alan Jay Smith, Efficient analysis of caching systems, 1987

INDEX TERMS

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

Additional Classification:
  B. Hardware
  B.3 MEMORY STRUCTURES
      B.3.3 Performance Analysis and Design Aids**
          Subjects: Simulation**

  F. Theory of Computation
  F.2 ANALYSIS OF ALGORITHMS AND PROBLEM COMPLEXITY
      F.2.2 Nonnumerical Algorithms and Problems
          Subjects: Computations on discrete structures

  G. Mathematics of Computing
  G.2 DISCRETE MATHEMATICS
      G.2.2 Graph Theory
          Subjects: Graph algorithms

General Terms:
Algorithms, Design, Performance