# How many stall cycles resulted by incorrectly predicted branch in instruction pipelining

I have been solving following exercise problem from book Computer Organization by Patterson and Hennessy:

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:
Also, assume the following branch predictor accuracies:

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.

The solution given was:

Each branch that is not correctly predicted by the always-taken predictor will cause 3 stall cycles, so we have:

Doubt

I was thinking how incorrectly predicted branch can cause 3 stall cycles? I was able to guess only 2 stall cycles. Consider instruction sequence:

BEQ R1, R2, Label
INSNX
INSNY
:
:
Label: TINS1
TINS2


Where,

• BEQ is branch if equal instruction.
• TINS means target instruction.
• INSN means instructions next to BEQ.

Consider that "static branch taken predictor" is used which always prefetches branch target instruction, thinking branch will always be taken. However, assume that the prediction fails and the prefetched two instructions needs to be discarded. Shouldnt this execution cause two stall cycles as explained below:

BEQ       F   D   E
TINS1         F   D   X        (Branch Taken prediction, target instruction prefetched,
but prediction failed, thus instruction cancelled)
TINS2             F   X        (prediction failed, thus instruction cancelled)
INSNX                 F   D... (Instruction after BEQ executed)

|<--->|           (Two instructions cancelled.
Isnt this equals two stall cycles?)


Isn't this proves incorrectly predicted branch result in 2 stall cycles? What I am missing?

• Could you refer to the page(s) and the edition of the book? And have you considered (or should you? I don't know...) a cycle for updating the branch predictor itself (this is a 2-bit predictor, so the state must be updated, yes?) – jonk Jan 8 at 16:00
• Nope neither I in the bottom most explanation nor the book solution considered cycle for updating the branch predictor. In fact I wasnt aware of necessity of such cycle as I never came across such problem. However I dont think we have to consider it here as the problem explicitly says "What is the extra CPI due to mispredicted branches with the always-taken predictor?" (Second last line in first quote.) The "always taken predictor" is a static predictor which assumes that branch will always be taken. – anir Jan 8 at 16:07
• What made me ask you is that I also see in your question the "2 bit" column in a table there. However, I also see that those percentages in that table aren't applied, either. So, I guess I must take your point about the static predictor use. My mistake. I'd still like to know which edition and which page. – jonk Jan 8 at 16:12
• [...continued from last comment] I am solving Exerscise 4.23.1 (page 431) from Computer Organization And Design (The Hardware / Software interface), 4th edition by Patterson and Hennessy. The same problem is there in the book Computer Organization and Design RISC-V Edition: The Hardware Software Interface by Patterson and Hennessy but at Exercise 4.28. – anir Jan 8 at 16:16
• Its the group of questions which involves other predictors related questions also. I am stuck with this specific one. (edition and page in earlier comment) – anir Jan 8 at 16:17