Control Hazards

• Chapter 4.9
• Static Branch Prediction
  • Predict branch not taken;
    • Easy default
    • Just do what we are doing, and continue to fetch instructions.
    • But we may have to flush instructions not needed.
    • The number depends on when we know we are going to branch
  • Predict branch taken
    • As the program executes, keep a table of where the branches are and the destinations.
    • If we load that address in the table, set the pc to be the target address.
    • But we might have to flush these instructions and reset the pc.
    • The number depends on when we know we didn't branch.
  • Which of these two schemes are best?
    • Neither.
    • Basic While Loop

      • top:
            beq  r1, r2, OutOfLoop 
            calculations
            b top
        OutOfLoop:
        

      • In this case, we should select branch not taken.
      • The repeat until

      • top:
           calculations
           beq r1, r2 top
                       

      • IN this case, I would assume branch taken is the choice.
      • What about if

        •     beq r1, r2, else
                  then code 
                  b done
          else:
                  else code
          done: 

        • Depending on the code, but probably wrong 50% of the time.
• When can we predict that a conditional branch is taken?
  • This has changed immensely in my life time.
  • Easy choice is after the instruction has finished ALU
    • But we have three bad instructions in the pipeline then
    • A three pipeline stall is bad.
  • We could possibly move this to the beginning of ALU by adding more hardware
    • During ID we could fetch the two register values we want to compare.
    • And add a simple ALU (subtractor) to determine if the values are equal.
    • And calculate the target address at this phase as well.
    • Because Moore's Law .
    • At the end we still have fetched the instruction immediately following the branch.
    • And this would still be subjects to data hazards.
• An old, but reasonable solution is a branch delay slot
  • Like the load delay slot, just have the compiler stick some instruction following the branch that should be executed no matter what.
  • This is ok for a 5 stage pipeline, but not good for a longer pipeline.
• Dynamic branch prediction.
  • Like static, we build a table.
    • Address of branch.
    • Some bits to indicate historical branch results.
    • Address of destination.
  • Based on the prediction bits, we change the pc appropriately.
  • 1 bit predictor
    • Assume a while loop that, predict taken or not taken

      • top:
            bne r1, r2, endOfLoop
            code 
            b top
        endOfLoop: 

      • Assume 0 means not taken and it the value of the bit at start
      • It will predict correctly all but the last time.
      • When it will be flipped.
      • But the next time through it will be wrong as well.
      • So two mis-pedictions.
    • How about this code however

      •     beq r1 r2, else
               then code
               b doneIf
        else: 
              else code
        doneIf: 

      • But the code is something like

        • for(i = 0; i < 10; ++i) {
              if (i %2) {
              } else {
              }
          }

      • It will be right perhaps the first time.
      • Then after that it will be wrong, so it will flip the bit
      • Then after that it will be wrong, so it will flip the bit...
  • A two bit predictor does better.
  • Look at figure 4.63 page 334.
    • While loops will only be wrong on exit, not exit and enter.
    • If statements like the one above will be wrong 50% of the time.
• They mention several other methods.
• "There are more transistors in the branch predictor of modern microprocessors than there were in the who first MIPS chps!"