Improving trace cache effectiveness with branch promotion and trace packing

ABSTRACT

The increasing widths of superscalar processors are placing greater demands upon the fetch mechanism. The trace cache meets these demands by placing logically contiguous instructions in physically contiguous storage. As a result, the trace cache delivers instructions at a high rate by supplying multiple fetch blocks each cycle.In this paper, we examine two techniques to improve the number of instructions delivered each cycle by the trace cache. The first technique, branch promotion, dynamically converts strongly biased branches into branches with static predictions. Because these promoted branches require no dynamic prediction, the branch predictor suffers less from the negative effects of interference.Branch promotion unlocks the potential of the second technique: trace packing. With trace packing, trace segments are packed with as many instructions as will fit, without regard to naturally occurring fetch block boundaries. With both techniques, the effective fetch rate of the trace cache jumps up 17% over a trace cache which implements neither.On a machine where the execution engine has a very aggressive memory disambiguator, the performance of a machine using branch promotion and trace packing is on average 11% higher than a machine using neither technique.

REFERENCES

• 1: D. Burger, T. Austin, and S. Bennett. Evaluating future microprocessors: The simplescalar tool set. Technical Report 1308, University of Wisconsin - Madison Technical Report, July 1996.
• 2: Po-Yung Chang , Marius Evers , Yale N. Patt, Improving Branch Prediction Accuracy by Reducing Pattern History Table Interference, Proceedings of the 1996 Conference on Parallel Architectures and Compilation Techniques, p.48, October 20-23, 1996
• 3: Po-Yung Chang , Eric Hao , Tse-Yu Yeh , Yale Patt, Branch classification: a new mechanism for improving branch predictor performance, Proceedings of the 27th annual international symposium on Microarchitecture, p.22-31, November 30-December 02, 1994, San Jose, California, United States [doi>10.1145/192724.192727]
• 4: Manoj Franklin , Mark Smotherman, A fill-unit approach to multiple instruction issue, Proceedings of the 27th annual international symposium on Microarchitecture, p.162-171, November 30-December 02, 1994, San Jose, California, United States [doi>10.1145/192724.192748]
• 5: 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
• 6: W. W. Hwu , Y. N. Patt, Checkpoint repair for out-of-order execution machines, Proceedings of the 14th annual international symposium on Computer architecture, p.18-26, June 02-05, 1987, Pittsburgh, Pennsylvania, United States [doi>10.1145/30350.30353]
• 7: 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
• 8: Andreas Moshovos , Scott E. Breach , T. N. Vijaykumar , Gurindar S. Sohi, Dynamic speculation and synchronization of data dependences, Proceedings of the 24th annual international symposium on Computer architecture, p.181-193, June 01-04, 1997, Denver, Colorado, United States
• 9: S.J. Patel, D. H. Friendly, and Y. N. Patt. Critical issues regarding the trace cache fetch mechanism. Technical Report CSE-TR-335-97, University of Michigan Technical Report, May 1997.
• 10: A. Peleg and U. Weiser. Dynamic flow instruction cache memory organized around trace segments independant of virtual address line. U.S. Patent Number 5,381,533, 1994.
• 11: 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
• 12: Eric Rotenberg , Quinn Jacobson , Yiannakis Sazeides , Jim Smith, Trace processors, Proceedings of the 30th annual ACM/IEEE international symposium on Microarchitecture, p.138-148, December 01-03, 1997, Research Triangle Park, North Carolina, United States
• 13: Mark Smotherman , Manoj Franklin, Improving CISC instruction decoding performance using a fill unit, Proceedings of the 28th annual international symposium on Microarchitecture, p.219-229, November 29-December 01, 1995, Ann Arbor, Michigan, United States
• 14: Jared Stark , Paul Racunas , Yale N. Patt, Reducing the performance impact of instruction cache misses by writing instructions into the reservation stations out-of-order, Proceedings of the 30th annual ACM/IEEE international symposium on Microarchitecture, p.34-43, December 01-03, 1997, Research Triangle Park, North Carolina, United States
• 15: Gary S. Tyson , Todd M. Austin, Improving the accuracy and performance of memory communication through renaming, Proceedings of the 30th annual ACM/IEEE international symposium on Microarchitecture, p.218-227, December 01-03, 1997, Research Triangle Park, North Carolina, United States
• 16: Cliff Young , Nicolas Gloy , Michael D. Smith, A comparative analysis of schemes for correlated branch prediction, Proceedings of the 22nd annual international symposium on Computer architecture, p.276-286, June 22-24, 1995, S. Margherita Ligure, Italy

INDEX TERMS

Primary Classification:
  C. Computer Systems Organization
  C.1 PROCESSOR ARCHITECTURES

Additional Classification:
  B. Hardware
  B.8 Performance and Reliability