1 (50 pts) For the following repeating pattern (e.g., in a loop) of branch outcomes:
NT, NT, NT, T, T, NT, NT, NT, T, T
a. (10 pts) What is the accuracy of always-taken and always-not-taken predictors
for this sequence of branch outcomes?
b. (20 pts) What is the accuracy of a one-bit predictor assuming the predictor starts
in the predict-taken state. What is the accuracy of this predictor if this pattern
repeats forever?
c. (20 pts) What is the accuracy of a two-bit dynamic branch predictor assuming
that the predictor starts off in the weakly predict-not-taken state? What is the
accuracy of this predictor if this pattern is repeated forever?
2. (30 pts) Briefly discuss the BHT (Branch History Table) and BTB (Branch
Target Buffer). Please cover the following aspects in your answer:
What are they used for? What are the entries in them? How to get the right entry in
BTB and BHT (addressing)? How BTB and BHT work together to do branch
prediction?
3. (20 pts) Assume the 2-bits branch predictor accuracy is 85%. 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?
