Donald Lindsay
Department of Computer Science
Campus Box 430
University of Colorado
Boulder, CO 80309
lindsay@cs.colorado.edu
Recent microprocessors devote tens of thousands of transistors to the important problem of performing a branch prediction in a single pipeline stage. This Thesis is about the design of predictors that would be valuable in such microprocessors, both present and future. My overall approach has been to look at designs that are profile-based, and which are therefore partly implemented in software. This work encompasses new static predictors, static selection in hybrid predictors, and static optimization of specific properties.
My new static predictors are a class of machine-generated functions. This class can be efficiently implemented by Programmed Logic Arrays and are trained by growing decision trees over sets of branch history patterns.
Hybrid branch predictors combine the predictions of multiple ``component'' predictors. The prediction combining hardware --- the selection mechanism --- has costs that I eliminate by controlling selection from software, in what I call a static hybrid predictor. This Thesis investigates several static hybridization techniques, and also investigate combinations of components that form effective static hybrid predictors.
An important advantage of static selection is that each branch site is assigned to a single component predictor. This assignment means that unlike most previous hybrids, the site makes no demands on other components, effectively increasing the overall predictor ``capacity''.
I argue that all of my proposals are implementable, and that they collectively address important size, speed and parallelism issues currently facing hardware designers.
My design approach requires profiling and compute intensive parameter space searches. This Thesis addresses a number of resulting issues about suitability of benchmark suites, about cross validation techniques, efficient search methods, robustness, sensitivity to parameters, and sensitivity to cost models.
Finally, this Thesis presents results that show some new predictors to be better than any in the current literature, both in performance and in cost effectiveness, across a wide range of sizes. These new predictors also solve the widely studied aliasing problem to the extent that future research should instead emphasize increases in predictive power.