CPU-分支预测的算法与流水线

工程

Created At : 2023-12-19 12:29

分支预测的重要性

CPU中, 直接影响性能的两个关键部分是:

Cache.
分支预测.

对于CPU来说, 除了要在当前周期内取地址, 还需要决定下个周期从哪个地方开始取地址.

如果只是简单的按顺序取指令(默认分支不执行), 那么如果出现分支执行的情况, 就需要把当前流水线中的指令全部flush, 浪费了处理器的功耗, 同时降低了性能.

因此, 进行分支预测是必要的, 超标量处理器的分支预测需要完成如下的任务:

在取指令阶段, 预知我现在的指令里有没有分支指令.
如果有分支指令, 分支指令到底taken不taken.
如果taken, 那么我的分支指令的跳转地址是哪里.

分支预测一般指的是动态分支预测, 也就是根据程序的运行时状态决定分支是taken还是不taken.

分支指令的类型

ISA中的分支指令一般可以分成两种, 一类是直接跳转, 另一类是间接跳转, 这种分类的分类依据是分支的目标地址是否依赖寄存器.

直接跳转(PC-relative):
- 直接跳转的意思是, 在指令编码中用立即数的形式, 给定一个相对PC的偏移量, 用当前指令PC值加上偏移量就可以得到目标地址.
- 对于这种分支指令, 跳转的范围不会很大, 因为立即数是编码在指令中的, 它的大小不会很大.
- 对于这种分支指令, 非常容易计算目标地址, 可以整体提高分支预测的性能, 因此更推荐使用这种分支指令.
间接跳转:
- 间接跳转的意思是: 分支指令的目标地址依赖于一个特定的寄存器的值.
- 如果要计算目标地址, 就需要等待某个寄存器的值, 很可能需要等到流水线的execute阶段, 那么在这个时刻之前所有进入流水线的指令都有可能不正确, 增大了分支预测失败的penalty.
- 如果使用这种分支指令, 很难预测目标地址.

在CPU中, 一般只有call和ret这种伪指令会被编译成间接跳转指令, 除此之外, 基本都会使用直接跳转.

call和ret虽然是间接跳转的指令, 但是它们目标地址很有规律, 很方便预测.
对于编译器的设计者, 一般都会建议, 如果使用间接跳转, 尽量使用call和ret, 其余的跳转指令都使用直接跳转.

branch delay slot

假设你设计了一个n级的流水线CPU, 但是分支指令只有到了第m个stage才知道跳不跳转, 如果你分支预测失败了, 前面m-1个stage的流水线都要被flush, 这样就造成了前面m - 1个周期的浪费.

因此, 此时就需要程序员或者特定的Compiler, 可以从分支指令的前面挑出m - 1条指令, 这些指令有如下特点:

无论这个分支跳转结果如何, 这m - 1条指令都要执行.
这m - 1条指令如果放在分支后面执行, 不影响整体计算的正确性.

也就是说, 我预先知道这m - 1条指令可能作废, 我就选m - 1条无关并且肯定执行的指令, 执行了我就赚, 不执行我也不亏, 这个设计方式就是branch delay slot.

分支预测在流水线中的位置

首先, 分支预测器是一个进程有一个, 如果发生了进程切换, 分支预测器的数据也需要切换.

在流水线中, 分支预测的大概是这样工作的:

首先, 取址单元根据PC值(这个PC值是虚拟地址), 从I-Cache中把指令拿出来.
在同一个周期, 分支预测器会根据PC值, 来判定取出的这些指令是否有分支, 是否taken, 如果taken目标地址是多少.
然后, 下一个周期取指令的时候就可以根据分支预测的信息针对性地取.

为什么要根据PC的值来进行分支预测?

一旦程序开始执行, 每条指令对应的虚拟地址是固定的, 也就是说, 可以根据虚拟的PC唯一确定这个指令是否是分支指令.

是不是分支指令的判断

