Completion time multiple branch prediction for enhancing trace cache performance

ABSTRACT

The need for multiple branch prediction is inherent to wide instruction fetching. This paper presents a completion time multiple branch predictor called the Tree-based Multiple Branch Predictor (TMP) that builds on previous single branch prediction techniques. It employs a tree structure of branch predictors, or tree-node predictors, and achieves accurate multiple branch prediction by leveraging the high accuracies of the individual branch predictors. A highly-efficient TMP design uses the 2-bit saturating counters for the tree-node predictors. To achieve higher prediction rate, the TMP employs two-level schemes for the tree-node predictors resulting in a three-level TMP design. Placing the TMP at completion time reduces the critical latency in the front-end of the pipeline; the resultant longer update latency does not significantly impact the overall performance. In this paper the TMP is applied to a trace cache design and shown to be very effective in increasing its performance. Results: A realistic-size TMP (72KB) can predict 1, 2, 3, and 4 consecutive blocks with compounded prediction accuracies of 96%, 93%, 87%, and 82%, respectively. The block-based trace cache with this TMP achieves 4.75 IPC for SPECint95 on an idealized machine, which is a 20% performance improvement over the original design [1]. This improved performance is 8% above that of a conventional I-cache design with perfect single branch prediction.

REFERENCES

• 1: Bryan Black , Bohuslav Rychlik , John Paul Shen, The block-based trace cache, Proceedings of the 26th annual international symposium on Computer architecture, p.196-207, May 01-04, 1999, Atlanta, Georgia, United States
• 2: Brad Calder , Dirk Grunwald, Next cache line and set prediction, Proceedings of the 22nd annual international symposium on Computer architecture, p.287-296, June 22-24, 1995, S. Margherita Ligure, Italy
• 3: Thomas M. Conte , Kishore N. Menezes , Patrick M. Mills , Burzin A. Patel, Optimization of instruction fetch mechanisms for high issue rates, Proceedings of the 22nd annual international symposium on Computer architecture, p.333-344, June 22-24, 1995, S. Margherita Ligure, Italy
• 4: Keith Diefendorff , Ed Silha, The PowerPC User Instruction Set Architecture, IEEE Micro, v.14 n.5, p.30-41, October 1994 [doi>10.1109/MM.1994.363069]
• 5: 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
• 6: Daniel Holmes Friendly , Sanjay Jeram Patel , Yale N. Patt, Putting the fill unit to work: dynamic optimizations for trace cache microprocessors, Proceedings of the 31st annual ACM/IEEE international symposium on Microarchitecture, p.173-181, November 1998, Dallas, Texas, United States
• 7: IBM Microelectronics Division, PowerPC 604 RISC Microprocessor User' s Manual, 1994.
• 8: Quinn Jacobson , Eric Rotenberg , James E. Smith, Path-based next trace prediction, Proceedings of the 30th annual ACM/IEEE international symposium on Microarchitecture, p.14-23, December 01-03, 1997, Research Triangle Park, North Carolina, United States
• 9: S. McFarling, "Combining Branch Predictors." Technical Report TN-36, Digital Equipment Corp., June 1993.
• 10: Ravi Nair, Dynamic path-based branch correlation, Proceedings of the 28th annual international symposium on Microarchitecture, p.15-23, November 29-December 01, 1995, Ann Arbor, Michigan, United States
• 11: Sanjay Jeram Patel , Marius Evers , Yale N. Patt, Improving trace cache effectiveness with branch promotion and trace packing, Proceedings of the 25th annual international symposium on Computer architecture, p.262-271, June 27-July 02, 1998, Barcelona, Spain
• 12: S. Patel, D. Friendly, and Y. Patt, "Evaluation of Design Options for the Trace Cache Fetch Mechanism." IEEE Transactions on Computers a Special Issue on Cache Memory and Related Problems.
• 13: 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
• 14: 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
• 15: André Seznec , Stéphan Jourdan , Pascal Sainrat , Pierre Michaud, Multiple-block ahead branch predictors, Proceedings of the seventh international conference on Architectural support for programming languages and operating systems, p.116-127, October 01-04, 1996, Cambridge, Massachusetts, United States
• 16: J. Smith, "A Study of Branch Prediction Strategies." In Proceedings of the 30th International Symposium on Microarchitecture, pp. 138-148, December 1997.
• 17: S. Peter Song , Marvin Denman , Joe Chang, The PowerPC 604 RISC microprocessor, IEEE Micro, v.14 n.5, p.8-17, October 1994 [doi>10.1109/MM.1994.363071]
• 18: 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]
• 19: 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
• 20: 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:
  B. Hardware
  B.3 MEMORY STRUCTURES

Additional Classification:
  B. Hardware
  B.2 ARITHMETIC AND LOGIC STRUCTURES

General Terms:
Experimentation, Measurement, Performance