Cache miss behavior: is it √2?

ABSTRACT

It has long been empirically observed that the cache miss rate decreased as a power law of cache size, where the power was approximately -1/2. In this paper, we examine the dependence of the cache miss rate on cache size both theoretically and through simulation. By combining the observed time dependence of the cache reference pattern with a statistical treatment of cache entry replacement, we predict that the cache miss rate should vary with cache size as an inverse power law for a first level cache. The exponent in the power law is directly related to the time dependence of cache references, and lies between -0.3 to -0.7. Results are presented for both direct mapped and set associative caches, and for various levels of the cache hierarchy. Our results demonstrate that the dependence of cache miss rate on cache size arises from the temporal dependence of the cache access pattern.

REFERENCES

• 1: R. Kalla, B.Sinharoy, and J. Tendler. "IBM Power5 Chip: A dual-core multi-threaded processor", IEEE Micro 24(2), 40-47, 2004.
• 2: D. Boggs et al. "The microarchitecture of the Intel Pentium 4 processor on 90 nm technology", Intel Technology Journal 8, Issue 1, 1997.
• 3: http://www.amd.com, Technical Documentation. "AMD Opteron Product Data Sheet", Publication number 23932, 2004.
• 4: http://www.sun.com/processors/manuals/USIV_v1.0.pdf. "UltraSPARC IV Processor", User's Manual Supplement, Version 1.0, 2004.
• 5: C. K. Chow. "On Optimization of Storage Hierarchies", IBM Journal of R & D 18, 194--203, 1974.
• 6: C. K. Chow. "Determination of Cache's Capacity and its Matching Storage Hierarchy", IEEE Transactions on Computers, c-25, 157--164, 1976.
• 7: John S. Harper , Darren J. Kerbyson , Graham R. Nudd, Efficient Analytical Modelling of Multi-Level Set-Associative Caches, Proceedings of the 7th International Conference on High-Performance Computing and Networking, p.473-482, April 12-14, 1999
• 8: S. Prybylski , M. Horowitz , J. Hennessy, Performance tradeoffs in cache design, Proceedings of the 15th Annual International Symposium on Computer architecture, p.290-298, May 30-June 02, 1988, Honolulu, Hawaii, United States
• 9: S. Przybylski , M. Horowitz , J. Hennessy, Characteristics of performance-optimal multi-level cache hierarchies, Proceedings of the 16th annual international symposium on Computer architecture, p.114-121, April 1989, Jerusalem, Israel
• 10: Gururaj S. Rao, Performance Analysis of Cache Memories, Journal of the ACM (JACM), v.25 n.3, p.378-395, July 1978 [doi>10.1145/322077.322081]
• 11: Jerome H. Saltzer, A simple linear model of demand paging performance, Communications of the ACM, v.17 n.4, p.181-186, April 1974 [doi>10.1145/360924.360926]
• 12: Alan Jay Smith, Cache Memories, ACM Computing Surveys (CSUR), v.14 n.3, p.473-530, Sept. 1982 [doi>10.1145/356887.356892]
• 13: M. H. Macdougall. "Instruction-level Program and Processor Modeling", Computer 7, 14--24, 1984.
• 14: Jaswinder Pal Singh , Harold S. Stone , Dominique F. Thiébaut, A Model of Workloads and its Use in Miss-Rate Prediction for Fully Associative Caches, IEEE Transactions on Computers, v.41 n.7, p.811-825, July 1992 [doi>10.1109/12.256450]
• 15: A. Hartstein , Thomas R. Puzak, Optimum Power/Performance Pipeline Depth, Proceedings of the 36th annual IEEE/ACM International Symposium on Microarchitecture, p.117, December 03-05, 2003
• 16: Joel L. Wolf , Harold S. Stone , Dominique Thiébaut, Synthetic Traces for Trace-Driven Simulation of Cache Memories, IEEE Transactions on Computers, v.41 n.4, p.388-410, April 1992 [doi>10.1109/12.135552]

INDEX TERMS

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

Additional Classification:
  B. Hardware
  B.3 MEMORY STRUCTURES
      B.3.2 Design Styles
          Subjects: Cache memories; Mass storage (e.g., magnetic, optical, RAID); Virtual memory; Shared memory; Primary memory

General Terms:
Algorithms, Design, Measurement, Performance

Keywords:
cache organization, memory hierarchy, performance