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:
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
BEQis branch if equal instruction.
TINSmeans target instruction.
INSNmeans instructions next to
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?