摘要：Traditional branch predictors exploit correlations between pattern history and branchoutcome to predict branches, but there is a stronger and more natural correlation betweenpath history and branch outcome. I exploit this correlation with piecewise linear branchprediction, an idealized branch predictor that develops a set of linear functions, one foreach program path to the branch to be predicted, that separate predicted taken from predictednot taken branches. Taken together, all of these linear functions form a piecewise lineardecision surface.Disregarding implementation concerns modulo a 64.25 kilobit hardware budget, I presentthis idealized branch predictor for the first Championship Branch Predictor competition. Idescribe the idea of the algorithm and as well as tricks used to squeeze it into 64.25 kilobitswhile maintaining good accuracy
