Take a look at the new version of this page: [ beta version ]. Tell us what you think.

ABSTRACT

Current trends in processor design are pointing to deeper and wider pipelines and superscalar architectures. The efficient use of these resources requires speculative execution, a technique whereby the processor continues executing the predicted path of a branch before the branch condition is resolved.In this paper, we investigate the implications of speculative execution on instruction cache performance. We explore policies for managing instruction cache misses ranging from aggressive policies (always fetch on the speculative path) to conservative ones (wait until branches are resolved). We test these policies and their interaction with next-line prefetching by simulating the effects on instruction caches with varying architectural parameters. Our results suggest that an aggressive policy combined with next-line prefetching is best for small latencies while more conservative policies are preferable for large latencies.

REFERENCES

• Bray & Flynn 91: Brian K. Bray , M. J. Flynn, Strategies for branch target buffers, Proceedings of the 24th annual international symposium on Microarchitecture, p.42-50, September 1991, Albuquerque, New Mexico, Puerto Rico [doi>10.1145/123465.123473]
• Calder & Grunwald 94: B. Calder , D. Grunwald, Fast and accurate instruction fetch and branch prediction, Proceedings of the 21ST annual international symposium on Computer architecture, p.2-11, April 18-21, 1994, Chicago, Illinois, United States
• 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
• Lee & Smith 84: Lee, J. K. E and Smith, A. J. Branch prediction strategies and branch target buffer design. IEEE Computer, 21 (7):6-22, January 1984.
• McFarling & Hennessy 86: S. McFarling , J. Hennesey, Reducing the cost of branches, Proceedings of the 13th annual international symposium on Computer architecture, p.396-403, June 02-05, 1986, Tokyo, Japan
• McFarling 93: McFarling, S. Combining branch predictors. TN 36, DEC- WRL, June 1993.
• Pan et al. 92: Shien-Tai Pan , Kimming So , Joseph T. Rahmeh, Improving the accuracy of dynamic branch prediction using branch correlation, Proceedings of the fifth international conference on Architectural support for programming languages and operating systems, p.76-84, October 12-15, 1992, Boston, Massachusetts, United States
• Perleberg & Smith 93: C. H. Perleberg , A. J. Smith, Branch Target Buffer Design and Optimization, IEEE Transactions on Computers, v.42 n.4, p.396-412, April 1993 [doi>10.1109/12.214687]
• Pierce & Mudge 94: Pierce, J. and Mudge, T. Wrong-path instruction prefetching. Technical Report CSE-222-94, University of Michigan, 1994.
• Pierce 95: James Edward Pierce, Cache behavior in the presence of speculative execution: the benefits of misprediction, University of Michigan, Ann Arbor, MI, 1995
• Smith & W.-C.Hsu 92: 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
• Smith 81: James E. Smith, A study of branch prediction strategies, Proceedings of the 8th annual symposium on Computer Architecture, p.135-148, May 12-14, 1981, Minneapolis, Minnesota, United States
• Smith 82: Alan Jay Smith, Cache Memories, ACM Computing Surveys (CSUR), v.14 n.3, p.473-530, Sept. 1982 [doi>10.1145/356887.356892]
• Srivastava & Eustace 94: Amitabh Srivastava , Alan Eustace, ATOM: a system for building customized program analysis tools, Proceedings of the ACM SIGPLAN 1994 conference on Programming language design and implementation, p.196-205, June 20-24, 1994, Orlando, Florida, United States
• Yeh & Patt 92a: Tse-Yu Yeh , Yale N. Patt, Alternative implementations of two-level adaptive branch prediction, Proceedings of the 19th annual international symposium on Computer architecture, p.124-134, May 19-21, 1992, Queensland, Australia
• Yeh & Patt 92b: Tse-Yu Yeh , Yale N. Patt, A comprehensive instruction fetch mechanism for a processor supporting speculative execution, Proceedings of the 25th annual international symposium on Microarchitecture, p.129-139, December 01-04, 1992, Portland, Oregon, United States
• Yeh & Patt 93: Tse-Yu Yeh , Yale N. Patt, A comparison of dynamic branch predictors that use two levels of branch history, Proceedings of the 20th annual international symposium on Computer architecture, p.257-266, May 16-19, 1993, San Diego, California, United States

INDEX TERMS

Primary Classification:
  C. Computer Systems Organization
  C.1 PROCESSOR ARCHITECTURES
      C.1.2 Multiple Data Stream Architectures (Multiprocessors)
          Subjects: Parallel processors**

Additional Classification:
  C. Computer Systems Organization
  C.4 PERFORMANCE OF SYSTEMS
      Subjects: Performance attributes; Modeling techniques

  D. Software
  D.1 PROGRAMMING TECHNIQUES
  D.3 PROGRAMMING LANGUAGES
      D.3.2 Language Classifications

          Nouns: C++

General Terms:
Design, Experimentation, Languages, Performance