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 since a 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. Because it is so critical to performance, branch prediction has been studied and steadily improved for decades. Microprocessor performance is projected to be flat for the foreseeable future, after decades of exponential growth. A breakthrough in branch predictor design would be transformational.
This project provides insight into why conventional branch predictors are limited. A whole 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. This project proposes 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. Together, these two principles are called EXACT, stands for EXplicit dynamic-branch prediction with ACTive updates.
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. Results with idealized implementations demonstrate such leaps in accuracy are possible and a first realistic implementation already achieves a significant fraction of this potential. To achieve broader impact, project participants will collaborate closely with industry partners, Intel and IBM, to translate EXACT technology into future microprocessor designs.
