Boosting trace cache performance with nonhead miss speculation

ABSTRACT

Trace caches are used to help dynamic branch prediction make multiple predic¿tions in a cycle by embedding some of the predictions in the trace. In this work, we evaluate a trace cache that is capable of delivering a trace consisting of a variable number of instructions via a linked list mechanism. We evaluate several schemes in the context of an x86 processor model that stores decoded instructions. By developing a new classification for trace cache accesses, we are able to target those misses that cause the largest performance loss. We have pro¿posed a hardware speculation technique, called NonHead Miss Speculation, which removes much of the penalty associated with nonhead misses in the eight applica¿tions we studied. Performance improvements ranged from 2% to 20%, with an average speedup of around 10% across our application suite.

REFERENCES

• 1: Simonjit Dutta , Manoj Franklin, Control flow prediction with tree-like subgraphs for superscalar processors, Proceedings of the 28th annual international symposium on Microarchitecture, p.258-263, November 29-December 01, 1995, Ann Arbor, Michigan, United States
• 2: Daniel Holmes Friendly , Sanjay Jeram Patel , Yale N. Patt, Alternative fetch and issue policies for the trace cache fetch mechanism, Proceedings of the 30th annual ACM/IEEE international symposium on Microarchitecture, p.24-33, December 01-03, 1997, Research Triangle Park, North Carolina, United States
• 3: R. Krick, G. Hinton, M. Upton, D. Sager, C. Lee, "Trace Based Instruction Caching," U. S. Patent 6,018,786, October 1997.
• 4: S. W. Melvin , M. C. Shebanow , Y. N. Patt, Hardware support for large atomic units in dynamically scheduled machines, Proceedings of the 21st annual workshop on Microprogramming and microarchitecture, p.60-63, November 28-December 02, 1988, San Diego, California, United States
• 5: Sanjay Jeram Patel , Yale N. Patt, Trace cache design for wide-issue superscalar processors, 1999
• 6: A. Peleg and U. Weiser, "Dynamic Flow Instruction Cache Memory Organized Around Trace Segments Independent of Virtual Address Line," U.S. Patent Number 5,381,533, 1994.
• 7: Eric Rotenberg , Steve Bennett , James E. Smith, Trace cache: a low latency approach to high bandwidth instruction fetching, Proceedings of the 29th annual ACM/IEEE international symposium on Microarchitecture, p.24-35, December 02-04, 1996, Paris, France
• 8: Standard Performance Evaluation Corporation, CPU2000 documentation. http://www.spec.org/osg/cpu2000/docs
• 9: S. Vlaovic, "TAXI: Trace Analysis for X86 Interpretation," PhD Dissertation, University of Michigan, 2002.
• 10: Tse-Yu Yeh , Deborah T. Marr , Yale N. Patt, Increasing the instruction fetch rate via multiple branch prediction and a branch address cache, Proceedings of the 7th international conference on Supercomputing, p.67-76, July 19-23, 1993, Tokyo, Japan [doi>10.1145/165939.165956]

INDEX TERMS

Primary Classification:
  B. Hardware
  B.1 CONTROL STRUCTURES AND MICROPROGRAMMING
      B.1.4 Microprogram Design Aids
          Subjects: Optimization

General Terms:
Design, Performance

Keywords:
branch prediction, optimization, trace cache, x86