Using convolutional neural networks to improve branch prediction

The state-of-the-art branch predictor, TAGE, remains inefficient at identifying correlated branches deep in a noisy global branch history. This dissertation argues this inefficiency is a fundamental limitation of runtime branch prediction and not a coincidental artifact due to the design of TAGE. To further improve branch prediction, we need to relax the constraint of runtime only training and adopt more sophisticated prediction mechanisms. To this end, I propose using convolutional neural networks (CNNs) that are trained at compile-time to accurately predict branches that TAGE cannot. Given enough profiling coverage, CNNs learn input-independent branch correlations that can accurately predict branches when running a program with unseen inputs. I describe two practical approaches for using CNNs. First, I build on the work of Tarsa et al. and introduce BranchNet, a CNN with a storage-efficient on-chip inference engine tailored to the needs of branch prediction. At runtime, BranchNet predicts a few hard-to-predict branches, while TAGE-SC-L predicts the remaining branches. This hybrid approach reduces the MPKI of SPEC2017 Integer benchmarks by 9.6% (and up to 17.7%) compared to a 64KB TAGE-SC-L without increasing the prediction latency. Alternatively, instead of using BranchNet as a black-box predictor, I use it to explicitly identify correlated branches and filter the global branch history of TAGE to include only the outcomes of correlated branches. Filtering the branch history leads to less allocation pressure and faster warmup time in TAGE, resulting in improved prediction accuracy and better storage-efficiency. Filtering TAGE histories achieves a notable fraction of BranchNet's accuracy improvements (average 3.7% MPKI reduction, up to 9.4%) with a simpler predictor design.