CORPUS-BASED STATIC BRANCH PREDICTION

Correctly predicting the direction that branches will take is increasi ngly important in today's wide-issue computer architectures. The name program-based branch prediction is given to static branch prediction t echniques that base their prediction on a program's structure. In this paper, we investigate a new approach to program-based branch predicti on that uses a body of existing programs to predict the branch behavio r in a new program. We call this approach to program-based branch pred iction, evidence-based static prediction, or ESP. The main idea of ESP is that the behavior of a corpus of programs can be used to infer the behavior of new programs. In this paper, we use a neural network to m ap static features associated with each branch to the probabilty that the branch will be taken. ESP shows significant advantages over other prediction mechanisms. Specifically, it is a program-based technique, it is effective across a range of programming languages and programmin g styles, and it does not rely on the use of expert-defined heuristics . In this paper, we describe the application of ESP to the problem of branch prediction and compare our results to existing program-based br anch predictors. We also investigate the applicability of ESP across c omputer architectures, programming languages, compilers, and run-time systems. Averaging over a body of 43 C and Fortran programs, ESP branc h prediction results in a miss rate of 20%, as compared with the 25% m iss rate obtained using the best existing program-based heuristics.