Fetch阶段可以进行一定程度的预解码, 进行预解码之后, 可以知道取出的指令是否是分支指令.

分支方向预测

状态机算法

分支预测算法可以用一个状态机来表示, 一般这个状态机有4个状态:

Strongly taken: 预测taken.
Weakly taken: 预测taken.
Weakly not taken: 预测not taken.
Strongly not taken: 预测not taken.

一般来说, 初始状态/复位后的状态选择Strongly not taken或者Weakly not taken.

状态转移表如下, 其中每一条转移边代表这个分支的最后结果, T是taken了, N是not taken.

2-bit branch predictor

这个算法的核心理念就是: 当一个分支两次被预测taken了, 我就有足够的信心预测第三次也是taken, 可以在一定程度上过滤掉分支偶尔发生变化的情况.

状态机算法对应的架构

首先, 状态编码需要采用格雷码, 保证每次状态转换只有1位变化, 降低功耗.

其次, 每一个分支指令都要对应一个状态机, 分支指令可以用PC值唯一确定, 因此, 在CPU中需要有一个表格, 以分支指令的PC为索引, 值是计数器的值, 这个表格就叫做Pattern History Table (PHT).

但是, 如果拿PC当索引, 那么每条指令都需要有一个状态机, 存储消耗太大, 因此会选用PC的一部分来索引PHT, 例如$k$位, 那么PHT的大小就是$2^{k} \times 2$.

PHT的大小直接影响了分支预测的准确度, PHT越大, 分支预测的准确度越高, 但是最后会趋于一个峰值.

PHT aliasing

如果采用PC的一部分寻址PHT, 那么就可能会出现两条分支指令, 它们PC的这k位刚好是一样的, 这种问题就是aliasing问题, aliasing问题会影响分支预测准确度.

常见的处理办法是使用Hash, 将PC值进行哈希之后再索引PHT.

Hash算法就是将任意长度的输入映射到固定长度的输出, 一般输出长度远小于输入.

什么时候更新PHT

在CPU中, 一共有三个时刻可以更新PHT:

在取指令时, 同时进行分支预测, 并且根据这个分支预测的结果更新PHT.
在流水线执行阶段, 分支的方向被实际计算出来后, 用这个结果来更新PHT.
在分支指令Commit之后, 用分支指令的结果更新PHT.

首先, 第一个时刻不行, 因为这个分支预测的结果不一定对.

其次, 第二个时刻不行, 理由如下:

假设CPU是乱序执行, 那么当前计算出来的分支结果, 很可能处在一条分支预测失败的路径上(前面还有一个分支指令, 出现了分支预测失败, 那么这条指令就作废了), 那么拿这个分支结果更新PHT就是不对的.

因此, 需要在第三个时刻更新PHT.

基于局部历史进行预测

架构

如果一个分支taken还是不taken很有规律的话, 就可以使用基于局部历史的预测方法进行预测.

实现的方法如下:

首先, 对于每一个分支, 我都要准备一个n位的寄存器, 叫做Branch History Register (BHR).
- 这个寄存器用来保存这个分支指令前面n次的执行结果, 如果某一位是1, 表示这次这个分支指令taken了.
其次, 对于每一个分支, 我都要准备一个Pattern History Table (PHT), 然后用BHR的值去索引PHT.

如何确定BHR中n的值?

观察分支预测序列, 如果连续的数最多有$p$位, 那么这个序列的循环周期就是$p$, BHR的宽度也就是$p$.

例如11000_11000_11000这个序列, 连续的1的个数是2, 连续的0的个数是3, 那么循环周期就是3, BHR的宽度就是3.

使用这种方法, 能完美预测循环周期小于等于n的序列.

所有分支的BHR会组成一个表, 叫做Branch History Table (BHT).

实际上, 不可能为每一个分支指令都准备一个BHR和一个PHT.

对于BHT来说, 会选用PC的$k$位来作为索引, 得到分支的BHR值.
为了更大限度地节约存储空间, 一般所有分支共用一个PHT.

