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

Question

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?

Answer 1

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

Answer 2

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