Footprints in the cache

ABSTRACT

This paper develops an analytical model for cache-reload transients and compares the model to observations based on several address traces. The cache-reload transient is the set of cache misses that occur when a process is reinitiated after being suspended temporarily. For example, an interrupt program that runs periodically experiences a reload transient at each initiation. The reload transient depends on the cache size and on the sizes of the footprints in the cache of the competing programs, where a program footprint is defined to be the set of lines in the cache in active use by the program. The model shows that the size of the transient is related to the normal distribution function. A simulation based on program-address traces shows excellent agreement between the model and the observations.

REFERENCES

• 1: 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]
• 2: EASTON, M. C. Computation of cold-start miss ratios. IEEE Trans. Comput. C-27, 5 (May 1978), 404-408.
• 3: Ronald Fagin , Malcolm C. Easton, The independence of miss ratio on page size, Journal of the ACM (JACM), v.23 n.1, p.128-146, Jan. 1976 [doi>10.1145/321921.321935]
• 4: FENWICK, P.M. Some aspects of the dynamic behavior of hierarchical memories. IEEE Trans. Comput. C-34, 6 (June 1985), 570-573.
• 5: GECSEI, J. Determining hit ratios for multilevel hierarchies, IBM J. Res. Dev. 18, 7 (July 1974), 316-327.
• 6: Kai Hwang , Faye A. Briggs, Computer Architecture and Parallel Processing, McGraw-Hill, Inc., New York, NY, 1990
• 7: Thomas Roberts Puzak, Analysis of cache replacement-algorithms, 1985
• 8: SATYANARAYANAN, M., AND BHANDARKAR, D. Design trade-offs in VAX-11 translation buffer organization. Computer 14, 12 (Dec. 1981), 103-111.
• 9: D. R. Slutz , I. L. Traiger, A note on the calculation of average working set size, Communications of the ACM, v.17 n.10, p.563-565, Oct. 1974 [doi>10.1145/355620.361167]
• 10: 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.
• 11: Alan Jay Smith, Cache Memories, ACM Computing Surveys (CSUR), v.14 n.3, p.473-530, Sept. 1982 [doi>10.1145/356887.356892]
• 12: 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
• 13: 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]
• 14: VOLDMAN, J., AND HOEVEL, L. W. The software-cache connection. IBM J. Res. Dev. 25, 6 {Nov. 1981), 877-893.
• 15: VOLDMAN, J., MANDELBROT, S., HOEVEL, L., KNIGHT, J. AND ROSENFELD, P. Fractal nature of software-cache interaction. IBM J. Res. Dev. 27, 2 (Mar. 1983) 164-170.

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**

  C. Computer Systems Organization
  C.4 PERFORMANCE OF SYSTEMS
      Subjects: Modeling techniques

  D. Software
  D.4 OPERATING SYSTEMS
      D.4.1 Process Management
          Subjects: Multiprocessing/multiprogramming/multitasking
      D.4.2 Storage Management
          Subjects: Swapping**

General Terms:
Design, Experimentation, Performance, Theory