CSE-211_PART_4

 

Topic Covered: Branch Cost Motivation,Branch Prediction Introduction,Static Outcome Prediction,Dynamic Outcome Prediction,Target Address Prediction

1. Branch Cost Motivation

• Pipeline Stalling: Branches cause delays because the processor may fetch and partially execute instructions that it later discards if the branch takes a different path. This delay in the pipeline is known as a stall.
• Branch Cost Reduction Techniques: The primary methods to reduce branch cost include branch prediction, speculative execution (where instructions are executed ahead of time), and branch delay slots (reordering instructions to fill the delay).
• Cost Implications: Without good branch prediction, high misprediction rates lead to increased CPU cycles, slowing down the overall execution. The motivation to reduce branch cost is to improve instruction throughput and minimize idle CPU time.

Two types of Prediction                                                                                                                                     

    1. Predict Branch Outcome     2. Predict Branch/Jump Address

1. Predict Branch Outcome

This type of prediction involves guessing whether a branch will be taken or not taken. The processor uses historical data to make this prediction. If the prediction is correct, the pipeline continues without interruption. If incorrect, the pipeline must be flushed, and the correct path must be fetched, decoded, and executed, which can cause delays.

2. Predict Branch/Jump Address

This prediction involves guessing the target address of a branch or jump instruction. Accurate prediction of the target address allows the processor to fetch the next instruction without delay. This is often done using a branch target buffer (BTB), which stores the target addresses of previously taken branches.

• Types of Branch Prediction

  1. Static Branch Prediction 2. Dynamic Branch Prediction

3. Static Outcome Prediction

• Static outcome prediction is a branch prediction technique where the CPU makes a fixed assumption about how branches will behave during execution. This prediction does not rely on previous execution history but uses predefined assumptions that are consistent for all branches. Static prediction is simple and does not require additional hardware complexity, but its accuracy is limited, especially for programs with unpredictable branching behavior.

  Mechanism of Static Prediction

  In static outcome prediction, the CPU predicts branches based on a set rule, which does not change dynamically. The most common types of static branch prediction are:

  1. Always Taken:

     • Assumption: The CPU assumes that every branch will be taken.
     • How it works:
       • The processor always predicts that the branch will be executed (i.e., the code inside the branch will run).
       • This is particularly effective in loops, where the program frequently jumps to the start of the loop (i.e., a backward branch).
     • Best suited for: Programs with loops that continuously jump back to the beginning of the loop.

  2. Backward Taken, Forward Not Taken (BTFNT):

     • Assumption: The CPU assumes that backward branches (often loops) will be taken, and forward branches (like if statements) will not be taken.
     • How it works:
       • Backward branches: These are branches that go back to a previous instruction, commonly seen in loops (e.g., for or while loops). The CPU predicts that these branches will be taken, as loops tend to repeat.
       • Forward branches: These are branches that move forward in the program (e.g., if-else conditions). The CPU assumes these will not be taken, as they often represent conditional decisions that do not lead to an immediate branch.
     • Best suited for: Programs that contain many loops (backward branches) and fewer if-else type conditionals (forward branches).

  Advantages of Static Prediction

  1. Simplicity

  2. No Additional Hardware Required:

  3. Low Power Consumption:

  4. Effective for Programs with Predictable Patterns

  Drawbacks of Static Prediction

  1. Limited Accuracy in Unpredictable Programs:

     • The main limitation of static prediction is that it doesn’t adapt to varying program behavior. For example:
       • If the branch behavior changes (e.g., the loop exits more often than expected), the fixed assumptions of static prediction become inaccurate, leading to performance loss.
       • If-else statements with unpredictable conditions will be mispredicted, especially if the branches don't follow the assumption that forward branches are rarely taken.

  2. Poor Performance in Complex or Irregular Branching:

     • In programs with irregular or complex branching patterns (e.g., a mix of loops and conditional branches), static prediction might lead to frequent mispredictions, causing pipeline stalls and wasted cycles.

  3. Inefficient for Programs with Non-Loop Conditional Branches:

     • For programs that do not contain many loops (e.g., programs dominated by if-else statements), static predictions like Always Taken or BTFNT will be inaccurate, resulting in poor performance.

  Example Scenarios:

  1. Loop (Backward Branches):

     • In a program that processes a list or array with a loop that iterates multiple times, static prediction (using Always Taken or BTFNT) works well because loops often represent backward branches. These backward branches are typically taken, so the processor will benefit from correct predictions most of the time.

     Example:

     c
     
     for (int i = 0; i < n; i++) {
         // Do something
     }
     

     • Here, the branch (loop) will likely always be taken, so static prediction like Always Taken or BTFNT will perform reasonably well.

  2. Conditional Branches (Forward Branches):

     • In cases where the program has conditionals with unpredictable outcomes, such as if statements that depend on runtime conditions, static prediction will likely be wrong. If a forward branch is incorrectly predicted to be not taken, the CPU will fetch incorrect instructions, resulting in wasted cycles.

     Example:

     c
     if (x > 50) {
         // Do something
     } else {
         // Do something else
     }
     

     • Static prediction like Always Taken or BTFNT may mispredict the outcome, especially if the branch is unpredictable.

