Fast Path-Based Neural Branch Prediction

ABSTRACT

Microarchitectural prediction based on neural learninghas received increasing attention in recent years. However,neural prediction remains impractical because its superioraccuracy over conventional predictors is not enough to offsetthe cost imposed by its high latency. We present a newneural branch predictor that solves the problem from bothdirections: it is both more accurate and much faster thanprevious neural predictors. Our predictor improves accuracyby combining path and pattern history to overcomelimitations inherent to previous predictors. It also has muchlower latency than previous neural predictors. The result isa predictor with accuracy far superior to conventional predictorsbut with latency comparable to predictors from industrialdesigns. Our simulations show that a path-basedneural predictor improves the instructions-per-cycle (IPC)rate of an aggressively clocked microarchitecture by 16%over the original perceptron predictor.

REFERENCES

• 1: [1] H. D. Block. The perceptron: A model for brain functioning. Reviews of Modern Physics, 34:123-135, 1962.
• 2: Edward Brekelbaum , Jeff Rupley , Chris Wilkerson , Bryan Black, Hierarchical Scheduling Windows, Proceedings of the 35th annual ACM/IEEE international symposium on Microarchitecture, November 18-22, 2002, Istanbul, Turkey
• 3: [3] Doug Burger and Todd M. Austin. The SimpleScalar tool set version 2.0. Technical Report 1342, Computer Sciences Department, University of Wisconsin, June 1997.
• 4: Brad Calder , Dirk Grunwald , Donald Lindsay , James Martin , Michael Mozer , Benjamin Zorn, Corpus-based static branch prediction, Proceedings of the ACM SIGPLAN 1995 conference on Programming language design and implementation, p.79-92, June 18-21, 1995, La Jolla, California, United States
• 5: Thomas T. Cormen , Charles E. Leiserson , Ronald L. Rivest, Introduction to algorithms, MIT Press, Cambridge, MA, 1990
• 6: Marius Evers , Sanjay J. Patel , Robert S. Chappell , Yale N. Patt, An analysis of correlation and predictability: what makes two-level branch predictors work, Proceedings of the 25th annual international symposium on Computer architecture, p.52-61, June 27-July 02, 1998, Barcelona, Spain
• 7: Daniel A. Jiménez, Reconsidering Complex Branch Predictors, Proceedings of the 9th International Symposium on High-Performance Computer Architecture, p.43, February 08-12, 2003
• 8: Daniel A. Jiménez , Stephen W. Keckler , Calvin Lin, The impact of delay on the design of branch predictors, Proceedings of the 33rd annual ACM/IEEE international symposium on Microarchitecture, p.67-76, December 2000, Monterey, California, United States [doi>10.1145/360128.360137]
• 9: Daniel A. Jiménez , Calvin Lin, Dynamic Branch Prediction with Perceptrons, Proceedings of the 7th International Symposium on High-Performance Computer Architecture, p.197, January 20-24, 2001
• 10: Daniel A. Jiménez , Calvin Lin, Neural methods for dynamic branch prediction, ACM Transactions on Computer Systems (TOCS), v.20 n.4, p.369-397, November 2002 [doi>10.1145/571637.571639]
• 11: R. E. Kessler, The Alpha 21264 Microprocessor, IEEE Micro, v.19 n.2, p.24-36, March 1999 [doi>10.1109/40.755465]
• 12: Gabriel H. Loh , Dana S. Henry, Predicting Conditional Branches With Fusion-Based Hybrid Predictors, Proceedings of the 2002 International Conference on Parallel Architectures and Compilation Techniques, p.165, September 22-25, 2002
• 13: [13] Scott McFarling. Combining branch predictors. Technical Report TN-36m, Digital Western Research Laboratory, June 1993.
• 14: 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
• 15: [15] Frank Rosenblatt. Principles of Neurodynamics: Perceptrons and the Theory of Brain Mechanisms. Spartan, 1962.
• 16: André Seznec , Stephen Felix , Venkata Krishnan , Yiannakis Sazeides, Design tradeoffs for the Alpha EV8 conditional branch predictor, Proceedings of the 29th annual international symposium on Computer architecture, May 25-29, 2002, Anchorage, Alaska
• 17: André Seznec , Antony Fraboulet, Effective ahead pipelining of instruction block address generation, Proceedings of the 30th annual international symposium on Computer architecture, June 09-11, 2003, San Diego, California
• 18: [18] Premkishore Shivakumar and Norman P. Jouppi. Cacti 3.0: An integrated cache timing, power and area model. Technical Report 2001/2, Compaq Computer Corporation, August 2001.
• 19: Kevin Skadron , Margaret Martonosi , Douglas W. Clark, A Taxonomy of Branch Mispredictions, and Alloyed Prediction as a Robust Solution to Wrong-History Mispredictions, Proceedings of the 2000 International Conference on Parallel Architectures and Compilation Techniques, p.199, October 15-19, 2000
• 20: Eric Sprangle , Doug Carmean, Increasing processor performance by implementing deeper pipelines, Proceedings of the 29th annual international symposium on Computer architecture, May 25-29, 2002, Anchorage, Alaska
• 21: Jared Stark , Marius Evers , Yale N. Patt, Variable length path branch prediction, Proceedings of the eighth international conference on Architectural support for programming languages and operating systems, p.170-179, October 02-07, 1998, San Jose, California, United States
• 22: Renju Thomas , Manoj Franklin , Chris Wilkerson , Jared Stark, Improving branch prediction by dynamic dataflow-based identification of correlated branches from a large global history, Proceedings of the 30th annual international symposium on Computer architecture, June 09-11, 2003, San Diego, California
• 23: [23] Lucian N. Vintan and M. Iridon. Towards a high performance neural branch predictor. In Proceedings of the International Joint Conference on Neural Networks, volume 2, pages 868- 873, July 1999.

INDEX TERMS

Primary Classification:
  C. Computer Systems Organization
  C.4 PERFORMANCE OF SYSTEMS
      Subjects: Modeling techniques

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

  I. Computing Methodologies
  I.2 ARTIFICIAL INTELLIGENCE
      I.2.6 Learning
          Subjects: Connectionism and neural nets

General Terms:
Design, Measurement, Performance