SHF:Small: EXACT: Explicit Dynamic-Branch Prediction with Active Updates

计算机程序由许多由微处理器执行的低级指令组成。更快地执行程序的关键是并行执行更多的指令。分支指令会阻碍这一过程，因为必须在执行后续指令之前执行分支。微处理器试图通过预测分支的结果来绕过这一限制，从而使得来自预测目标的指令能够推测性地且没有延迟地执行。由于分支预测对性能至关重要，几十年来人们一直在研究并稳步改进分支预测。微处理器的性能在经历了几十年的指数增长后，预计在可预见的未来将持平。分支预测器设计方面的突破将是变革性的。该项目提供了对传统分支预测器有限的原因的见解。这一认识揭示了支路预测器设计的一个全新方向。暴露了两个相互关联的问题：1)传统预测器通常不能区分需要专门预测的动态分支，尤其是依赖于存储器的分支，以及2)明确地专门针对这些动态分支的预测并不能单独解决问题，因为对它们的依赖存储器地址的存储无论如何都会改变它们的未来结果。这个项目为分支预测器的设计提出了两个前所未有的原则：第一，明确识别动态分支，以便为它们提供专门的预测；第二，当存储发生在它们的从属内存地址时，主动更新它们的预测。这两个原则一起被称为Exact，代表具有活动更新的显式动态分支预测。拟议研究的目标是将这两个原则应用于设计预测器，以实现分支预测精度的飞跃，相对于最知名的预测器，错误预测的数量减少一半或一半以上。理想化实现的结果表明，这种精确度的飞跃是可能的，第一个现实的实现已经实现了这种潜力的很大一部分。为了获得更广泛的影响，项目参与者将与行业合作伙伴英特尔和IBM密切合作，将准确的技术转化为未来的微处理器设计。

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.