Two-level adaptive branch prediction and instruction fetch mechanisms for high performance superscalar processors

As the issue width and depth of pipelining of high performance superscalar processors increase, the importance of an effective instruction fetch mechanism becomes vital to delivering the potential performance of a wide-issue, deep pipelined microarchitecture. In this thesis a new dynamic branch predictor (Two-Level Adaptive Branch Prediction) and a new instruction fetch mechanism suitable for superscalar processors are proposed to reduce the branch execution penalty in instruction fetch. The branch predictor uses two levels of branch history information to make predictions: the history of the last k branches encountered, and the branch behavior for the last s occurrences of the specific pattern of these k branches. Its nine variations are identified according to how finely the history information is gathered. The cost-effectiveness of the variations is compared. Simulation results show that the average misprediction rate for the Two-Level Adaptive branch predictor with a reasonable implementation cost is 3% over nine programs in the SPEC89 benchmark suite, while other known schemes achieve at least 5.6% average misprediction rate. The branch predictor is integrated into an instruction fetch mechanism that is able to fetch multiple instructions each cycle and change instruction flow without incurring any pipeline bubbles. Compared with designs which use other branch predictors, the proposed design significantly reduces the branch execution penalty.