Homework answers / question archive / 1

1

Computer Science

Share With

---

1.The importance of having a good branch predictor depends on how often conditional branches are executed. Together with branch predictor accuracy, this will determine how much time is spent stalling due to mispredicted branches. In this exercise, assume that the breakdown of dynamic instructions into various instruction categories is as follows:

 

R-Type BEQ JMP LW SW

40% 25% 5% 25% 5%

 

Also, assume the following branch predictor accuracies:

 

Always - Taken Always-Not-Taken 2-Bit

40% 60% 85%

 

1.1, Stall cycles due to mispredicted branches increase the CPI. What is the extra CPI due to mispredicted branches with the always-taken predictor? Assume that branch outcomes are determined in the EX stage, that there are no data hazards, and that no delay slots are used.

 

Number of stall cycles due to mis-predicted branches 3

Breakdown of dynamic instruction into BEQ = 25% = 0.25

Accuracy of the predicted branches with Always-Taken predictor = 45% = 0.45

Accuracy of the mis-predicted branches with Always-Taken predictor = 100.0 - 0.45 0.55

Therefore, Extra CPI due to mis-predicted branches with Always-Taken predictor = 3 *0.55 *0.25 0.4125

 

1.2, Repeat 4.15.1 for the "always-not-taken" predictor.

Explanation:

If we stall for 1 cycle for each wrong prediction, here is the time wasted in each of the cases:

Case 1: Always-taken:

Accuracy: 40% => 60/100 * Number of beq instructions have stalls = 0.6*0.25 stalls/instruction

= 0.15 stalls/instruction

Case 2: Always-not-taken:

Accuracy: 60% => 40/100 * Number of beq instructions have stalls = 0.4*0.25 stalls/instruction

= 0.1 stalls/instruction

Case 1: 2-bit:

Accuracy: 85% => 15/100 * Number of beq instructions have stalls = 0.15*0.25 stalls/instruction

= 0.0375 stalls/instruction

Hence there is a large amount of time wasted installing due to wrong predictions.

 

1.3, Repeat 4.15.1 for the 2-bit predictor.

 

Extra CPI

3*(1-0.85)*0.25=0.113

 

1.5, With the 2-bit predictor, what speedup would be achieved if we could convert half of the branch instructions in a way that replaced each branch instruction with two ALU instructions? Assume that correctly and incorrectly predicted instructions have the same chance of being replaced. 

 

need answered 1.4 and 1.6

 

1.4, With the 2-bit predictor, what speedup would be achieved if we could convert half of the branch instructions in a way that replaces a branch instruction with an ALU instruction? Assume that correctly and incorrectly predicted instructions have the same chance of being replaced.

 

1.6, Some branch instructions are much more predictable than others. If we know that 80% of all executed branch instructions are easy-to-predict loop-back branches that are always predicted correctly, what is the accuracy of the 2-bit predictor on the remaining 20% of the branch instructions?