Instruction fetching: coping with code bloat

ABSTRACT

Previous research has shown that the SPEC benchmarks achieve low miss ratios in relatively small instruction caches. This paper presents evidence that current software-development practices produce applications that exhibit substantially higher instruction-cache miss ratios than do the SPEC benchmarks. To represent these trends, we have assembled a collection of applications, called the Instruction Benchmark Suite (IBS), that provides a better test of instruction-cache performance. We discuss the rationale behind the design of IBS and characterize its behavior relative to the SPEC benchmark suite. Our analysis is based on trace-driven and trap-driven simulations and takes into full account both the application and operating-system components of the workloads.This paper then reexamines a collection of previously-proposed hardware mechanisms for improving instruction-fetch performance in the context of the IBS workloads. We study the impact of cache organization, transfer bandwidth, prefetching, and pipelined memory systems on machines that rely on the use of relatively small primary instruction caches to facilitate increased clock rates. We find that, although of little use for SPEC, the right combination of these techniques substantially benefits IBS. Even so, under IBS, a stubborn lower bound on the instruction-fetch CPI remains as an obstacle to improving overall processor performance.

REFERENCES

• Accetta86: Accetta, M., Baron, R., Golub, D., Rashid, R., Tevanian, A. and Young, M. Mach: A new kernel foundation for UN1X development, In the Summer 1986 USENIX Conference.
• Alexander85: Cedell A. Alexander , William M. Keshlear , Faye Briggs, Translation buffer performance in a UNIX enviroment, ACM SIGARCH Computer Architecture News, v.13 n.5, p.2-14, Dec 1 1985 [doi>10.1145/381757.381758]
• Alexander86: 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]
• Agarwal88: Anant Agarwal , John Hennessy , Mark Horowitz, Cache performance of operating system and multiprogramming workloads, ACM Transactions on Computer Systems (TOCS), v.6 n.4, p.393-431, Nov. 1988 [doi>10.1145/48012.48037]
• Baer87: Baer, J.-L. and Wang, W.-H. Architectural choices for multi-level cache hierarchies. In the 16th International Conference on Parallel Processing: 258-261, 1987.
• Baer88: J.-L. Baer , W.-H. Wang, On the inclusion properties for multi-level cache hierarchies, Proceedings of the 15th Annual International Symposium on Computer architecture, p.73-80, May 30-June 02, 1988, Honolulu, Hawaii, United States
• Bershad94: Brian N. Bershad , Dennis Lee , Theodore H. Romer , J. Bradley Chen, Avoiding conflict misses dynamically in large direct-mapped caches, Proceedings of the sixth international conference on Architectural support for programming languages and operating systems, p.158-170, October 05-07, 1994, San Jose, California, United States
• Bomberger92: Allen C. Bomberger , William S. Frantz , Ann C. Hardy , Norman Hardy , Charles R. Landau , Jonathan S. Shapiro, The KeyKOS Nanokernel Architecture, Proceedings of the Workshop on Micro-kernels and Other Kernel Architectures, p.95-112, April 27-28, 1992
• Borg90: Borg, A., Kessler, R. and Wall, D. Generation and analysis of very long address traces, In the 17th ISCA, Seattle, WA, 1990.
• Bray90: Brian K. Bray , William L. Lunch , Michael J. Flynn, Page allocation to reduce access time of physical caches, Stanford University, Stanford, CA, 1990
• Brunner91: Richard A. Brunner, VAX architecture reference manual (2nd ed.), Digital Press, Newton, MA, 1991
• Budd91: Timothy Budd, An introduction to object-oriented programming, Addison Wesley Longman Publishing Co., Inc., Redwood City, CA, 1991
• Calder94: Calder, B., Grunwald, D. and Zorn, B. Quantifying behavioral differences between C and C++ programs. The Department of Computer Science, University of Colorado. CU- CS-698-94.1994.
• Chen93: J. Bradley Chen , Brian N. Bershad, The impact of operating system structure on memory system performance, Proceedings of the fourteenth ACM symposium on Operating systems principles, p.120-133, December 05-08, 1993, Asheville, North Carolina, United States
• Chen94: Chen, B. Memory behavior of an Xll window system, In the USENIX Winter 1994 Technical Conference, 1994.
• Cheriton84: Cheriton, D. R. The V kernel: A software base for distributed systems. IEEE Software 1 (2): 19-42, 1984.
• Clark83: 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]
• Clark85: 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]
• Clark88: D. W. Clark , P. J. Bannon , J. B. Keller, Measuring VAX 8800 performance with a histogram hardware monitor, Proceedings of the 15th Annual International Symposium on Computer architecture, p.176-185, May 30-June 02, 1988, Honolulu, Hawaii, United States
• Cmelik94: Bob Cmelik , David Keppel, Shade: a fast instruction-set simulator for execution profiling, Proceedings of the 1994 ACM SIGMETRICS conference on Measurement and modeling of computer systems, p.128-137, May 16-20, 1994, Nashville, Tennessee, United States
• Custer93: Helen Custer, Inside Windows NT, Microcomputer Applications, Suisun City, CA, 1992
• Cvetanovic94: Z. Cvetanovic , D. Bhandarkar, Characterization of alpha AXP performance using TP and SPEC workloads, Proceedings of the 21ST annual international symposium on Computer architecture, p.60-70, April 18-21, 1994, Chicago, Illinois, United States
• Emer84: Joel S. Emer , Douglas W. Clark, A Characterization of Processor Performance in the vax-11/780, Proceedings of the 11th annual international symposium on Computer architecture, p.301-310, January 1984
• Farrens89: M. K. Farrens , a. R. Pleszkun, Improving performance of small on-chip instruction caches, Proceedings of the 16th annual international symposium on Computer architecture, p.234-241, April 1989, Jerusalem, Israel
• Flanagan93: Flanagan, J. K., Nelson, B. E. and Archibald, J. K. The inaccuracy of trace-driven simulation using incomplete trace data. Brigham Young University. 1993.
• Gee93: Jeffrey D. Gee , Mark D. Hill , Dionisios N. Pnevmatikatos , Alan Jay Smith, Cache Performance of the SPEC92 Benchmark Suite, IEEE Micro, v.13 n.4, p.17-27, July 1993 [doi>10.1109/40.229711]
• Happel92: Happel, L. P. and Jayasumana, A. P. Perfomtance of a RISC machine with two-level caches. IEE Proceedings-E 139 (3): 221-229, 1992.
• Hennessy90: David A. Patterson , John L. Hennessy, Computer architecture: a quantitative approach, Morgan Kaufmann Publishers Inc., San Francisco, CA, 1990
• Hill87: Hill, M. Aspects of cache memory and instruction buffer performance. The University of California at Berkeley. 1987.
• Huck93: Jerry Huck , Jim Hays, Architectural support for translation table management in large address space machines, Proceedings of the 20th annual international symposium on Computer architecture, p.39-50, May 16-19, 1993, San Diego, California, United States
• Hwu89: W. W. Hwu , P. P. Chang, Achieving high instruction cache performance with an optimizing compiler, Proceedings of the 16th annual international symposium on Computer architecture, p.242-251, April 1989, Jerusalem, Israel
• Jouppi90: Norman P. Jouppi, Improving direct-mapped cache performance by the addition of a small fully-associative cache and prefetch buffers, Proceedings of the 17th annual international symposium on Computer Architecture, p.364-373, May 28-31, 1990, Seattle, Washington, United States
• Jouppi94: N. P. Jouppi , S. J. E. Wilton, Tradeoffs in two-level on-chip caching, Proceedings of the 21ST annual international symposium on Computer architecture, p.34-45, April 18-21, 1994, Chicago, Illinois, United States
• Koch94: Koch, P. Emulating the 68040 in the PowerPC Macintosh, In Microprocessor Forum, San Francisco, CA, 1994.
• Kessler91: Kessler, R. Analysis of multi-megabyte secondary CPU cache memories. University of Wisconsin-Madison. 1991.
• Kessler92: R. E. Kessler , Mark D. Hill, Page placement algorithms for large real-indexed caches, ACM Transactions on Computer Systems (TOCS), v.10 n.4, p.338-359, Nov. 1992 [doi>10.1145/138873.138876]
• Malan91: Malan, G., Rashid, R., Golub, D. and Baron, R. DOS as a Mach 3.0 application, In the USENIX Mach Symposium, 27- 40, 1991.
• Maynard94: Ann Marie Grizzaffi Maynard , Colette M. Donnelly , Bret R. Olszewski, Contrasting characteristics and cache performance of technical and multi-user commercial workloads, Proceedings of the sixth international conference on Architectural support for programming languages and operating systems, p.145-156, October 05-07, 1994, San Jose, California, United States
• McFarling89: S. McFarling, Program optimization for instruction caches, Proceedings of the third international conference on Architectural support for programming languages and operating systems, p.183-191, April 03-06, 1989, Boston, Massachusetts, United States
• Mogul91: Jeffrey C. Mogul , Anita Borg, The effect of context switches on cache performance, Proceedings of the fourth international conference on Architectural support for programming languages and operating systems, p.75-84, April 08-11, 1991, Santa Clara, California, United States
• MReport92–95: Microprocessor Report. Sebastopol, CA, MicroDesign Resources, 1992, 1993, 1994 and 1995.
• Mulder91: Mulder, J., Quach, N. and Flynn, M. An area model for on-chip memories and its application. IEEE Journal of Solid- State Circuits 26 (2): 98-106, 1991.
• Nagle92: Nagle, D., Uhlig, R., Mudge, T., Monster: a tool for analyzing the interaction between operating systems and architectures. CSE-TR147-92. University of Michigan, 1992.
• Nagle93: David Nagle , Richard Uhlig , Tim Stanley , Stuart Sechrest , Trevor Mudge , Richard Brown, Design tradeoffs for software-managed TLBs, Proceedings of the 20th annual international symposium on Computer architecture, p.27-38, May 16-19, 1993, San Diego, California, United States
• Nagle94: D. Nagle , R. Uhlig , T. Mudge , S. Sechrest, Optimal allocation of on-chip memory for multiple-API operating systems, Proceedings of the 21ST annual international symposium on Computer architecture, p.358-369, April 18-21, 1994, Chicago, Illinois, United States
• Olukotun91: O. A. Olukotun , T. N. Mudge , R. B. Brown, Implementing a cache for a high-performance GaAs microprocessor, Proceedings of the 18th annual international symposium on Computer architecture, p.138-147, May 27-30, 1991, Toronto, Ontario, Canada
• Olukotun92: Kunle Olukotun , Trevor Mudge , Richard Brown, Performance optimization of pipelined primary cache, Proceedings of the 19th annual international symposium on Computer architecture, p.181-190, May 19-21, 1992, Queensland, Australia
• Ousterhout94: John K. Ousterhout, Tcl and the Tk toolkit, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1994
• Palcharla94: S. Palacharla , R. E. Kessler, Evaluating stream buffers as a secondary cache replacement, Proceedings of the 21ST annual international symposium on Computer architecture, p.24-33, April 18-21, 1994, Chicago, Illinois, United States
• Patel92: Patel, K., Smith, B. C. and Rowe, L. A. Performance of a Software MPEG Video Decoder. University of California, Berkeley. 1992.
• Pierce95: James Edward Pierce, Cache behavior in the presence of speculative execution: the benefits of misprediction, University of Michigan, Ann Arbor, MI, 1995
• Przybylski89: 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
• Przybylski90: Steven Przybylski, The performance impact of block sizes and fetch strategies, Proceedings of the 17th annual international symposium on Computer Architecture, p.160-169, May 28-31, 1990, Seattle, Washington, United States
• Rozier92: Marc Rozier, Chorus, Proceedings of the Workshop on Micro-kernels and Other Kernel Architectures, p.39-70, April 27-28, 1992
• Scheifler86: Robert W. Scheifler , Jim Gettys, The X window system, ACM Transactions on Graphics (TOG), v.5 n.2, p.79-109, April 1986 [doi>10.1145/22949.24053]
• Short88: R. T. Short , H. M. Levy, A simulation study of two-level caches, Proceedings of the 15th Annual International Symposium on Computer architecture, p.81-88, May 30-June 02, 1988, Honolulu, Hawaii, United States
• Sites88: 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
• Sites92: Sites, R., Chernoff, A., Kirk, M., Marks, M. and Robinson, S. Binary translation. Digital Technical Journal 4 (4): 137- 152, 1992.
• Smith78: Smith, A. J. Sequential program prefetching in memory hierarchies. IEEE Computer 11 (12): 7-21, 1978.
• Smith82: Alan Jay Smith, Cache Memories, ACM Computing Surveys (CSUR), v.14 n.3, p.473-530, Sept. 1982 [doi>10.1145/356887.356892]
• Smith85: 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
• Smith92: J. E. Smith , W.-C. Hsu, Prefetching in supercomputer instruction caches, Proceedings of the 1992 ACM/IEEE conference on Supercomputing, p.588-597, November 16-20, 1992, Minneapolis, Minnesota, United States
• SPEC91: SPEC. The SPEC Benchmark Suite. SPEC Newsletter. 3: 3-4, 1991. -
• SPEC93: SPEC. SPEC: A five year retrospective. The SPEC Newsletter 5 (4): 1-4, 1993.
• Taylor90: George Taylor , Peter Davies , Michael Farmwald, The TLB slice—a low-cost high-speed address translation mechanism, Proceedings of the 17th annual international symposium on Computer Architecture, p.355-363, May 28-31, 1990, Seattle, Washington, United States
• Torrellas92: Josep Torrellas , Anoop Gupta , John Hennessy, Characterizing the caching and synchronization performance of a multiprocessor operating system, Proceedings of the fifth international conference on Architectural support for programming languages and operating systems, p.162-174, October 12-15, 1992, Boston, Massachusetts, United States
• Torrellas95: J. Torrellas , Chun Xia , R. Daigle, Optimizing instruction cache performance for operating system intensive workloads, Proceedings of the 1st IEEE Symposium on High-Performance Computer Architecture, p.360, January 22-25, 1995
• Touma92: Walid Rachid Touma, The dynamics of the computer industry: modeling the supply of workstations and their components, Kluwer Academic Publishers, Norwell, MA, 1993
• Uhlig94: Richard Uhlig , David Nagle , Trevor Mudge , Stuart Sechrest, Trap-driven simulation with Tapeworm II, Proceedings of the sixth international conference on Architectural support for programming languages and operating systems, p.132-144, October 05-07, 1994, San Jose, California, United States
• Uhlig95: Richard Albert Uhlig, Trap-driven memory simulation, University of Michigan, Ann Arbor, MI, 1996
• Wada92: Wada, T., Rajan, S. and Przybylski, S. An analytical access time model for on-chip cache memories. IEEE Journal of Solid-State Circuits 27 (8): 1147-1156, 1992.
• Wang89: W. H. Wang , J.-L. Baer , H. M. Levy, Organization and performance of a two-level virtual-real cache hierarchy, Proceedings of the 16th annual international symposium on Computer architecture, p.140-148, April 1989, Jerusalem, Israel
• Wiecek92: Cheryl A. Wiecek, A Model and Prototype of VMS Using the Mach 3.0 Kernel, Proceedings of the Workshop on Micro-kernels and Other Kernel Architectures, p.187-204, April 27-28, 1992
• Wilton94: Wilton, S. and Jouppi, N. An enhanced access and cycle time model for on-chip caches. DEC Western Research Lab. Technical Report 93/5.1994.

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

  C. Computer Systems Organization
  C.0 GENERAL
      Subjects: Hardware/software interfaces

  D. Software
  D.2 SOFTWARE ENGINEERING
        D.2.10 Design**
            Subjects: Methodologies**

General Terms:
Algorithms, Design, Experimentation, Measurement, Performance