An analytical cache model

ABSTRACT

Trace-driven simulation and hardware measurement are the techniques most often used to obtain accurate performance figures for caches. The former requires a large amount of simulation time to evaluate each cache configuration while the latter is restricted to measurements of existing caches. An analytical cache model that uses parameters extracted from address traces of programs can efficiently provide estimates of cache performance and show the effects of varying cache parameters. By representing the factors that affect cache performance, we develop an analytical model that gives miss rates for a given trace as a function of cache size, degree of associativity, block size, subblock size, multiprogramming level, task switch interval, and observation interval. The predicted values closely approximate the results of trace-driven simulations, while requiring only a small fraction of the computation cost.

REFERENCES

• 1: Anant Agarwal, Trace compaction using cache filtering with blocking, Stanford University, Stanford, CA, 1987
• 2: AGARWAL, A., HOROWITZ, M., AND HENNESSY, J. An analytical cache model. Computer Systems Lab. Rep. TR 86-304, Stanford Univ. Stanford, Calif., Sept. 1986.
• 3: A. Agarwal , R. L. Sites , M. Horowitz, ATUM: a new technique for capturing address traces using microcode, Proceedings of the 13th annual international symposium on Computer architecture, p.119-127, June 02-05, 1986, Tokyo, Japan
• 4: Alfred V. Aho , Peter J. Denning , Jeffrey D. Ullman, Principles of Optimal Page Replacement, Journal of the ACM (JACM), v.18 n.1, p.80-93, Jan. 1971 [doi>10.1145/321623.321632]
• 5: ALPERT, D. Performance tradeoffs for microprocessor cache memories. Computer Systems Lab. Rep. TR 83-239, Stanford Univ., Stanford, Calif., Dec. 1983.
• 6: D. R. Cheriton , G. A. Slavenburg , P. D. Boyle, Software-controlled caches in the VMP multiprocessor, Proceedings of the 13th annual international symposium on Computer architecture, p.366-374, June 02-05, 1986, Tokyo, Japan
• 7: CHOW, C.K. Determining the optimum capacity of a cache memory. IBM Tech. Disclosure Bull. I7, 10 (Mar. 1975), 3163-3166.
• 8: Douglas W. Clark, Cache Performance in the VAX-11/780, ACM Transactions on Computer Systems (TOCS), v.1 n.1, p.24-37, Feb. 1983 [doi>10.1145/357353.357356]
• 9: Peter J. Denning, The working set model for program behavior, Communications of the ACM, v.11 n.5, p.323-333, May 1968 [doi>10.1145/363095.363141]
• 10: Malcolm C. Easton , Ronald Fagin, Cold-start vs. warm-start miss ratios, Communications of the ACM, v.21 n.10, p.866-872, Oct. 1978 [doi>10.1145/359619.359634]
• 11: EASTON, M. C. Computation of cold-start miss ratios. IEEE Trans. Comput. C-27, 5 (May 1978).
• 12: James R. Goodman, Using cache memory to reduce processor-memory traffic, Proceedings of the 10th annual international symposium on Computer architecture, p.124-131, June 13-17, 1983, Stockholm, Sweden
• 13: Ilkka J. Haikala, Cache hit ratios with geometric task switch intervals, Proceedings of the 11th annual international symposium on Computer architecture, p.364-371, January 1984
• 14: Mark D. Hill , Alan Jay Smith, Experimental evaluation of on-chip microprocessor cache memories, Proceedings of the 11th annual international symposium on Computer architecture, p.158-166, January 1984
• 15: KUMAR, B. A model of spatial locality and its application to cache design. Unpublished Report, Computer Systems Lab., Stanford Univ., Stanford, Calif., 1979.
• 16: Edward D. Lazowska , John Zahorjan , G. Scott Graham , Kenneth C. Sevcik, Quantitative system performance: computer system analysis using queueing network models, Prentice-Hall, Inc., Upper Saddle River, NJ, 1984
• 17: MATTSON, R. L., GECSEI, J., SLUTZ, D. R., AND TRAIGER, I. L. Evaluation techniques for storage hierarchies. IBM Syst. J. 9, 2 (1970), 78-117.
• 18: 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]
• 19: B. R Rau, Sequential prefetch strategies for instructions and data, Stanford University, Stanford, CA, 1977
• 20: 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]
• 21: SMITH, A.J. A comparative study of set associative memory mapping algorithms and their use for cache and main memory. IEEE Trans. Softw. Eng. SE-4, 2 (Mar. 1978), 121-130.
• 22: Alan Jay Smith, Cache Memories, ACM Computing Surveys (CSUR), v.14 n.3, p.473-530, Sept. 1982 [doi>10.1145/356887.356892]
• 23: James E. Smith , James R. Goodman, A study of instruction cache organizations and replacement policies, Proceedings of the 10th annual international symposium on Computer architecture, p.132-137, June 13-17, 1983, Stockholm, Sweden
• 24: Jeffrey R. Spirn, Program Behavior: Models and Measurements, Elsevier Science Inc., New York, NY, 1977
• 25: Harold S. Stone , Dominique Thibaut, Footprints in the cache, Proceedings of the 1986 ACM SIGMETRICS joint international conference on Computer performance modelling, measurement and evaluation, p.4-8, May 1986, Raleigh, North Carolina, United States
• 26: William D. Strecker, Transient behavior of cache memories, ACM Transactions on Computer Systems (TOCS), v.1 n.4, p.281-293, Nov. 1983 [doi>10.1145/357377.357379]

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: Formal models**; Simulation**

  D. Software
  D.4 OPERATING SYSTEMS
      D.4.1 Process Management
          Subjects: Multiprocessing/multiprogramming/multitasking

General Terms:
Design, Measurement, Performance, Theory