Abstract

As processor architectures have increased their reliance on speculative execution to improve performance, the importance of accurate prediction of what to execute speculatively has increased. Our approach was to use a simple algebraic-style notation that allows one to describe branch predictors and also the feedback-process necessary to improve the prediction. This notation, developed by Joel Emer and Nikolas Gloy at Harvard University, allows the description of a wide variety of branch predictors in a uniform way. Also, this notation facilitates the use of an efficient search technique called Genetic Programming, which is loosely modeled on the natural evolutionary process, to explore the design space. We expanded the initial notation to allow a more detailed description of modern branch predictors. In this paper, we describe our notation version, the modeling system used and the first results of the application of genetic programming to the design of branch predictors.