跳过正文

处理器是如何进行分支预测的

·5082 字
笔记 计算机系统 CPU 分支预测

什么是分支预测
#

分支预测就是处理器在分支条件尚未确定时,预测分支的走向(taken或not taken),并推测执行对应路径的指令。

具体来说,分支预测需要解决两个关键问题:

  1. 方向预测:预测分支是否会被执行(taken/not taken
  2. 目标预测:如果分支被执行,预测跳转的目标地址

这里主要介绍的是第一个问题,即对于分支结果的预测

当分支预测错误时,处理器需要刷新(flush)流水线中的错误指令,并重新从正确地址获取指令,从而产生数个到数十个时钟周期的惩罚。因此在分支预测中,MPKI (Missed predictions per kilo-instructions) 是一个重要的指标。

分支预测的分类
#

分支预测大体上可以分为两类:静态分支预测动态分支预测

其中,静态分支预测可以看作是软件侧,即编译器进行的优化,这也是早期分支预测常用的技术。而现代处理器基本使用的是动态分支预测,即硬件侧的优化。

静态分支预测
#

静态分支预测可以理解为通过编译器来达到更好的分支预测效果。

例如处理器在每次预测T/N时总是预测Not Taken,那么编译器在编译时,就会将更有可能的执行的Basic block放置在分支之后,只有在需要taken的时候才会将PC设置为目标地址并对流水线进行刷新。

更进一步的优化可以采取一些启发式规则。例如当target address < current PC时源代码通常是循环,因此此时预测Taken显然是看起来合理的做法,而反之则预测Not Taken

但是问题在于,程序通常是动态的,例如当branch依赖于外部输入时。因此静态分支预测仍然有较大的局限性。

动态分支预测
#

现代处理器常常采用动态分支预测,其核心就是根据历史信息来进行预测,因此在处理器中通常会存在单独的微架构和分支预测逻辑。

Bimodal predictor
#

即在 A Study of Branch Prediction Strategies 中提到的Strategy 7,也是最基础的动态分支预测。

其思路十分简单,就是我们假设分支通常会连续向一个方向执行一段时间(比如循环),换句话说即认为分支具有某种惯性。

其实现也很简单,即维护一个Table,为每一个branch entry分配一个m bit饱和计数器。每次预测结果为Taken就将计数器+1,反之将计数器-1。然后每次进入分支根据当前计数器来进行预测。

Two-level predictor
#

对于Bimodal branch predictor存在一个问题,即它对于一些固定的模式无法做出很好的预测。例如对于以下循环:

for(i = 0; i < n; i++){
    if(i % 2 == 0){
        // do some thing
    } else{
        // do some thing
    }
}

其分支即为TNTNTNTN,此时如果计数器处于10的状态,那么这段预测的准确性即为50%,这显然是不好的。

因此在 Two-Level Adaptive Training Branch Prediction 提出了Two-level branch predictor

这个方案的思路是,虽然当前分支之前的结果不稳定,但是如果向前多回溯几个结果,可以发现一些固定的模式并且和后续的分支结果有强相关,比如TNT后面总是N,NTN后面总是T。

在具体实现上,Two-level branch predictor相比于Bimodal branch predictor,在PHT (pattern history table) 前又增加了一个BHR (branch history register)。并使用BHR的值来访问对应的PHT。其中,可以只设置一个全局的BHR,也可以为每个分支均分配一个BHR,从而维护一张BHT (branch history table)。同样,PHT也可以设置为每一个单独的分支分配(local),或者设置为全局的(global)。

例如:

BHR: [T|NT|T|T|NT|T|NT|T]
     最新 ←----------→ 最旧
     
示例:4位BHR = 1011 (二进制)
表示最近4次分支:Taken, Not-Taken, Taken, Taken

PHT索引 = BHR值
PHT[0000] = 01 (弱NT)    PHT[1000] = 11 (强T)
PHT[0001] = 10 (弱T)     PHT[1001] = 00 (强NT)
PHT[0010] = 11 (强T)     PHT[1010] = 10 (弱T)
...                      ...
PHT[0111] = 01 (弱NT)    PHT[1111] = 11 (强T)

Gshare

Gshare 预测器将分支的 PC 与一个全局历史寄存器 XOR 以后作为 index 来选择 PHT 中的一个饱和计数器,然后使用这个计数器给出预测方向,更新时同样也通过同样的方式索引到同一个饱和计数器并更新。

gshare
GShare预测器

因此,Gshare使用了一个全局分支历史寄存器 (Global BHR)和私有模式历史表 (Private PHT)。可以理解为Two-level branch predictor的 GAp (Global Adaptive private) 分类。

hybrid predictor
#

出于对分支之间的相关性的需求,仅仅采用Bimodal branch predictor或者Two-level branch predictor是不够的。例如以下的例子:

correlation
分支间相关

以上的两个例子恰好对应局部分支历史和全局分支历史。循环退出的预测只需要单个 PC 的历史就可以解决,而分支间相关的例子则必须要全局的分支历史。可见不同的分支需要的历史是不同的,由此发展出了tournament predictor

21264
Alpha 21264

著名的 Alpha 21264 处理器就是使用了tournament predictor,由局部历史和全局历史的两个预测器分别独立预测,然后再由一个饱和计数器构成的选择结构选择使用哪个子预测器提供的方向预测。

这里仅做简单介绍,因为包括利用Global BHR和PC hash(XOR)来索引PHT的Gshare,使用hybrid predictor架构的tournament predictor,以及没有提到的混合local和global BHT的Alloyed都没有脱离Bimodal和Two-level的思路。但是作为经典超标量乱序处理器的Alpha 21264,其论文The Alpha 21264 microprocessor仍然值得进一步了解。

Perceptron predictor
#

某种意义上,我们可以将分支预测看作一个训练加预测的ML问题,而且还是一个基础的二分类问题(即预测结果是二元的T/N)。于是在 Dynamic branch prediction with perceptrons 提出了Perceptron branch predictor

perceptrons
Perceptron Model

其中selected Perceptron可以看作weights vector,而compute y则是将BHR与selected Perceptron作点积,即 $$y=w_0+\sum_{i=1}^{n}x_iw_i$$

随后通过一个threshold来输出prediction。

compute
Compute

所以很自然可以看出,Perceptron就是一个经典的neural network模型。其通过PC和BHR作为输入来进行预测,而实际的outcome则通过以下损失函数来进行反向传播。

train
training

相比于简单的Bimodal和Two-level branch predictor,Perceptron不再局限于PC和BHR,而是通过模型维护了更多和分支相关的状态作为weight。由于weights的数目增多(相比于饱和计数器),点积之后的空间更大,从而比之前的架构大大的提高了复杂度。同时通过输出置信度,Perceptron可以给出更精确的预测概率。

从更新的角度来看,每次得出的结果不仅仅只是更新了单个饱和计数器,而是通过训练同时更新了weight vector中的每一个weight,从而也提升了预测准确率的上限。

但是和现代machine learning不同,分支预测是一个对时序非常敏感的模块。分支预测在CPU前端,通常要一两个cycle就得到预测结果(taken的话还需要同时得出target address),如果预测慢了,branch evaluation已经得出了结果,预测也就没有意义了。因此,分支预测不能用复杂的模型,不仅预测需要高实时性,训练也需要快速的完成,并对权重进行实时更新。

进一步的,在perceptron predictor之上,Merging path and gshare indexing in perceptron branch prediction提出了hash perceptron的概念。从名字可以看出它与Gshare是相似的思想,通过将PC与BHR做hash来索引多个weight table。输入也不局限于BHR,而是可以用PC的某bit或者上几个PC的某bit作为input。

Perceptron branch predictor的应用更接近现代处理器一些,三星的M系列,AMD的zen系列的微架构都有用到了perceptron branch predictor。

TAGE
#

但是,当今几乎所有现代处理器使用的都不是以上的架构。而是在2006年,由André Seznec和Pierre Michaud提出的TAGE (TAgged GEometric),同时也是当今唯一的现代分支预测算法。TAGE提出当年即获得分支预测锦标赛冠军,随后接下来直到2016年,所有分支预测锦标赛都由TAGE预测器的变种获得。迄今为止,几乎所有的学术研究和商业高性能处理器都使用的是TAGE或者TAGE的变种。

Branch prediction research is basically about separating easier and more difficult branches, and using a simple predictor for the easy branches and a complex predictor for the difficult ones.
——Onur Mutlu (Computer Architecture and Digital Design, ETHZ)

分支预测研究基本上是将较容易和较困难的分支分开,对容易的分支使用简单的预测器,对困难的分支使用复杂的预测器,而这便是TAGE的设计思想。它使用多个不同历史长度的子预测器,并且使用一套机制自动地在这些子预测器中分配表项。这样能够做到使用短历史预测简单分支,长历史预测复杂分支,同时也能够避免存储空间的浪费,其示意图如下:

tage
TAGE

这里对于TAGE也仅作简单介绍,对于其具体的预测和更新算法可以参考论文 A case for (partially) tagged geometric history length branch prediction

现实的选择
#

事实上,如果单论MPKI,TAGE肯定是无法成为第一的,单论TAGE的变种TAGE-SC-L在准确率上已经超越了TAGE,但是在工业界上却少有使用。事实上,目前大部分的商业处理器仍然使用的是近20年前提出的TAGE或TAGE-L。这也反映了理论研究和现实应用的差距。因此,我们可以从工业的角度来讨论分支预测技术到底面临了哪些问题。

更新延迟
#

目前的分支预测算法都依赖的是分支的历史信息,毕竟信息的更新是必须根据执行结果来判断的。但是如果已经到下一次需要分支预测时,上一次分支预测的结果还没有执行完毕,此时该如何使用还未更新的历史进行预测?

目前主流的做法是对更新结果也进行预测,以便预测后立即更新分支历史供下一条分支使用。而当发现预测的结果出错时再对历史进行恢复。这本身就是一个值得探讨的话题,因为更新越早会造成准确率的下降,而追求更高的准确率就要承受更新的延迟。

这种技术又导致了另一个事实:现代处理器几乎采用的都是全局历史。原因涉及到了局部历史是难以恢复的。因此即使使用局部历史维护了更多的信息,显然能够提高准确率,但是只有部分处理器仅仅在循环上使用了局部历史。

简单来说,例如BHR作为全局历史仅需要使用寄存器来储存,但是如果使用局部历史,即BHT,则几乎必须使用SRAM来储存,而这就导致了恢复历史时无法在一拍内恢复或者甚至无法在短时间内恢复。关于历史维护更多的细节,包括一些解决方案可以参考 Towards the adoption of Local Branch Predictors in Modern Out-of-Order Superscalar Processors

预测延迟
#

相比于更新延迟,预测延迟是阻碍复杂算法落地的直接障碍。比如TAGE-SC-L,其使用的Statistical Corrector需要使用TAGE的结果作为输入,还需要做所有表项的加法规约,因此在现代处理器的主频下,延迟比TAGE多1-2拍。这就直接削减了TAGE-SC-L实际的竞争力。事实上,可能加入SC引入的功耗,面积,验证成本早已掩盖了其降低误检测率的好处了。

再比如说前文提到的Perceptron branch predictor,其最大的优点,通过维护更多的历史信息来准确的预测,恰恰成为了其最大的障碍————延迟。因此神经网络需要在延迟和规模间平衡,高准确率的代价就是更大的规模以及更高的延迟。amd zen的一二级预测器还都采用的是Perceptron,到了zen2则是一级预测器使用perceptron,二级预取则是使用了TAGE,而到了zen3就全部都是用的是TAGE了。

分支预测的未来
#

所以为什么大部分的商业处理器仍然使用的是近20年前提出的TAGE或TAGE-L?**可能仅仅是因为TAGE已经足够优秀,能够在存储耗尽之前充分地挖掘一条分支的可预测性。**而留给剩余的工作可能仅仅是针对一些边边角角进行优化,或者提高一些置信度,而这些提高可能还远小于其在现实中遇到的阻碍。

但正如计算机系统这门课所学习的,计算机是一个庞大的工程,不应该仅仅局限于一个层级,即纯硬件层面。就比如下面的例子就是一个已经实用的方向。

谓词化指令

谓词化指令其实就是赫赫有名的条件执行指令,例如 我们曾学习过的cmov指令就是著名的谓词化指令。设计这种指令的初衷是很多难预测的分支是和程序数据紧密相关的,甚至直接依赖于数据,那么如果将这些分支转化为cmov或类似的条件转送/执行指令,就可以只出现数据流的变化,而不出现控制流的变化。

MPKI从来就不应该作为分支预测唯一的评价指标,理论和实际也从未相等。而分支预测,则正如英特尔所发表的:

Branch Prediction Is Not A Solved Problem
——Intel

参考文章
#

TsukasaYatoki
作者
TsukasaYatoki
仍然向往着那片青空