Newsroom

Eric Rotenberg

Eric Rotenberg has been awarded $206,330 by the National Science Foundation for research on Explicit Dynamic-Branch Prediction with Active Updates.

The award will run from September 15th, 2009 to August 31st, 2012.

Research Abstract - A computer program consists of many low-level instructions that are executed by a microprocessor. The key to executing a program faster is executing more instructions in parallel. Branch instructions hinder this process. A branch instruction is a decision, whose outcome determines the next instruction to be executed. Thus, the branch must be executed before subsequent instructions can be executed. A microprocessor attempts to circumvent this constraint by predicting the outcome of the branch, enabling instructions from the predicted target to be executed speculatively and without delay.

Branch predictors proposed over the years are clever variations of the same basic approach and the accuracy of this approach only scales to a point. A breakthrough in branch predictor design would be transformational. It would not only have immediate performance scaling benefits for microprocessors today, but would also free designers to reinvent how microprocessors execute programs.

This project provides insight into why conventional branch predictors are limited. A new direction in branch predictor design is revealed by this understanding. Two interrelated problems are exposed: 1) conventional predictors often fail to distinguish dynamic branches for which specialized predictions are required, especially memory-dependent branches, and 2) explicitly specializing predictions for these dynamic branches does not fix the problem alone, because stores to their dependent memory addresses change their future outcomes anyway. We propose two unprecedented principles for branch predictor design: first, explicitly identifying dynamic branches in order to provide them with specialized predictions and, second, actively updating their predictions when stores occur to their dependent memory addresses. The goal of the proposed research is to apply these two principles to design predictors that achieve leaps in branch prediction accuracy, halving or more than halving the number of mispredictions with respect to the best known predictor.