所有分支可以共用一个PHT有什么依据吗?

一般来说, 在进行分支预测的时候不会用到太多的PHT.

例如这个序列: 11000_11000_11000_11000, 循环周期是3, BHR的宽度就是3, 那么最终训练结束后的BHR和对应分支预测结果的关系就是:

BHR值	分支预测结果
110	0
001	1
100	0
011	0
000	1

3位的BHR, 最多应该用8个表项, 但是现在只用了5个表项.

如果上面所说的设置, 那么会出现两种重名问题:

两个不同的分支指令, 最后用了同一个BHR.
虽然两个分支指令用了不同的BHR, 但是BHR的内容是相同的, 那么就会索引到PHT的同一个表项.

解决方法如下:

将PC值进行哈希, 用哈希之后的值索引BHT, 得到BHR.
得到BHR后, 将BHR和PC做某种程度的结合, 用这个结合后的值索引PHT.

有哪些可以将BHR值和PC值结合的方法?

可以采用按位异或, 现代的CPU会采用更先进的方法.

设计缺点

现实中的分支指令循环周期过大, 导致BHR宽度大, 训练时间长, 效果不好.
这种方法并没有考虑其他分支指令对该分支指令的影响.

基于全局历史进行预测

这种分支预测考虑了别的分支结果对我现在要预测的分支指令的影响.

架构

首先, 需要一个Global History Register (GHR), 这个寄存器是所有分支共用一个.

GHR用来保存最近执行的n条分支指令的结果.

理想情况下, 每一个分支指令都要有自己的PHT, 在进行分支预测时, 需要以GHR为索引, 从自己的PHT中找到分支预测的结果.

但是实际情况下, 没有办法为每一个PC准备一个PHT, 此时可以采用两种处理办法:

对PC进行哈希, 得到一个位宽比较少的索引, 这样PHT就不用每个分支都准备一个.
或者直接就只使用一个PHT, 理由同上.

如果只采用一个PHT, 索引PHT的就不能是GHR, 需要是GHR和PC的值进行某种程度的组合, 可以采用异或的方式.

设计缺点

实际的分支一般是混合的, 也就是说, 有一些分支适合基于全局历史进行预测, 有些分支适合基于局部历史进行预测, 只采用一种方法难以取得好效果.

竞争分支预测

竞争分支预测(Tournament Predictor)是对局部历史和全局历史预测方法的一种结合.

架构

如果要实现竞争分支预测, 首先需要同时实现局部历史和全局历史的预测方法, 然后需要使用一个新的PHT, 叫做Choice PHT, 简称CPHT.

CPHT用当前分支指令的PC值和GHR的组合作为索引.
对应的值是一个2-bit的状态机的值, 这个状态机的值会决定最终分支预测使用哪种方法.

这个状态机有四种状态: 00, 01, 10, 11.

00: 使用局部历史预测.
01: 使用局部历史预测.
10: 使用全局历史预测.
11: 使用全局历史预测.

状态转移的规则如下:

当局部历史预测正确, 全局历史预测错误, 状态机-1.
当局部历史预测错误, 全局历史预测正确, 状态机+1.
当都预测正确/预测不正确, 状态机不动.

为什么使用当前指令的PC值和GHR的组合作为索引?

使用PC值是为了保证每个分支指令都对应一个CPHT表项.
使用GHR是因为, 这个分支指令采用哪种方法, 很可能取决于前面分支指令的结果.

分支预测状态的更新

分支预测状态更新主要包括两个部分:

对历史寄存器的更新.
- 局部历史预测中的BHR, BHT.
- 全局历史预测中的GHR.
对PHT的更新.

这两种更新会采用不同的策略.

对BHT/GHR的更新

对历史寄存器的更新有三个阶段:

在取指令阶段, 进行完分支预测之后, 用分支预测的结果更新BHT/GHR.
在执行阶段, 分支的结果被计算出来之后, 用这个结果更新BHT/GHR.
在指令commit之后再更新BHT/GHR.

