Hazards

Situations that prevent starting the next instruction in the next cycle

Types

• Structural Hazard
  • A required resource is busy
  • Stalls for the cycle that the resource is busy
  • Ex: Trying to read instruction at the same time that memory is being written in a processor with a single memory interface
• Data Hazard
  • Need to wait for previous instruction to complete its data read/write
  • When two instructions depend on each other
  • Types:
    • Read after write: a = b + c, d = a + e
    • Write after write: a = b + c, a = d + e
    • Write after read: b = a + c, a = d + e
      • Only a problem if the second instruction is going through a shorter pipeline
  • Can still be somewhat optimized using forwarding
    • Not perfect because you can’t send data back in time
    • Those remaining stalls are called Load-Use hazard
• Control Hazard
  • Deciding on control action depends on previous instruction
  • You don’t know what next instruction to fetch if there is a conditional branch

Avoiding

• Forwarding
  • Reduces the impact of data hazards
  • Use result as soon as it is computed
  • Don’t wait for it to be stored in a register
  • Requires extra connections in the datapath
  • 
  • 
• Call Scheduling
  • Avoid data hazards by rearranging instructions
  • Modern compilers will automatically do this
• Branch Prediction
  • Avoids control hazards
  • Just start doing one of the branches before you know if you are going to branch or not
  • If the prediction was wrong, the pipeline is flushed to undo the guess
    • By the time that it realizes it was wrong, it should be able to be undone
  • The easiest prediction is just to move to the next instruction and not branch
  • More realistic branch prediction
    • Static branch prediction
      • Based on typical branch behavior
      • Ex: Loops normally loop
    • Dynamic branch prediction
      • Hardware measures actual branch behavior
      • Assume that the trend will continue
      • Uses a history table of branches taken
      • More often used (when the additional transistors are feasible)

Dynamic Branch Prediction

• Hardware measures actual branch behavior
• Assume that the trend will continue
• Uses a history table of branches taken
• More often used (when the additional transistors are feasible)
• Types of Tables
  • 1-bit
    • Branch table only keeps track of the last path taken
    • A loop with predict wrong the first and last repeat
      • This becomes a problem when the loop is inside of another loop and it adds up
  • 2-bit
    • Only change prediction on two successive mispredictions
    • 
    • Fixes the nested loop scenario

Stalls

• When you can’t avoid a hazard, a stall passes through the pipeline
• Also called bubbles because they flow through the pipeline
• How
  1. Force control values in ID/EX register to 0
     • Insert a NOP (no operation) either through hardware during runtime or by compiler beforehand
  2. Prevent update of PC and IF/ID register
     • Using instruction is decoded again
     • Following instruction is fetched again
     • 1-cycle stall allows MEM to read data for LDUI