EVIDENCE-BASED STATIC BRANCH PREDICTION USING MACHINE LEARNING

Correctly predicting the direction that branches will take is increasi ngly important in today's nide-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 article, we investigate a new approach to program-based branch predic tion that uses a body of existing programs to predict the branch behav ior in a new program. We call this approach to program-based branch pr ediction evidence-based static prediction, or ESP. The main idea of ES P is that the behavior of a corpus of programs can be used to infer th e behavior of new programs. In this article, we use neural networks an d decision trees la map static features associated with each branch to a prediction that the branch will be taken. ESP shows significant adv antages over other prediction mechanisms. Specifically, it is a progra m-based technique; it is effective across a range of programming langu ages and programming styles; and it does not rely on the use of expert -defined heuristics. In this article, me describe the application of E SP to the problem of static branch prediction and compare our results to existing program-based branch predictors. We also investigate the a pplicability of ESP across computer architectures, programming languag es, compilers, and run-time systems. We provide results showing how se nsitive ESP is to the number and type of static features and programs included in the ESP training sets, and we compare the efficacy of stat ic branch prediction for subroutine libraries. Averaging over a body o f 43 C and Fortran programs, ESP branch prediction results in a miss r ate of 20%, as compared with the 25% miss rate obtained using the best existing program-based heuristics.