对于历史寄存器的更新:

取指令阶段, 更新GHR.
Commit阶段, 更新BHT

为什么不在指令commit之后再更新GHR?

如果一条分支指令, 它在时刻$t$被分支预测, 在时刻$t + \Delta t$时被commit, 并且更新GHR, 那么在$\Delta t$时间段内进入流水线的所有指令, 都无法从这条分支指令的结果中获益, 这就会降低分支预测的准确度.

为什么不在执行阶段, 用实际计算出来的分支结果更新GHR?

在超标量CPU中, 取指阶段和执行阶段之间也有可能会差了很多指令, 这些指令都无法从这次分支预测受益.
如果CPU是乱序的, 那么这个在执行阶段的指令很有可能在分支预测错误的路径上, 导致更新是错误的.
- 更本质上来说, 这次计算出来的结果是推测值(speculative), 并不是真实值.

为什么要在取指令阶段用分支预测的结果更新GHR ?

后续的指令都能享受到这次更新带来的益处.
即使分支预测出现失败, 后面的指令都使用了错误的GHR也没有关系, 因为这些后面的指令都处于分支预测失败的路径上, 都会从流水线中flush.

但是, 如果在取指令阶段更新GHR, 那么一旦出现了分支预测失败, GHR中的值就是错误的, 需要修复. 这里有两种修复的方法:

修复方法一: 在Commit阶段进行修复

在流水线的Commit阶段, 再准备一个GHR, 叫做Retired GHR.

前面取指令阶段的GHR叫做Speculative GHR.

当一条分支指令被Commit之后, 需要把这条分支指令的结果写入Retired GHR.

如果一条分支指令被发现分支预测错误, 那么当这条分支指令被commit之后, 需要将Retired GHR的值同步到Speculative GHR中.

这种设计有一个缺点:

正确的值只有等到分支指令的commit阶段才能同步到GHR中, 这期间会有非常多的指令进入流水线, 增大了分支预测失败的penalty.

修复方法二: 使用Checkpoint进行修复

在取指令阶段对前端GHR进行更新时, 将旧的GHR的值进行保留, 这个保留值就是Checkpoint GHR.

在执行阶段, 分支预测结果被计算出来之后, 如果发现分支预测失败, 那么就把Checkpoint GHR的值同步到GHR中.

但是, 如果CPU是乱序的, 那么执行阶段的结果依然可能是错误的(处在分支预测失败/异常的路径上), 此时还需要在Commit阶段准备一个Retired GHR, 用来保证正确性.

历史寄存器包括两类, 一类是局部历史预测的BHT, 一类是全局历史预测的GHR, 对于GHR来说, 所有分支指令共用, 为了尽量使得后续分支指令都能享受到这条分支指令的结果, 需要在取指令阶段更新GHR.

但是BHT的更新还是有区别的:

如果一条指令更新了BHT的值, 那么后面享受这个更新值的分支指令只能还是我这条分支指令, 而这条分支指令大概率不会马上再次进入流水线.

因此, 基于这个特点, 对于BHT的更新可以在Commit阶段.

对PHT的更新

在Commit阶段, 根据分支指令的结果更新PHT.

加入分支指令的序列比较有规律, 那么PHT中的状态机有大概率会处于饱和状态, 也就是11或者00这种, 因此, 对PHT的更新大概率不会跨越taken/not taken的分界线, 因此不用太早对PHT进行更新.

分支目标地址预测

直接跳转指令的预测

对于直接跳转指令, 它的目标地址有两种情况:

如果这条分支指令预测不跳转, 那么目标地址 = PC + fetch group的size.
如果这条分支指令预测跳转, 那么目标地址 = PC + 指令中立即数经过符号扩展的结果.

对于一个直接跳转指令, 它的目标地址取决于当前的PC和指令中的立即数, 这两点都是确定的, 因此它的目标地址不会随着程序的执行而变化.

