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

SHF:Small: EXACT：具有主动更新的显式动态分支预测

• 批准号: 0916481
• 负责人: Eric Rotenberg
• 金额: $ 20.63万
• 依托单位: North Carolina State University
• 依托单位国家: 美国
• 项目类别: Standard Grant
• 财政年份: 2009
• 资助国家: 美国
• 起止时间: 2009-09-15 至 2015-08-31
• 项目状态: 已结题
• 来源: https://www.nsf.gov/awardsearch/showAward?AWD_ID=0916481&HistoricalAwards=false
• 关键词: SHF; Small; EXACT; Explicit; Dynamic

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.

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