branch-prediction-visualization

Tool for visualizing and comparing different dynamic branch prediction methods for a pipelined processor.

Currently only shows branch direction predictions (taken or not taken), not branch target address predictions or branch instruction predictions (determining whether instruction is branch), since these can generally be done efficiently for direct branches with a branch target buffer (BTB) and return address stack (RAS) for function returns.

Note that this tool is simply to be used for visualizing and better understanding branch prediction accuracy of different branch prediction methods under different branch patterns, not for rigorous testing for comparison between the methods.

Branch prediction methods covered

Compare between simple n-bit saturating counters or simulate custom branch predictor with the following architecture and choices:

• BHT entry types
  • n-bit saturating counters
  • n-bit agree predictor (bias bit set based on first direction)
    • The "Bias Bit Table" displayed would likely be part of the BTB or I-cache.
• Indexing methods for BHT
  • PC
  • GHR
  • GHR XOR PC (GShare)
  • PHT entry XOR PC (PShare)
  • PC index PHT, PHT entry index BHT (Local History)
• Input: list of (PC of branch instruction, T or NT)

Other

Ideas to (maybe) implement and more state-of-the-art prediction methods.

• Perceptron branch prediction
• Multiple predictors
  • Meta predictor; predictor for predictors (e.g. Alpha 21264 Tournament Predictor)
  • Majority vote method (skewed), predictor fusion, partial tagging, adder tree
• Alloyed-history predictors: concatenate local and global history to use as index
• Geometric history length predictors: TAGE, O-GEHL
• n by n predictors: Multiple arrays of predictors, use PC to select index, then use GHR to select array.
• YAGS
• Detect loop branch and count iterations (Intel Pentium M)
• Additional features
  • More misprediction stats (e.g. input a # of stages to flush for each misprediction, and it'll tell you the slowdown rate compared to perfect prediction)
  • Sample T/NT patterns representing loop branches, dependent branches, etc. to show how different methods are better in certain cases.
  • More diagram-like UI

Usage and Dependencies

Make sure Tkinter and pillow are installed, and launch/run main.py with Python 3.X.
Below is an example simulation of branch instructions using the Local History prediction method, with a 16-entry local pattern history table and 8-entry branch history table.
Example text files are provided in examples/ for simulating branch instructions from a file upload. PC values can be of any length. See examples/README.md for more details.

References

• McFarling, "Combining Branch Predictors," DEC WRL Technical Report, 1993.
• Sprangle et al., "The agree predictor: a mechanism for reducing negative branch history interference," ISCA 1997
• Yeh and Patt, "Two-Level Adaptive Training Branch Prediction," MICRO 1991.
• ECE 3058, GT HPCA, and CMU 18-740 lectures.