因此, 对于直接跳转指令的预测, 直接把这种分支指令对应的PC和计算出来的目标地址用一个表存储就可以了.

这个表格叫做Branch Target Buffer (BTB).

BTB的结构

BTB本质上是一个Cache, 它的结构和Cache的结构相同, 只不过没有Offset.

索引这个Cache的是直接跳转指令的PC值(PC值可以根据BTB的结构划分为Tag和Index), Cache Line中存储的元素是这条直接跳转指令的目标地址.

BTB一般被设计成Set Associative Cache, 但是Way的个数比较少, 为了节省面积, 并且提高BTB的访问速度.

partial-tag BTB

BTB的Tag部分可以不用占很多位, 对于一个PC来讲, 除去Index之后, 剩余的位中, 可以取一部分作为BTB的Tag. 这样做的合理性有如下几点:

如果一个指令并不是分支指令, 那么分支预测算法就会预测不taken, 就不会访问BTB.
如果一个指令是分支指令, 并且和另一条分支指令partial-tag相同, Index也相同, 那么取出来的目标地址就是错误的, 此时就发生了分支预测错误 (但是这种错误不会影响CPU正确运行, 因为后面分支预测失败会修正, 这个目标地址是取指令用来参考的).
- 但是, 在这种情况下, 如果不采用partial-tag, 那么也会出现Cache Conflict的情况, 如果BTB采用direct mapped cache, 那么此时就会出现BTB Miss.

partial-tag还有一种实现方式, 将原来的Tag进行一定程度的哈希, 然后将哈希之后的值作为新Tag, 例如异或.

一般情况下, partial-tag和Set associative BTB结合都可以获得不错的性能.

BTB Miss的处理

当发生BTB Miss的时候, 有两种处理方法:

暂停执行:
- 如果一个分支预测为跳转, 但是在BTB中没有找到目标地址, 那么取指令阶段就会被暂停, 直到这个分支指令的目标地址被计算出来为止(计算出来的目标地址会写入BTB).
  - 一般来说, 在Decode阶段目标地址就能被算出来.
- 设计缺点: 如果I-Cache的访问周期比较多, 那么如果取指令阶段暂停的话, 流水线上就会出现很多的Bubble, 造成资源浪费.
- 设计优点: 可以节省功耗.
继续执行:
- 如果在BTB中没有找到目标地址, 那么目标地址就先用PC + fetch group size 代替.
- 如果分支目标地址计算出来发现目标地址不对, 那么进入流水线的指令就需要被flush.
- 设计缺点: 这种方式会浪费CPU的功耗, 不适合低功耗设计.

间接跳转指令的预测

间接跳转指令的目标地址依赖于寄存器的值, 其中主要讨论call指令和return指令的跳转.

call指令和Return指令一般是伪指令, 在RISC中, 一般用jal label作为call指令, 用jr ra作为return指令.

Call指令和Return指令一定会发生跳转.

Call指令的预测

一般来说, Call指令的目标地址都是固定的(因为你要调用一个函数, 这个函数的地址肯定是固定的), 因此, 对于Call指令来说可以使用BTB进行目标地址预测.

Return指令的预测

Return指令目标地址采用RAS (Return Address Stack)进行预测.

当遇到Call指令时, 需要把Call指令的下一条指令的PC放到RAS中.
- 一般来说, 只有到了Decode阶段才知道一条指令是不是Call.
- 因此, 在Decode阶段需要将PC+4保存在RAS中.
Return指令的目标地址就是RAS的栈顶, 预测完之后需要将栈顶弹出.

在Decode阶段将PC+4保存在RAS中, 这会导致什么问题?

这条指令在Decode阶段把PC+4放到了RAS中, 在这个时刻, 如果Fetch阶段的指令中还有Return指令(超标量CPU), 那么这个Return指令就取不到正在放入RAS的目标地址, 预测就会失败.

