Predicting indirect branches via data compression

Publisher Website
Google Scholar
Abstract
Branch prediction is a key mechanism used to achieve high pe$ormance on multiple issue, deeply pipelined pro- cessors. By predicting the branch outcome at the instruction fetch stage of the pipeline, superscalar processors become able to exploit Instruction Level Parallelism (ILP) by pro- viding a larger window of instructions. However, when a branch is mispredicted, instructions from the mispredicted path must be discarded. Therefore, branch prediction ac- curacy is critical to achieve high performance. Existing branch prediction schemes can accurately predict the direc- tion of conditional branches, but have dificulties predicting the correct targets of indirect branches. Indirect branches occur frequently in Object-Oriented Languages (OOL), as well as in Dynamically-Linked Libraries (DLLs), two pro- gramming environments rapidly increasing in popularity In addition, certain language constructs such as multi-way control transfers (e.g., switches), and architecturalfeatures such as 64-bit address spaces, utilize indirect branching. In this paper, we describe a new algorithmforpredicting unconditional indirect branches called Prediction by Par- tial Matching (PPM). We base our approach on techniques proven to work optimally in the field of data compression. We combine a viable implementation of the PPM algorithm with dynamic per-branch selection of path-based correla- tion and compare its prediction accuracy against a variety of predictors. Our results show that, for approximately the same hardware budget, the combined predictor can achieve a misprediction ratio of 9.47%, as compared to 11.48% for the previously published most accurate indirect branchpre- dictor

This publication has 18 references indexed in Scilit: