Cold-start vs. warm-start miss ratios

ABSTRACT

In a two-level computer storage hierarchy, miss ratio measurements are often made from a “cold start”, that is, made with the first-level store initially empty. For large capacities the effect on the measured miss ratio of the misses incurred while filling the first-level store can be significant, even for long reference strings. Use of “warm-start” rather than “cold-start” miss ratios cast doubt on the widespread belief that the observed “S-shape” of lifetime (reciprocal of miss ratio) versus capacity curve indicates a property of behavior of programs that maintain a constant number of pages in main storage. On the other hand, if cold-start miss ratios are measured as a function of capacity and measurement length, then they are useful in studying systems in which operation of a program is periodically interrupted by task switches. It is shown how to obtain, under simple assumptions, the cache miss ratio for multiprogramming from cold-start miss ratio values and how to obtain approximate cold-start miss ratios from warm-start miss ratios.

REFERENCES

• 1: L. A. Belady , C. J. Kuehner, Dynamic space-sharing in computer systems, Communications of the ACM, v.12 n.5, p.282-288, May 1969 [doi>10.1145/362946.363002]
• 2: Edward G. Coffman, Jr. , Peter J. Denning, Operating Systems Theory, Prentice Hall Professional Technical Reference, 1973
• 3: Chamberlin, D.D., Fuller, S.H., and Liu, L.Y. An analysis of page allocation strategies for multiprogramming systems with virtual memory. IBM J. Res. Develop. 17 (Sept. 1973), 404-412.
• 4: Chu, W.W., and Opderbeck, H. Performance of replacement algorithms with different page sizes. Computer 7,11 (Nov. 1974), 14-21.
• 5: Doob, J.L. Stochastic Processes. Wiley, New York, 1953.
• 6: Denning, P.J., and Graham, G.S. Multiprogrammed memory management. IEEE Proc. Interactive Computer Systems, 63 (June 1975), pp. 924-939.
• 7: Peter J. Denning , Kevin C. Kahn, A study of program locality and lifetime functions, Proceedings of the fifth ACM symposium on Operating systems principles, p.207-216, November 19-21, 1975, Austin, Texas, United States
• 8: Easton, M.C. Computation of cold-start miss ratios. IEEE Trans. Comptrs. C-27, 5 (May 1978), 404-408.
• 9: Easton, M.C., and Fagin, R. Cold-start vs. warm-start miss ratios and multiprogramming performance. IBM Res. Rep. RC 5715, IBM T.J. Watson Res. Ctr., Yorktown Heights, N.Y., Nov. 1975.
• 10: Fagin, R. Asymptotic miss ratios over independent references. J. Computer Syst. Sci. 14, 2 (April 1977), 222-250.
• 11: 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]
• 12: Ghanem, M.Z. Study of memory partitioning for multiprogramming systems with virtual memory. IBM Z Res. Develop. 19, 5 (Sept. 1975), 451-457.
• 13: Ghanem, M.Z. Experimental study on the behavior of programs. IBM Res. Rep. RC 5460, IBM T.J. Watson Res. Ctr., Yorktown Heights, N.Y., June 1975.
• 14: Ghanem, M.Z. Personal communication.
• 15: Hardy, G.H., Littlewood, J.E., and Polya, G. Inequalities. Cambridge U. Press, London, 1964.
• 16: Kaplan, K.R., and Winder, R.O. Cache-based computer systems. Computer 6, 3 (March 1973), 30-36.
• 17: Shedler, G.S., and Tung, C. Locality in page reference strings. SIAM J. Comptng. 1, 3 (Sept. 1972), 218-241.

INDEX TERMS

Primary Classification:
  D. Software
  D.4 OPERATING SYSTEMS

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

General Terms:
Design, Performance, Theory

Keywords:
S-shape, cold start, lifetime function, miss ratio, multiprogramming, storage hierarchy, warm start