current addressBTBSoftware-based and Hardware-based Branch Prediction Strategies and Performance EvaluationGang Luo ([email protected])Hongfei Guo ([email protected])AbstractThe SimpleScalar 3.0 branch prediction simulator implements a number of state-of-art branch prediction mechanisms. As regards to static branch prediction strategies, it supports branch always taken, and branch always not taken. For dynamic branch prediction strategies, it implements simple directly mapped bimodal predictor and two level adaptive branch predictor, which again includes GAg, GAp, PAg, and PAp.SimpleScalar 3.0 branch predictor assigns a branch target buffer associated with each dynamic branch predictor. It records the latest taken branches and their target addresses. The branch prediction simulator works in the following way:ReferencesCS 752 Project Report Software-based and Hardware- based Branch Prediction Strategies and Performance EvaluationSoftware-based and Hardware-based Branch PredictionStrategies and Performance EvaluationGang Luo ([email protected])Hongfei Guo ([email protected])AbstractIn a highly parallel computer system, performance losses due to conditional branch instructions can beminimized by branch prediction to fetch and issue subsequent instructions before the actual branchoutcome is known. This paper discusses several software-based static and hardware-based dynamic branchprediction strategies and uses the modified release 3.0 of the SimpleScalar simulation tool set to evaluatetheir performance. According to our test result, the hardware-based dynamic branch prediction strategiesalways achieve high prediction accuracy than the software-based static branch prediction strategies. 1. IntroductionIt is well known that in a highly parallel computer system, branch instructions can break the smooth flow ofinstruction fetching, decoding and execution. This results in delay, because the instruction issuing mustoften wait until the actual branch outcome is known. To make things worse, the deeper the pipelining is, thegreater 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 predictionmay lead to more delay because the wrongly fetched instructions occupy the useful functional units, likethe ALU, reservation stations, and memory bus. This leads to the need for highly accurate branch predictionstrategies.Branch prediction strategies can be divided into two basic categories: software-based static branchprediction strategy and hardware-based dynamic branch prediction strategy. . 1 .CS 752 Project Report Software-based and Hardware- based Branch Prediction Strategies and Performance EvaluationThe 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’tbe taken.4. Predict that all branches with certain operation codes will be taken; Predict that the others won’t betaken.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 usuallyhardware-based dynamic branch prediction strategies have better prediction accuracy compared to thesoftware-based static ones. In this paper, we discuss several representative software-based static and hardware-based dynamic branchprediction strategies. Due to the wide variation in branching behavior between different applicationprograms, there exists no good analytical model for evaluating the performance of the branch predictionstrategies. So we utilize the SimpleScalar Tool Set Version 3.0, which is a widely used simulation tool setdeveloped at the computer sciences department of University of Wisconsin-Madison, and some benchmarkprograms to do performance evaluation. . 2 .CS 752 Project Report Software-based and Hardware- based Branch Prediction Strategies and Performance EvaluationSince the meaning of the software-based static branch prediction strategies are quite obvious, we only needto present the meanings of the different hardware-based branch prediction strategies in detail. Then, insection 4, we analyze the performance of the different branch prediction strategies.2. Hardware-based Dynamic Branch Prediction Strategies2.1. One-bit Branch Prediction BufferThis is the simplest dynamic branch prediction schema. The branch prediction buffer is a small memoryindexed by the lower portion of the address of the branch instruction. It contains a bit that says whether thebranch was recently taken or not, which is the hint for the next branch instruction. If the hint turns out to bewrong, the prediction bit is inverted and stored back. This schema has a performance shortcoming: Even if a branch is almost always taken, we will likelypredict 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 CounterThe two-bit schema is a specialization of the n-bit schema. Since the two-bit predictors do almost as well asthe n-bit predictors, we just rely on two-bit branch predictors rather than the more general n-bit ones. Thetwo-bit predictor is essentially a two-bit counter which takes values between 0 and 3: when the counter isgreater than or equal to one half of its maximum value 2, the branch is predicted as taken; otherwise, it ispredicted 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. . 3 .CS 752 Project Report Software-based and Hardware- based Branch Prediction Strategies and Performance EvaluationFigure 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 ofthat branch. Since