因此, 需要在Fetch阶段(同时也是分支预测阶段)就需要知道一条指令是不是Call指令, 将Call指令的目标地址保存在RAS也需要在Fetch阶段完成.

因此, 可以在BTB中增加一项, 标注这个指令是Call, Return还是其他类型的分支指令.

如果是Call指令, 目标地址还需要push到RAS.
如果是Return指令, 目标地址输出的是RAS的值, 而不是BTB的值.

如果函数调用嵌套很深, Call连续调用了多次, 把RAS占满了, 此时应该怎么办?

此时有如下两种处理方案:

RAS满了, 就停止向RAS中写入.
RAS满了, 就倒过头来从从栈底开始覆盖写入.

第一种策略下, Call指令和Return指令的对应关系会被完全打乱, 最前面的若干个Return指令会出现在RAS中找不到对应元素的情况.

第二种策略比第一种策略好, 因为存在正确的可能, 例如在递归调用的情况下, RAS中覆盖的地址和原来的地址是一样的, RAS依旧能给出正确的值.

针对递归函数特殊设计的RAS

递归的Call指令有一个特点, 就是这次写入RAS的目标地址和上一次相同. 此时, 如果两个相同的值占了RAS的两个空间, 就造成了资源浪费.

因此, 对于RAS的每一个空间, 都单独再准备一个计数器, 如果这一次写入RAS的目标地址和上一次相同, 直接把计数器+1即可.

其他间接跳转指令的分支预测

对于其他间接跳转指令,它的目标地址的可能值一般是很有限的.

可以采用局部历史分支预测方法来进行目标地址的预测.

在局部历史分支预测中, 索引PHT一般用PC和BHR经过哈希之后的值.
此时, 可以再加一个表, 叫做Target Cache, 也是用PC和BHR哈希之后的值来索引, 存储的值就是这个分支指令的目标地址.
在Commit阶段对PHT进行更新的时候, 同时也对Target Cache进行更新即可.

分支预测的检查与恢复

在流水线中:

在Decode阶段, 可以得到:
- 直接跳转指令的方向.
- 直接跳转指令的目标地址.
- 某些间接跳转指令的方向.
  - 此时, 如果出现了方向预测错误, 目标地址目前还不能得到, 就没有办法按照正确的目标地址取指令, 此时可以停止流水线, 防止功耗浪费.
在Execute阶段, 可以得到所有分支指令的方向和目标地址.

因此, 在这两个阶段都可以判断之前分支预测是否正确, 如果错误:

需要将后续指令从流水线中flush.
需要将后续指令占用的资源进行恢复.

分支预测的检查与恢复越提前, 那么分支预测失败的penalty越小.

如果在Execute阶段能够检查分支预测是否成功, 那么flush阶段可以分成两个部分:

Dispatch之前, 所有的指令都可以无差别抹掉, 因为在这之前的指令都是顺序执行, 而且都肯定处在分支预测失败的路径上, 这个过程可以在一个周期内完成.
Dispatch之后, 有一部分指令可能在分支预测失败的路径上, 但是有一部分指令在分支之前(这一部分指令就不需要flush), 此时, 这种flush就比较复杂, 需要特殊的机制支持.

ROB Flush

Execute阶段如果发现了分支预测失败, 会将这个信息写入ROB中.
暂停取指令.
让流水线继续执行, 直到这个分支指令成为流水线中最老的指令.
将流水线中的指令全部flush.
重新取指令开始执行,

设计缺点

出现预测失败的分支指令需要等它前面的指令执行完才能开始处理.
如果之前的指令出现了什么异常情况(例如load出现cache miss), 那么等待时间就会很长.

设计优点

容易实现, 复杂度不高.

Tag Flush

这个做法的思路是:

在Decode阶段, 给每一个分支指令一个编号, 在这个分支后面的指令和这个分支指令有相同的编号.
编号会随着流水线流动, 并且写入ROB.
当需要flush时, 只需要把编号大于等于分支指令编号的所有指令抹掉即可.

