Stall Penalty

• When the CPU encounters a branch instruction, it cannot fetch the next instruction until the outcome of the branch is determined (whether the branch is taken or not).
• During this time, the CPU may remain idle, leading to a stall and wasted CPU cycles, as the pipeline cannot proceed without the result of the branch.

Control Hazard (Branch Hazard)

• A control hazard occurs when the pipeline cannot determine which instruction to fetch next because it depends on the outcome of a branch instruction.
• In the example below, the next instruction to be executed depends on whether the condition a < b is true or false:

  if (a < b) {
      result = a + b;
  } else {
      result = a - b;
  }
  

• If the branch outcome is unknown right away, the pipeline may have to stall, causing inefficiency.

Branch Prediction

• Branch prediction is a technique to mitigate the stall penalty by predicting the outcome of a branch instruction.
• The longer pipeline, the more expensive the stall penalty.
• The decision on which control action to take (e.g., whether the branch is taken or not) often relies on the outcome of previous instructions.
  • If the prediction is correct, the pipeline continues smoothly.
  • If the prediction is incorrect, the pipeline must discard or "flush" the wrong path instructions and restart from the correct instruction, which introduces further delays.

Static Branch Prediction

Static branch prediction relies on fixed rules or heuristics, rather than dynamically adjusting based on past behaviors. For common patterns like loops and if statements, certain realistic strategies can be used:

Loop Branches (Backward Branch Prediction)

• Common Heuristic: Predict that backward branches (i.e., branches that loop back to a previous instruction) are always taken.

• Reasoning: In loops, backward branches are often used to repeat iterations until the terminate condition is satisfied (e.g., in for or while loops). The loop typically executes multiple times, so it makes sense to predict that the backward branch will be taken.

  • Example: In a for loop:The branch instruction at the end of the loop will jump back to the beginning if the terminate condition holds. A static predictor assumes the branch is taken (i.e., the loop continues) until the condition becomes false.

    for (int i = 0; i < 10; i++) {
        // loop body
    }
    

If-Else Statements (Forward Branch Prediction

• Common Heuristic: Predict that forward branches (branches moving ahead in code) are not taken.
• Reasoning: Forward branches typically occur in conditional statements (if conditions) where the code jumps ahead only if the condition is met. Since conditions are often designed to evaluate to false under default or common scenarios, static prediction assumes the condition will not be met.
  • Example:A static prediction might assume that the if condition is false, so the default path is the "else" block, and no branch will be taken.

    if (a < b) {
        // taken branch (forward)
    } else {
        // not taken branch (fallthrough)
    }
    

Jump Table from Complex Branches

Branch Prediction and Control Flow

In complex if-else and switch statements, multiple branches increase the likelihood of branch mispredictions, leading to performance penalties. Each condition introduces a branch, making outcomes harder to predict.

Jump Tables: Reducing Branches

Jump tables map variable values directly to memory addresses of the target code blocks, eliminating the need for multiple conditional branches. This reduces mispredictions and simplifies control flow.

Benefits of Jump Tables

• Fewer Branches: Only one indirect jump is needed, reducing the chance of mispredictions.
• Constant Time: Jump tables provide O(1) access to code blocks, improving performance over O(n) if-else comparisons.
• Smoother Pipelines: Fewer stalls from branch misprediction.