Wisconsin Alumni Research Foundation

Information Technology
Information Technology
More Accurate Branch Predictor Circuit
WARF: P140330US01

Inventors: Mikko Lipasti, Dibakar Gope

The Wisconsin Alumni Research Foundation (WARF) is seeking commercial partners interested in developing a bias-free branch prediction method that outperforms state-of-the-art techniques.
A branch predictor is a digital circuit that attempts to direct traffic in an instruction stream. Branching is usually implemented with a conditional jump instruction, and branches may be ‘taken’ or ‘not taken.’

High-performance processors typically rely on branch predictors to continuously supply the core with a smooth flow of instructions. Without branch prediction the processor would have to wait until the conditional jump instruction has passed before the next instruction could enter the pipeline. Branch predictors attempt to avoid this delay by guessing whether the conditional jump is most likely to be ‘taken’ or ‘not taken.’

Prediction accuracy has improved using recently developed ‘neurally-inspired’ predictors. However, systems with moderate hardware budgets (e.g., 64KB) restrict these predictors from correlating beyond a few dozen branches. As some correlations may be more than a thousand branches apart, the predictors cannot perform to their potential.
The Invention
UW–Madison researchers have developed a more accurate branch prediction method by distinguishing between ‘biased’ and ‘non-biased’ branch instructions. Biased branches are consistently skewed towards one direction while non-biased branches resolve in both directions.

The new method filters out biased branches because they merely reinforce earlier prediction decisions. Favoring non-biased branches enables more far apart correlations and superior prediction accuracy.
  • Circuit can be implemented in branch predictor designs.
Key Benefits
  • Improves branch prediction accuracy
  • Enables more distant correlations (e.g., 2000 branches apart)
  • Overcomes implementation challenges of ‘gold-standard’ neural predictors
  • Employs practical and cost-effective hardware
Stage of Development
The researchers have performed highly promising simulations.
For current licensing status, please contact Jeanine Burmania at [javascript protected email address] or 608-960-9846