Neural methods for dynamic branch prediction

ABSTRACT

This article presents a new and highly accurate method for branch prediction. The key idea is to use one of the simplest possible neural methods, the perceptron, as an alternative to the commonly used two-bit counters. The source of our predictor's accuracy is its ability to use long history lengths, because the hardware resources for our method scale linearly, rather than exponentially, with the history length. We describe two versions of perceptron predictors, and we evaluate these predictors with respect to five well-known predictors. We show that for a 4 KB hardware budget, a simple version of our method that uses a global history achieves a misprediction rate of 4.6% on the SPEC 2000 integer benchmarks, an improvement of 26% over gshare. We also introduce a global/local version of our predictor that is 14% more accurate than the McFarling-style hybrid predictor of the Alpha 21264. We show that for hardware budgets of up to 256 KB, this global/local perceptron predictor is more accurate than Evers' multicomponent predictor, so we conclude that ours is the most accurate dynamic predictor currently available. To explore the feasibility of our ideas, we provide a circuit-level design of the perceptron predictor and describe techniques that allow our complex predictor to operate quickly. Finally, we show how the relatively complex perceptron predictor can be used in modern CPUs by having it override a simpler, quicker Smith predictor, providing IPC improvements of 15.8% over gshare and 5.7% over the McFarling hybrid predictor.

REFERENCES

• 1: Thomas Ball , James R. Larus, Branch prediction for free, Proceedings of the ACM SIGPLAN 1993 conference on Programming language design and implementation, p.300-313, June 21-25, 1993, Albuquerque, New Mexico, United States
• 2: Block, H. D. 1962. The perceptron: A model for brain functioning. Rev. Mod. Phy. 34, 123--135.
• 3: Burger, D. and Austin, T. M. 1997. The SimpleScalar tool set version 2.0. Tech. Rep. 1342, Computer Sciences Department, University of Wisconsin. June.
• 4: Brad Calder , Dirk Grunwald , Michael Jones , Donald Lindsay , James Martin , Michael Mozer , Benjamin Zorn, Evidence-based static branch prediction using machine learning, ACM Transactions on Programming Languages and Systems (TOPLAS), v.19 n.1, p.188-222, Jan. 1997 [doi>10.1145/239912.239923]
• 5: Thomas T. Cormen , Charles E. Leiserson , Ronald L. Rivest, Introduction to algorithms, MIT Press, Cambridge, MA, 1990
• 6: A. N. Eden , T. Mudge, The YAGS branch prediction scheme, Proceedings of the 31st annual ACM/IEEE international symposium on Microarchitecture, p.69-77, November 1998, Dallas, Texas, United States
• 7: Joel Emer , Nikolas Gloy, A language for describing predictors and its application to automatic synthesis, Proceedings of the 24th annual international symposium on Computer architecture, p.304-314, June 01-04, 1997, Denver, Colorado, United States
• 8: Marius Evers , Yale N. Patt, Improving branch prediction by understanding branch behavior, 2000
• 9: 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
• 10: Laurene Fausett, Fundamentals of neural networks: architectures, algorithms, and applications, Prentice-Hall, Inc., Upper Saddle River, NJ, 1994
• 11: Gomez, F., Burger, D., and Miikkulainen, R. 2001. A neuroevolution method for dynamic resource allocation on a chip multiprocessor. In Proceedings of the International Joint Conference on Neural Networks (IJCNN-01), 2355--2360.
• 12: John L. Hennessy , David A. Patterson, Computer architecture (2nd ed.): a quantitative approach, Morgan Kaufmann Publishers Inc., San Francisco, CA, 1996
• 13: Erik Jacobsen , Eric Rotenberg , J. E. Smith, Assigning confidence to conditional branch predictions, Proceedings of the 29th annual ACM/IEEE international symposium on Microarchitecture, p.142-152, December 02-04, 1996, Paris, France
• 14: 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
• 15: Jiménez, D. A. and Walsh, N. 1998. Dynamically weighted ensemble neural networks for classification. In Proceedings of the 1998 International Joint Conference on Neural Networks, 753--756.
• 16: 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]
• 17: R. E. Kessler, The Alpha 21264 Microprocessor, IEEE Micro, v.19 n.2, p.24-36, March 1999 [doi>10.1109/40.755465]
• 18: Arun D. Kulkarni, Artificial Neural Networks for Image Understanding, John Wiley & Sons, Inc., New York, NY, 1993
• 19: Chih-Chieh Lee , I-Cheng K. Chen , Trevor N. Mudge, The bi-mode branch predictor, Proceedings of the 30th annual ACM/IEEE international symposium on Microarchitecture, p.4-13, December 01-03, 1997, Research Triangle Park, North Carolina, United States
• 20: Lesartre, G. and Hunt, D. 1997. PA-8500: The continuing evolution of the PA-8000 family. In 42nd IEEE International Computer Conference.
• 21: McFarling, S. 1993. Combining branch predictors. Tech. Rep. TN-36m, Digital Western Research Laboratory, June.
• 22: Pierre Michaud , André Seznec , Richard Uhlig, Trading conflict and capacity aliasing in conditional branch predictors, Proceedings of the 24th annual international symposium on Computer architecture, p.292-303, June 01-04, 1997, Denver, Colorado, United States
• 23: Rosenblatt, F. 1962. Principles of Neurodynamics: Perceptrons and the Theory of Brain Mechanisms. Spartan, New York.
• 24: Stuart Sechrest , Chih-Chieh Lee , Trevor Mudge, Correlation and aliasing in dynamic branch predictors, Proceedings of the 23rd annual international symposium on Computer architecture, p.22-32, May 22-24, 1996, Philadelphia, Pennsylvania, United States
• 25: Setiono, R. and Liu, H. 1995. Understanding neural networks via rule extraction. In Proceedings of the Fourteenth International Joint Conference on Artificial Intelligence, 480--485.
• 26: 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
• 27: Eric Sprangle , Robert S. Chappell , Mitch Alsup , Yale N. Patt, The agree predictor: a mechanism for reducing negative branch history interference, Proceedings of the 24th annual international symposium on Computer architecture, p.284-291, June 01-04, 1997, Denver, Colorado, United States
• 28: 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
• 29: Vintan, L. and Iridon, M. 1999. Towards a high performance neural branch predictor. In Proceedings of the International Joint Conference on Neural Networks (IJCNN), vol. 2. 868--873.
• 30: Kai Wang , Manoj Franklin, Highly accurate data value prediction using hybrid predictors, Proceedings of the 30th annual ACM/IEEE international symposium on Microarchitecture, p.281-290, December 01-03, 1997, Research Triangle Park, North Carolina, United States
• 31: Widrow, B. and Hoff Jr., M. 1960. Adaptive switching circuits. In IRE WESCON Convention Record, part 4, 96--104.
• 32: Tse-Yu Yeh , Yale N. Patt, Two-level adaptive training branch prediction, Proceedings of the 24th annual international symposium on Microarchitecture, p.51-61, September 1991, Albuquerque, New Mexico, Puerto Rico [doi>10.1145/123465.123475]

INDEX TERMS

Primary Classification:
  C. Computer Systems Organization
  C.1 PROCESSOR ARCHITECTURES
      C.1.1 Single Data Stream Architectures

Additional Classification:
  C. Computer Systems Organization
  C.1 PROCESSOR ARCHITECTURES
      C.1.3 Other Architecture Styles
          Subjects: Neural nets

General Terms:
Performance

Keywords:
Branch prediction, neural networks