Let's say that conditional branches are resolved at the 2nd-stage on a 4-stage pipeline. Why is there different penalties on a taken branch versus an untaken branch ? Should the penalty be the same for both? I always assumed that the not taken and taken branch penalty is 2 cycles but this is incorrect according to my friend. Could someone clarify this ?
Ideally there are two possible branch outcomes which are unconditional and conditional branches.Conditional branches normally include a branch that can either be taken or not taken. Unconditional branches are usually known as jump or goto instructions.
Jump instructions in a 4-stage pipeline
Assuming that jumps can be resolved on the 2nd-stage (for a normal IF,ID,EX,WB) and that 1th-stage can always be done independently. This as a penalty will include 1 stall cycle. The main reason is simply because the pipeline fetches the next instruction following the jump(IF must update the PC , and the next sequential address is the only address known at this point). Now at the 2-stage when the jump resolves and realizes that the the fetch it issued was awrong address . The scenario will change,meaning that the pipeline will re-issue the fetch of the available instruction in the next cycle ( i + 1 ) causing one-cycle stall.
branch instructions taken in a 4-stage pipeline
Assuming that branches are resolved at the 3th-stage the pipeline then realizes taht it must reissue the fetch for the next instruction ( assuming the next instruction is not directly the branch) thus creating two-cycle stalls.
branch instructions not-taken in a 4-stage pipeline
For not taken branches the fetched instruction that is after the branch is actually correct because the branch is false ( meaning the instruction after it will execute). Mentioning that branches are resolved at the 3th-stage the pipeline then realizes that it doenst have to reissue the fetch and can therefore resume execution the instruction that was fetched after the branch. However the branch instruction cannot leave the 1th-stage (IF) since it has to resolve the branch thus including a penalty of 1 cycle.
Here is a picture showing every scenario: