写在开头

本文为笔者学习《超标量处理器设计》的一些理解，请学习时结合本书食用~
超标量处理器设计分享

概述

考虑我们在计组设计中未曾考虑的问题：如果跳转指令成功跳转，选择默认不跳转的我们需要清空流水线前面的指令，这种清空被称为跳转惩罚。

但由于我们的设计是五层流水线，跳转级在第二级，我们只需要引入延迟槽，便不需要清空流水线前面的指令，使得这个问题得到了解决。

但现代CPU设计具有以下的特点：

流水线的深度往往较深，可以达到十几级，一次清空就要被浪费掉许多条指令。
流水线的设计采用超标量设计，一次取指取到大于等于两条指令。
处理器高并行。

这样的特点导致了这种惩罚已经不是可以通过延迟槽避免的了，并且单次惩罚损失10+条指令。

并且在现代编程中，if,for,while这些语句的出现并不稀奇，所以这种频繁的惩罚是我们不能接受的，我们就需要对跳转进行尽力的预测，让CPU的实际运行尽力接近于我们的预测，这就引入了今天的设计——分支预测。

预测内容

方向

我们需要预测现在摆在我们面前的这条分支语句会不会发生跳转。

目标地址

我们需要预测现在摆在我们面前的这条分支语句如果真跳了，会跳到哪里？

这里可能有一个疑问，那就是跳到哪里这个难道不是固定的吗？我们会用一个式子直接算出来。确实，对于B类型的跳转是这样的
但J类型的跳转呢？比如jr $ra呢？假如现在用的$ra没被写回，或者还未产生怎么办？所以我们需要预测。
而且，一般情况下，我们并不通过计算来算B类型跳转，也是通过预测进行的。

方向预测具体实现

基于两位饱和计数器的分支预测

定位

最好写的分支预测，后续更强大的分支预测的基础。
对于简单程序预测率极高，捕捉冒泡排序、快速排序的分支效果欠佳。

测试点	预测率
stream_copy	164/32612 = 99.5%
bubble_sort	216537/731271 = 70.3%

思路

一条指令

在某种情况下，对于某一条特定的跳转指令，跳转方向是固定的。

这里强调一下某一条特定的跳转指令，指的是同一PC值取出来的那一条跳转指令，下同。

比如：For循环的循环判断
我们因此可以用一定量过去的同一PC的该条指令真正执行的跳转方向来预测本次跳转的方向。
由于是二位的，所以我们利用过去两次执行情况来预测本次执行，我们先定义四个状态

Strongly taken: 计数器饱和，在这种状态下预测本次发生跳转。
Weakly taken: 计数器不饱和，在这种状态下预测本次发生跳转。
Weakly not taken: 计数器不饱和，在这种状态下预测本次不发生跳转。
Strongly not taken: 计数器饱和，在这种状态下预测本次不发生跳转。

饱和不饱和在笔者这里看来代表了一种本次预测的可信度：
如果是饱和的，那有很大概率预测是正确的。
如果是不饱和的，那有相比于饱和较低的概率预测是正确的。

使用方法很简单：

对于每次预测的结果，我们用它来改变状态机的状态。
对于每次进行的预测，我们根据我们当前所处的状态给出预测。

状态转移如下：
饱和计数

例如现在我们处于Strongly not taken状态，并且这时候来了一条需要预测的指令，我们做出了不跳转的预测。
假如我们预测正确，状态不变，仍为Strongly not taken饱和。
假如我们预测失败，状态转移，变为Weakly not taken不饱和。

完全实现

压缩大小

前面是对于某一条固定PC值对应的跳转指令的预测方式，但在实际中，我们会有很多pc值不同的跳转，我们都需要对其进行预测。

所以我们可以建立一个数组（在FPGA开发中是寄存器组），存放每一个跳转的两位饱和计数的状态。

每次预测和更新都从这个数组中取出状态进行更新，这样就完成了对于所有跳转的预测。

但是，由于板子资源有限，我们显然不能开2^32大小的数组，所以采用将 31位 PC 哈希为 12位哈希值来减少碰撞。

为了节约资源，选用 IP 核而不是寄存器堆来存储这 2^12 = 4096 个饱和计数器的状态。

所以，分支预测需要两周期完成。

内容携带

更新时需要两个内容，原始饱和计数器的值和是否跳转。

如果原始饱和计数器的值仍然要从IP核取出，就会导致更新多一周期，为了避免这种情况，在预测时就会将原始饱和计数器的值流水。让 CPU 在更新时将这个值传递回来。

总体流程

饱和计数器设计思路

局部历史分支预测

定位

某些位置的分支是有历史性规律的，比如固定循环次数的 for 循环。根据该指令过去的跳转情况来预测下一次是否跳转称为局部历史分支预测。

由于使用到了饱和计数器，它可以被视为是饱和计数器分支预测的升级版本。

对于简单的程序，由于它的训练时间较长等因素，预测率略微低于饱和计数器分支预测

对于冒泡排序、快速排序则比饱和计数器分支预测更加优秀。

测试点	预测率
stream_copy	307/32624 = 99.1%
bubble_sort	136310/730336 = 81.3%

思路

根据某一指令过去的 3 次执行情况来捕捉规律，这 3 次执行的可能如下：TTT,TTN,TNT,NTT,TNN,NNT,NTN,NNN. 对每个情况都建立一个饱和计数器，捕捉在每种情况上该指令的跳转情况。

即给出 PC 值，取出该 PC 值的执行情况，由执行情况和 PC 寻址到相应的饱和计数器，用该饱和计数器给出预测。

BHR示意

图为针对某一条分支的局部历史预测取值示意

具体实现

PHT 压缩

（PHT 是指存储所有饱和计数器状态的那个 IP核）

如果根据某一指令过去的三次执行情况来捕捉规律，一个分支指令就需要 8 个饱和计数器，相比于饱和计数器分支预测方法，PHT 的占用面积是 8 倍。
这显然不太能被接受，所以我们需要压缩 PHT. 尽管可能会带来冲突(多个分支共享一个饱和计数器)。

我采用这种方式进行压缩：在我的实现中，PHT 仍然有 4096 项，深度是12位，所以我用3位执行情况拼接9位PC完成12位寻址
BHR的PHT压缩

BHR 引入

我们需要记录每一个分支指令的历史 3 次执行情况，这也需要一个表格来记录，因此需要引入新的 IP 核统一存储这个信息。称其为 BHR。

BHR 大小我设置为 4096项，仍然采用和上述饱和计数器预测相同的哈希函数将 PC 哈希后寻址。

BHR 采用 IP 核的 Distribute Ram 实现，综合消耗 LutRam，这是为了保证分支预测仍然两周期完成。否则就是三周期。

BHR预测逻辑.png

总体流程

BHR总体逻辑

全局历史分支预测

定位

某些位置的分支是有历史性规律的，比如 if..else if...else。根据前述 if 对应的跳转指令预测后面的 else if..else 是否跳转被称为全局历史预测。

由于使用到了饱和计数器，它可以被视为是饱和计数器分支预测的升级版本。

对于简单的程序，由于它的训练时间较长、全局规律不明显等因素，预测率略低于前述两种方法。

对于冒泡排序、快速排序则比前述两种方法显著优秀。

测试点	预测率
stream_copy	351/32624 = 98.9%
bubble_sort	67440/730336 = 90.8%

思路

根据过去最近 6 条分支指令的执行情况来预测当前分支是否跳转，和局部历史类似，对于每一个情况建立一个饱和计数器，捕捉在每个情况上将要被预测的分支指令的跳转规律。

即给出 PC 值，取出该 PC 值的执行情况，由执行情况和 PC 寻址到相应的饱和计数器，用该饱和计数器给出预测。

具体实现

GHR

由于我们记录的是全局分支执行情况，所以区别于 BHR 的 IP 核实现，我们只需要利用一个寄存器即可记录执行信息。

更新

GHR 的更新是我写分支目前为止遇到的最复杂，最让人不适的更新，有几个问题：

GHR 的内容如何更新？如果仅仅是在分支更新信息返回时更新，那么在预测发出到更新返回这一段时间内，往往也会有分支指令，这些分支指令的预测理应是在了解前述分支执行情况上进行的预测，如果在分支信息更新信息返回时更新，显然不能满足这个条件。
GHR 不能完全正确这是因为在前期分支指令还处于部分被识别，部分没有被识别的情况下，GHR 也不能满足反映最近 6 次分支指令执行情况，准确的说只能满足最近已识别 6 次分支指令执行情况。

问题一的解决是通过用预测是否跳转来更新 GHR，在更新信息返回时再进行纠正。

问题二难以解决，且不会影响长期正确性，最多加长训练时间，所以暂时不做处理。

GHR 这里的复杂逻辑目前我已经尽力完善，但可能还有潜在问题，用时间来慢慢思考吧。

总体流程

GHR总体逻辑.png

竞争式分支预测

定位

分支预测集大成者，集成局部历史与全局历史，根据预测准确性自动选择预测方法。

对于简单和复杂的程序，预测率都处于前述方法的中上游水平，属于是稳而不尖的分支预测，当然可能是我的实现问题，我个人感觉它不该只是这个水平。

测试点	预测率
stream_copy	99.2%
bubble_sort	87.0 %

思路

引入新的饱和计数器来记录两种方法对某一分支指令的预测情况，利用此饱和计数器选择预测率较高的方法来预测该分支指令。

具体实现

GHR 更新的变化

引入竞争后，GHR 的更新逻辑变得更加复杂，具体变为了四种情况：

使用了 BHR 的预测信息，且 BHR 与 GHR 预测都正确，不需要更新
使用了 BHR 的预测信息，且 BHR 预测正确， GHR 预测错误，更新时仅仅需要修改 GHR 某一位。
使用了 BHR 的预测信息，且 BHR 预测错误， GHR 预测错误，更新和全局历史预测一致。
使用了 BHR 的预测信息，且 BHR 预测错误， GHR 预测正确，更新时不能直接利用流水传递的 Recover_GHR 来更新。

CPHT 的引入

CPHT 的本质和 PHT 相同，都是饱和计数器的状态，只不过 CPHT 中饱和计数器的状态是为了选择方法。

CMP预测逻辑

总体流程

CMP总体逻辑.png

地址预测具体实现

跳转指令分类

Branch: b 开头的指令，例如 beq，这类指令只有两个固定的目标地址，跳转为一个，不跳转为一个，但不跳转可以通过当前 PC 直接计算得出，所以只需要用表格记录跳转的目标地址即可。
Jump: j 开头的部分指令，例如 j，这类指令只有一个固定的目标地址，所以只需要用表格记录跳转的目标地址即可。
Call: 用来进入函数的跳转指令，例如jal，这类指令只有一个固定的目标地址，所以只需要用表格记录跳转的目标地址即可。
Return: 用来返回函数的跳转指令，例如jr，这类指令会根据 Call 的地址变化而变化，设计较为特殊，用栈来维护目标地址。