如果编号用$n$位编码, 那么$2^n$就代表流水线中可以同时容纳的分支指令, 如果分支指令超过这个值就会暂停取指.

编号的维护过程

需要准备两个FIFO:

Tag list: 用来存储所有被使用过的编号.
Free Tag List: 用来存储没有被使用过的编号.

当一个分支指令到了Decode阶段, 就会从Free Tag list中拿到一个编号.

当一个分支指令被commit, 就会把它的编号回收.

当一个分支指令预测失败, 就会把目前占用的大于等于这个分支编号的所有编号回收.

编号机制的一个很大的设计问题?

如果要实际进行flush, 需要对所有的编号进行广播:

广播之后, 需要在ROB和Issue Queue中抹除相关的指令.

但是, 如果需要广播的编号很多, 假设有$m$个编号, 那么就需要$m$个周期($m$次广播)才能抹除完成, 可能会很拖累性能.

因此, 可以采用如下折中的办法:

一个周期同时广播若干个编号.
flush进行的时候, 后面取指令不会暂停, 继续按照正确目标地址取指.
如果后面正确的指令到达了Dispatch阶段, flush还没有完成, 就会先让流水线停下来, 等待flush完成.

在超标量处理器中, 编号机制的一个问题?

在超标量CPU中, 最坏情况下, 一个周期取出的$n$条指令全是分支指令.

那么就需要Free Tag List一个周期提供$n$个编号, Tag List也需要一个周期能写入$n$个编号, 这就需要多端口FIFO.

但是, 在大部分情况下, 取出的$n$条指令中只有少部分是分支指令, 那么FIFO的大部分端口都会被闲置.

因此, 可以采用如下策略:

如果取出的$n$条指令中, 有多于1条分支指令, 那么第二个分支指令及其后续的指令就不能进入Decode阶段, 它们会被延迟到下一个周期.

PTAB

在取指令阶段获得了分支预测的结果后, 可以用PTAB (Prediction Target Address Buffer) 来保存这个结果, PTAB是一个表, 表项如下所示:

PTAB只会写入方向预测为taken的分支, 不是taken的分支不会写入.
Valid: 表示这个表项是否被占用.
Predict Address: 分支指令预测的目标地址.
Next PC: 预测为taken的分支指令的下一个指令的PC值, 如果发现分支预测失败, 那么这个值就可以作为正确的取指令地址.

在Fetch阶段, 如果一个分支被预测为taken, 就可以被写入PTAB, 同时这个分支在PTAB中的位置会随着流水线流动, 当得到分支实际的结果时:

实际结果not taken, 在PTAB中没有找到, 预测正确.
实际结果not taken, PTAB中找到了, 预测错误, Next PC为实际地址.
实际结果taken, 没在PTAB找到, 预测错误, 实际地址需要计算出来.
实际结果taken, 在PTAB找到, 需要对比目标地址.

但是, Fetch阶段还不知道这条指令是不是分支, 可能会把非分支指令的信息写入

超标量CPU分支预测

在超标量CPU中, 分支预测的逻辑应该是:

对取出的$n$条指令中的所有分支指令同时进行预测, 下个周期的取指地址以第一个预测为taken的分支的目标地址为准.
需要处理的最坏情况: 取出的$n$条指令全都是分支指令.

如果分支方向预测和目标地址预测是并行的, 那么下面的部件需要支持多端口:

BTB
局部历史预测的BHT和PHT.
全局历史预测的GHR和PHT.

但是, 目标地址仅仅是fetch group中第一个预测为taken的分支的目标地址, 因此, BTB理论上只需要一个端口.

因此, 可以先对fetch group中的指令进行方向预测, 然后根据方向预测的结果再用BTB预测目标地址.

GHR的多端口问题!

注意, GHR不能简单地扩展成多端口, 因为一个fetch group中, 两个分支指令的GHR值是不同的, 需要特殊的机制处理.