I need help in understanding the solution from solution manual. The question is from the exercise 4.24.4 and 4.24.5 of chapter 4 in the book Computer Organization and Design by Patterson and Hannessey (4th edition). The question is about designing branch predictor.

Branch Outcome Pattern
(T for branch taken, NT for branch not taken)

Question A
Design a predictor that would achieve a perfect accuracy if this pattern is repeated forever. You predictor should be a sequential circuit with one output that provides a prediction (1 for taken, 0 for not taken) and no inputs other than the clock and the control signal that indicates that the instruction is a conditional branch.

Question B
What is the accuracy of your predictor from question A if it is given a repeating pattern that is the exact opposite of this one?

Solutions given are as follows:

Solution A
The predictor should be an N-bit shift register, where N is the number of branch outcomes in the target pattern. The shift register should be initialized with the pattern itself (0 for NT, 1 for T), and the prediction is always the value in the leftmost bit of the shift register. The register should be shifted after each predicted branch.

Question B
Since the predictor’s output is always the opposite of the actual outcome of the branch instruction, the accuracy is zero.

Now I have doubt with solution to problem B. If we have 5 bit left shift register initialized with the pattern T,NT,T,T,NT (T=1,NT=0) and if the branch outcomes are reverse: NT,T,T,NT,T, then the prediction will be correct for the middle (3rd prediction/branch instruction result) T, right? So the accuracy would be at least 20% (1/5). Then why the book says it will be zero?

I know this is a very simple question, but still am not getting it.... :\


I guess the question meant the exact opposite with respect to the values, not the order. So the opposite of T,NT,T,T,NT in this sense is NT,T,NT,NT,T. Note that this is different from what you thought the opposite.

| improve this answer | |
  • \$\begingroup\$ ok thats what it looks like \$\endgroup\$ – Maha Jul 9 '17 at 19:02

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.