CS 752 Project Report Software-based and Hardware- based Branch Prediction Strategies and Performance Evaluation . 1 . Software-based and Hardware-based Branch Prediction Strategies and Performance Evaluation Gang Luo ([email protected]) Hongfei Guo ([email protected]) Abstract In a highly parallel computer system, performance losses due to conditional branch instructions can be minimized by branch prediction to fetch and issue subsequent instructions before the actual branch outcome is known. This paper discusses several software-based static and hardware-based dynamic branch prediction strategies and uses the modified release 3.0 of the SimpleScalar simulation tool set to evaluate their performance. According to our test result, the hardware-based dynamic branch prediction strategies always achieve high prediction accuracy than the software-based static branch prediction strategies. 1. Introduction It is well known that in a highly parallel computer system, branch instructions can break the smooth flow of instruction fetching, decoding and execution. This results in delay, because the instruction issuing must often wait until the actual branch outcome is known. To make things worse, the deeper the pipelining is, the greater performance loss is. To reduce delay, one can try to predict the direction that a branch instruction will take and begin fetching, decoding and issuing instructions before the branch decision is made. However, a wrong branch prediction may lead to more delay because the wrongly fetched instructions occupy the useful functional units, like the ALU, reservation stations, and memory bus. This leads to the need for highly accurate branch prediction strategies. Branch prediction strategies can be divided into two basic categories: software-based static branch prediction strategy and hardware-based dynamic branch prediction strategy.CS 752 Project Report Software-based and Hardware- based Branch Prediction Strategies and Performance Evaluation . 2 . The most widely used software-based static branch prediction strategies are: 1. Taken: Predict that all branches will be taken. 2. Not-taken: Predict that all branches won’t be taken. 3. Back-taken: Predict that all backward branches will be taken; predict that all forward branches won’t be taken. 4. Predict that all branches with certain operation codes will be taken; Predict that the others won’t be taken. The most widely used hardware-based dynamic branch prediction strategies are: 1. One-bit: One-bit branch prediction buffer. 2. Two-bit: Two-bit branch prediction counter. 3. GAg. 4. PAg. 5. PAp. 6. Branch instruction table. Since different data sets will let the programs have different dynamic branch behaviors, so usually hardware-based dynamic branch prediction strategies have better prediction accuracy compared to the software-based static ones. In this paper, we discuss several representative software-based static and hardware-based dynamic branch prediction strategies. Due to the wide variation in branching behavior between different application programs, there exists no good analytical model for evaluating the performance of the branch prediction strategies. So we utilize the SimpleScalar Tool Set Version 3.0, which is a widely used simulation tool set developed at the computer sciences department of University of Wisconsin-Madison, and some benchmark programs to do performance evaluation.CS 752 Project Report Software-based and Hardware- based Branch Prediction Strategies and Performance Evaluation . 3 . Since the meaning of the software-based static branch prediction strategies are quite obvious, we only need to present the meanings of the different hardware-based branch prediction strategies in detail. Then, in section 4, we analyze the performance of the different branch prediction strategies. 2. Hardware-based Dynamic Branch Prediction Strategies 2.1. One-bit Branch Prediction Buffer This is the simplest dynamic branch prediction schema. The branch prediction buffer is a small memory indexed by the lower portion of the address of the branch instruction. It contains a bit that says whether the branch was recently taken or not, which is the hint for the next branch instruction. If the hint turns out to be wrong, the prediction bit is inverted and stored back. This schema has a performance shortcoming: Even if a branch is almost always taken, we will likely predict incorrectly twice, rather than once, when it is not taken. To remedy this, the two-bit prediction schema is proposed. 2.2. Two-bit Branch Prediction Counter The two-bit schema is a specialization of the n-bit schema. Since the two-bit predictors do almost as well as the n-bit predictors, we just rely on two-bit branch predictors rather than the more general n-bit ones. The two-bit predictor is essentially a two-bit counter which takes values between 0 and 3: when the counter is greater than or equal to one half of its maximum value 2, the branch is predicted as taken; otherwise, it is predicted not-taken. The counter is incremented on a taken branch and decremented on a not-taken branch. The finite-state machine for this schema is shown in figure 1.CS 752 Project Report Software-based and Hardware- based Branch Prediction Strategies and Performance Evaluation . 4 . Figure 1. The states in a two-bit branch prediction counter. The two-bit predictor schema uses only the recent behavior of a branch to predict the future behavior of that branch. Since sometimes in the program, the branch behavior of different instructions are related together, it is possible to improve the prediction accuracy if we also look at the recent behavior of other branches rather than just the branch we are trying to predict, which leads to GAg. 2.3. GAg In the GAg schema, the global history of the most recent m branches is recorded in an m-bit shift register, named global branch history register, where each bit records whether the branch was taken or not taken. We have another global branch history pattern table, which has 2m entries, each corresponding to the 2-bit counter for a global branch history. The prediction of a branch is based on the history pattern of the most Predict taken