4. Dynamic Outcome Prediction

• Overview: Dynamic prediction uses runtime information, based on past executions of the branch, to make predictions. It’s generally more accurate than static prediction because it adapts to actual program behavior.
• Branch History Table (BHT): A common implementation where each entry records the last outcome of a branch. If the branch was taken the last time, it predicts "taken" again.
• Two-Level Predictors: These are more advanced and include:
  • Local History Prediction: Uses the history of a specific branch.
  • Global History Prediction: Uses the outcome history of all branches, stored in a Global History Register (GHR).
• Tournament Predictors: Combine multiple predictors (like global and local) and dynamically select the best-performing one based on past accuracy.

5. Target Address Prediction:

• Target address prediction is a technique used to predict the destination address of branch and jump instructions. This is crucial for maintaining the flow of instructions in the pipeline and minimizing delays caused by control hazards. Here are some key methods used for target address prediction:

  1. Branch Target Buffer (BTB)

  The Branch Target Buffer (BTB) is a cache that stores the target addresses of recently executed branch instructions. When a branch instruction is encountered, the processor checks the BTB to see if the target address is already known. If it is, the processor can immediately fetch the next instruction from the predicted address, reducing the delay.

  2. Return Address Stack (RAS)

  The Return Address Stack (RAS) is used to predict the return addresses of function calls. When a function call is made, the return address is pushed onto the stack. When the function returns, the address is popped from the stack, providing an accurate prediction of the return address.

  3. Indirect Branch Prediction

  Indirect branches, such as those used in virtual function calls or switch statements, can have multiple possible target addresses. Predicting the target address for indirect branches is more complex. Techniques like using a history table that records the target addresses of indirect branches based on the branch history can be employed.

  How It Works

  1. Instruction Fetch: When a branch or jump instruction is fetched, the processor checks the BTB for a matching entry.

  2. Prediction: If a matching entry is found, the target address is predicted, and the next instruction is fetched from this address.

  3. Execution: The branch or jump instruction is executed, and the actual target address is determined.

  4. Update: The BTB is updated with the actual target address if the prediction was incorrect.

  Benefits

  • Reduced Pipeline Stalls: Accurate target address prediction reduces the number of pipeline stalls caused by control hazards.

  • Improved Performance: By fetching the correct instructions earlier, the overall performance of the processor is improved.

  Challenges

  • Accuracy: The accuracy of target address prediction is crucial. Incorrect predictions can lead to pipeline flushes and wasted cycles.

  • Complexity: Implementing effective target address prediction mechanisms adds complexity to the processor design.