# 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, 2019 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.
– Maha
Jan 8, 2019 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, 2019 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.
– Maha
Jan 8, 2019 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)
– Maha
Jan 8, 2019 at 16:17

So, the reason why an incorrectly predicted branch can cause 3 stall cycles is because in this problem, it is stated: "Assume that branch outcomes are determined in the EX stage..." This means, that it takes us 3 clock cycles to determine whether or not a branch is taken. Going back to your scenario, you may be wondering how this applies to the TINS instructions, in other words, the target instructions. Looking at the very first TINS1, we can observe that it takes that instruction AT MOST 3 clock cycles before we branch off to INSNX. If you are wondering why, you must understand that our branch is predicted in the execution stage which is 3 CLOCK CYCLES. Therefore, if we branch to ISNX, we will have a penalty of 3 CLOCK CYCLES to flush out potentially 3 (TINS1, TINS2, TINS3) instructions. Please refer to page 308 figure 4.59 of Computer Organization by Patterson and Hennessy Risc-V edition to have a better visualization of what I mean. The problem is very similar. I hope this helps.

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?)


If you compare the problem description of Patterson & Hennessy's Computer Organization and Design Fourth/Fifth edition and that of MIPS 6th edition/RISC-V 1st/2nd edition, you will notice that later versions updated the problem description as "branch outcomes are determined in the ID stage and applied in the EX stage" to resolve the previous ambiguity. The comparison of registers, the determination of branch outcomes, or the branch test, are different from the decision about whether to branch, the application of branch outcomes, or the selection of branch. The determination and the application can be different or they can be the same, depending on the implementation.

This problem implicitly uses the implementation of the classic pipeline in the textbook, where the determination of the branch outcomes is in the EX stage and the application of the branch outcomes is in the MEM stage, i.e., to decide whether the branch is taken or not taken is still in the MEM stage. Given this assumption, it is clear that 3 stalls would be inserted, and 3 clock cycles of penalty are imposed (you can refer to Figure 4.61 of the fifth edition or Figure 4.59 of RISC-V 1st edition or Figure 4.63 of RISC-V 2nd edition).