University of Central England in Birmingham
The Prediction-by-Partial Matching (PPM) algorithm has been well known for its high prediction accuracy. Recent proposals of PPM-like predictors confirm its effectiveness on branch prediction. In this paper, the authors introduce a new branch prediction algorithm, named Prediction by combining Multiple Partial Matches (PMPM). The PMPM algorithm selectively combines multiple matches instead of using the longest match as in PPM. They analyze the PPM and PMPM algorithms and show why PMPM is capable of making more accurate predictions than PPM. Based on PMPM, they propose both an idealistic predictor to push the limit of branch prediction accuracy and a realistic predictor for practical implementation.