Cache performance of operating system and multiprogramming workloads

ABSTRACT

Large caches are necessary in current high-performance computer systems to provide the required high memory bandwidth. Because a small decrease in cache performance can result in significant system performance degradation, accurately characterizing the performance of large caches is important. Although measurements on actual systems have shown that operating systems and multiprogramming can affect cache performance, previous studies have not focused on these effects. We have developed a program tracing technique called ATUM (Address Tracing Using Microcode) that captures realistic traces of multitasking workloads including the operating system. Examining cache behavior using these traces from a VAX processor shows that both the operating system and multiprogramming activity significantly degrade cache performance, with an even greater proportional impact on large caches. From a careful analysis of the causes of this degradation, we explore various techniques to reduce this loss. While seemingly little can be done to mitigate the effect of system references, multitasking cache miss activity can be substantially reduced with small hardware additions.

REFERENCES

• 1: A. Agarwal, Analysis of cache performance for operating systems and multiprogramming, Stanford University, Stanford, CA, 1987
• 2: AGARWAL, A., CHOW, P., HOROWITZ, M., ACKEN, J., SALZ, A., AND HENNESSY, J. On-chip instruction caches for high performance processors. In Proceedings of the Conference on Advanced Research in VLSI (Stanford, Cal., March 1987). MIT Press, Boston, Mass, 1987, pp. 1-24.
• 3: AGARWAL, i., HOROWITZ, M., AND HENNESSY, J. An analytical cache model. Computer Systems Lab. Rep. 86-304, Stanford Univ., Sept. 1986.
• 4: 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
• 5: Cedell Alexander , William Keshlear , Furrokh Cooper , Faye Briggs, Cache memory performance in a unix enviroment, ACM SIGARCH Computer Architecture News, v.14 n.3, p.41-61, June 1 1986 [doi>10.1145/381711.381717]
• 6: James Cho , Alan J Smith , Howard Sachs, The Memory Architecture and the Cache and Memory Management Unit for, University of California at Berkeley, Berkeley, CA, 1986
• 7: 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]
• 8: Douglas W. Clark , Joel S. Emer, Performance of the VAX-11/780 translation buffer: simulation and measurement, ACM Transactions on Computer Systems (TOCS), v.3 n.1, p.31-62, Feb. 1985 [doi>10.1145/214451.214455]
• 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: EASTON, M. C. Computation of cold-start miss ratios. IEEE Trans. Comput. C-27, 5 (May 1978).
• 11: 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]
• 12: Fu, J., KELLER, J. B., AND HADUCH, K.J. Aspects of the VAX 8800 C box design. Digital Tech. J. 4 (Feb. 1987), 41-51.
• 13: GOODMAN, J. R. Cache memory optimization to reduce processor/memory traffic. Dept. of Computer Sciences, Univ. of Wisconsin-Madison, 1985.
• 14: 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
• 15: HENNESSY, J.L. VLSI processor architecture. IEEE Trans. Comput. C-33, 12 (Dec. 1984).
• 16: Mark Hill , Susan Eggers , Jim Larus , George Taylor , Glenn Adams , B. K. Bose , Garth Gibson , Paul Hansen , Jon Keller , Shing Kong , Corinna Lee , Daebum Lee , Joan Pendleton , Scott Ritchie , David Wood , Ben Zorn , Paul Hilfinger , Dave Hodges , Randy Katz , John Ousterhout , Dave Patterson, Design decisions in SPUR, Computer, v.19 n.11, p.8-22, Nov. 1986 [doi>10.1109/MC.1986.1663096]
• 17: HOROWITZ, M., AND CHOW, P. The MIPS-X microprocessor. In Proceedings o{ IEEE WESCON 85 (San Francisco, 1985). IEEE, New York, 1985.
• 18: KAPLAN, K. R., AND WINDER, R. O. Cache-based computer systems. Comput. 6, 3 (March 1973), 30-36.
• 19: Makoto Kobayashi, An empirical study of task switching locality in MVS, IEEE Transactions on Computers, v.35 n.8, p.720-731, Aug. 1986 [doi>10.1109/TC.1986.1676823]
• 20: LAHA, S., PATEL, J. H., AND IYER, R.K. Accurate low-cost methods for performance evaluation of cache memory systems. Coordinated Science Laboratory, Univ. of Illinois, 1986.
• 21: MOUSSOURIS, J. ET AL. A CMOS RISC processor with integrated system functions. In COMP- CON (San Francisco, Mar. 1986). IEEE, New York, March 1986, pp. 126-131.
• 22: PA~'rERSON, D. A., AND SEQUIN, C.H. Design considerations for single-chip computers of the future. IEEE Trans. Comput. C-29, 2 (Feb. 1980), 108-116.
• 23: Bernard L. Peuto , Leonard J. Shustek, An instruction timing model of CPU performance, Proceedings of the 4th annual symposium on Computer architecture, p.165-178, March 23-25, 1977
• 24: George Radin, The 801 minicomputer, Proceedings of the first international symposium on Architectural support for programming languages and operating systems, p.39-47, March 01-03, 1982, Palo Alto, California, United States
• 25: Arturo Salz , Anant Agarwal , Paul Chow, MIPS-X: the external interface, Stanford University, Stanford, CA, 1987
• 26: R. L. Sites , A. Agarwal, Multiprocessor cache analysis using ATUM, Proceedings of the 15th Annual International Symposium on Computer architecture, p.186-195, May 30-June 02, 1988, Honolulu, Hawaii, United States
• 27: Alan Jay Smith, Cache Memories, ACM Computing Surveys (CSUR), v.14 n.3, p.473-530, Sept. 1982 [doi>10.1145/356887.356892]
• 28: Alan Jay Smith, Cache evaluation and the impact of workload choice, Proceedings of the 12th annual international symposium on Computer architecture, p.64-73, June 17-19, 1985, Boston, Massachusetts, United States
• 29: 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
• 30: WILLIAM D. STRECKER, Cache memories for PDP-11 family computers, Proceedings of the 3rd annual symposium on Computer architecture, p.155-158, January 19-21, 1976
• 31: 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]
• 32: Shreekant S Thakkar , Alan E Knowles, A high-performance memory management scheme, Computer, v.19 n.5, p.8-22, May 1986
• 33: Vax-11 Architecture Reference Manual. Form EK-VARAR-RM-001, Digital Equipment Corp., Bedford, Mass., 1982.

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.2 Design Styles
          Subjects: Virtual memory; Associative memories
      B.3.3 Performance Analysis and Design Aids**
          Subjects: Simulation**; Formal models**

  C. Computer Systems Organization
  C.4 PERFORMANCE OF SYSTEMS
      Subjects: Modeling techniques; Design studies; Measurement techniques

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

General Terms:
Design, Measurement, Performance