Improving branch prediction accuracy via effective source information and prediction algorithms.

Modern superscalar processors rely on branch predictors to sustain a high instruction fetch throughput.

Given the trend of deep pipelines and large instruction windows, a branch misprediction will incur a large performance penalty and result in a significant amount of energy wasted by the instructions along wrong paths.

With their critical role in high performance processors, there has been extensive research on branch predictors to improve the prediction accuracy.

Conceptually a dynamic branch prediction scheme includes three major components: a source, an information processor, and a predictor.

Traditional works mainly focus on the algorithm for the predictor.

In this dissertation, besides novel prediction algorithms, we investigate other components and develop untraditional ways to improve the prediction accuracy.

First, we propose an adaptive information processing method to dynamically extract the most effective inputs to maximize the correlation to be exploited by the predictor.

Second, we propose a new prediction algorithm, which improves the Prediction by Partial Matching (PPM) algorithm by selectively combining multiple partial matches.

The PPM algorithm was previously considered optimal and has been used to derive the upper limit of branch prediction accuracy.

Our proposed algorithm achieves higher prediction accuracy than PPM and can be implemented in realistic hardware budget.

Third, we discover a new locality existing between the address of producer loads and the outcomes of their consumer branches.

We study this address-branch correlation in detail and propose a branch predictor to explore this correlation for long-latency and hard-to-predict branches, which existing branch predictors fail to predict accurately.