Control Hazard
//Unconditional branch
Monday, August 09, 2021 3:45 PM
ADD R1, R2, R3
Critical situation that is arises due to branch instruction . JMP Level
AND R6, R7
As branch instruction changes the program control to execute the next instruction from the target -
address and deciding the target address for the branch take place after decoding stage so this .-
makes delay the pipeline. -
-
Branch Instruction Unconditional both change the value of PC Level SUB
Conditional incase of conditional branch PC will change MUL
PC <--- branch target address[if cond true]
Conditional
ADD R1, R2, R3
BNE R4, R5, LOOP
AND R6, R7
-
.-
-
-
Loop SUB
MUL
Technique Used to handle the branch hazard :
: Freeze or flush
: Prediction based Technique
: Delayed slot
Freeze or flush : In this technique after the branch instruction enter into the pipeline , pipeline is freeze /blocked and new
instruction must enter after the completion of decoding phase of branch so that branch successor address can be found
: One stall or delay must arises in this technique because as we know the branch successor only after decoding the
Branch instruction
Prediction Based Technique :
i. Prediction Not Taken Method
ii. Prediction Taken method
i. Not Taken or Untaken Prediction Method :
Here the prediction assume that the branch condition will never be executed
If prediction is set as untaken then the branch instruction is just treated as the Conditional branch
Normal instruction and after branch enter into pipeline then next instruction ADD R1, R2, R3
entered into pipeline. BNE R4, R5, LOOP
AND R6, R7
If branch prediction is mis predicted then restart the pipeline and start fetch instruction -
From branch target. This is schown in below figure. .-
-
-
Loop SUB
MUL
Dr Anuja Kumar Acharya Page 1
i. Prediction Taken method : Prediction is that branch will always be executed .
Assumption is branch condition is true and according to this prediction is true. Generally this technique is not
used as branch target is estimated in decoding stage but some machine use complex hardware to know branch
address prior to decoding
Complex hardware is used for calculating the branch target address in fetch part of the branch instruction
Ex: Prefetching buffer
Conditional branch
ADD R1, R2, R3
BNE R4, R5, LOOP
AND R6, R7
-
.-
-
-
Loop SUB
MUL
Delayed slot : A better approach is the delayed slot technique in which an independent instruction which is
not depend on the branch instruction is pushed into the branch delayed slot.
Delay slot : Gap of 1 cycle between the branch and the branch successor
Dr Anuja Kumar Acharya Page 2
Assume the ideal CPI of a 5stage pipeline is 1.0 and branch cause 1 cycle penalty in pipeline. If 30% instructions are
Unconditional branch instruction then find the speedup gain in pipeline wrt to unpipeline
Speedup =
Performance of pipeline Avg Inst time in un pipeline
---------------------------- = ----------------------------------
Performance of un pipeline Avg. Instr time pipeline
= No of stage of pipeline 5
-------------------------------- = ------------------------------
1+ stall cycles per instruction in the pipeline 1 + 0.3
= 5/1.3 = 3.8462
Assume the ideal CPI of a 5stage pipeline is 1.0 and branch cause 1 cycle penalty in pipeline. If 30 % instructions are
conditional branch instruction. If prediction not taken scheme is used and it is observed that 50% is mis predicted then
find the CPI of the pipeline
CPI of the pipeline = Ideal CPI + stall cycles per instructions
Stall cycles per instruction for the conditional branch instruction
= 30 % X 50/100 = 0.15
CPI of the pipeline = 1.0 + 0.15 =1.15
Assume the ideal CPI of a 5stage pipeline is 1.0 and branch cause 1 cycle penalty in pipeline. If 30 % instructions a re conditional
branch instruction and 20 % instructions are unconditional. If prediction not taken scheme is used and it is observed that 50% is mis
prediction rate for branch then find the CPI of the pipeline and also the pipelin2 speed up
CPI of the pipeline = Ideal CPI + stall cycles per instructions
Stall cycles per instruction for the conditional branch instruction
= stall cycle for unconditional branch + stall cycles for conditional
= 20 % X 1 + 30 % X50% X1
= 0.2 + 0.3 X 1/2 X1 = 0.35
CPI of the pipeline = 1.0 + 0.35 =1.35
Speedup = 5/1.35=3.7037
Dr Anuja Kumar Acharya Page 3
CPI of the pipeline = 1.0 + 0.35 =1.35
Speedup = 5/1.35=3.7037
Assume the ideal CPI of a n stage pipeline is 1.0 and branch cause 1 cycle penalty in pipeline. If 20 % instructions
are conditional branch instruction and 10 % instructions are unconditional. If prediction not taken scheme is used
and it is observed that 25% is mis prediction rate for branch then find the depth of the pipeline if speedup of the
pipeline is 4.
Dr Anuja Kumar Acharya Page 4