control hazards

Summary

Control dependency

• when one instruction determines whether another gets executed
• need to wait for branch decision

beq  $1, $3, A  # suppose branch is taken
and $12, $2, $5
or  $13, $6, $2
add $14, $2, $2
A:
lw  $4,  5($7)

• solution: stalling
  • branch decision in MEM

stalls will add up over time, around 20% of code is some kind of brancing

• solution: branch predition (guess branch-not-taken)
  • branch taken -> wrong guess
  • branch decision in ID

• solution: branch predition (guess branch-taken)
  • branch taken -> correct guess
  • branch decision in ID

Delayed branch

• do something else while waiting for the branch decision

or  $8, $9, $10
add $1, $2, $3
sub $4, $5, $6
beq $1, $4, Exit # RAW with add, sub, but not with or
xor $10, $1, $11 

add $1, $2, $3
sub $4, $5, $6
beq $1, $4, Exit 
or  $8, $9, $10  # moved here since it gets executed regardless of branch decision
# if branch is taken, do it after the or
xor $10, $1, $11 

Concept

Control hazard

• control dependencies between instructions
• during branching

Branch decision

• made during the MEM stage
• or with early resolution in the ID stage

Reducing branch penalty

• early branch resolution
  • move branch decision to an earlier stage
• branch prediction
  • guess an outcome
• delayed branching
  • do some other computation while waiting for the branch decision

Application

Pipeline from MIPS code

lw $s2, 0($s1)    # suppose branch is taken
bne $s2, $s3, L1
sub $s0, $s4, $s5
L1:
add $s0, $s0, $s3

• branch-taken, decision at ID
  • correct guess

beq/bne need their operands by ID during early branching

• branch-not-taken, decision at MEM
  • wrong guess

we cant use the non branched add since it gets its value from sub, which could result in a different value