Lecture on Branch Prediction

Introduction

• Sparse attendance, possibly due to a party or event.
• Discussing a tough but important topic: branch prediction.
• Importance of improving branch prediction to keep pipelines full without stalling the fetch engine.

Branch Prediction Overview

• Branch Prediction: Predicting the direction of branches in instruction pipelines.
• Importance demonstrated: even with 90% accuracy, fetch IPC is only 1.66 (aim is 5), with 200% extra instructions fetched.
• Challenge: Achieving higher than 90% accuracy in difficult workloads.

Techniques in Branch Prediction

Basic Concepts

• Branch Target Buffer (BTB): Used to guess the next fetch address.
• Direction Predictor: Determines if a branch was taken/not taken the last time it was executed.

Static Branch Prediction Methods

1. Always Not Taken: Low accuracy (30-40%).
2. Always Taken: Better accuracy (about 60%).
3. Backward Taken, Forward Not Taken: Slightly better.
4. Profile-based Prediction: Uses compile-time profiling data to predict branches.
5. Program-based Prediction: Uses heuristics based on program analysis.
6. Programmer-based Prediction: Programmers provide hints (pragmas) on branch likelihood.

Dynamic Branch Prediction

• Last Time Predictor: Predicts the same outcome as last execution.
  • Problematic due to quick changes in state with a single opposite outcome.
• Two-bit Counter/Two-bit Saturating Counter: Adds hysteresis, meaning the predictor doesn't change state quickly.
  • Results in better accuracy and energy savings.

Advanced Branch Prediction

Two-Level Branch Prediction

• Global Branch Correlation: Utilizes recently executed branch outcomes for prediction.
• Local Branch Correlation: Correlates a branch's outcome with its past outcomes.

Hybrid Branch Predictors

• Combines multiple types of predictors for better accuracy.
• Alpha 21264 Example: Combines global and local predictors, with a choice predictor to select between them.

Perceptron Branch Predictor

• Uses machine learning to learn correlations between branch history and outcomes.
• More complex and accurate, enabling long history lengths.

TAGE Predictor

• Uses multiple history lengths to improve prediction accuracy.
• Implemented in AMD and Intel processors.

Additional Concepts

Branch Confidence Estimation

• Estimates if the current prediction is likely correct.
• Useful for speculative execution and pipeline gating.

Loop Predictors

• Specialized for detecting and predicting loops with predictable iteration counts.

Conclusion

• Branch prediction remains a critical area of study with ongoing research and contests to improve methods.
• Techniques discussed range from simple static methods to complex dynamic predictors using machine learning.

Backup Concepts

• Delayed Branching and other branch handling techniques exist but are less dominant compared to prediction methods.

These notes cover the essential concepts and details discussed in the lecture, providing a comprehensive overview of branch prediction techniques and their applications in modern computing systems.