Branch Sequence Detector

这篇2017年的arm专利，是我认为arm性能核前端bp中最有含金量的feature。其出现在ARM发布的一些性能核中，虽然具体的性能数据提升不得而知，但却可以按图索骥分析出不少代码实现的细节。、

由于一开始看代码时没有查到这篇专利的内容，花费了很多时间分析代码细节，最终整个预测器的行为和专利一一对应

我认为这个专利值得每行仔细品味。

简单来说其主要提出了一种分支序列预测方法，用于检测与预测分支目的地相关联的序列数据，所述序列数据识别在程序流顺序中跟随在预测分支目的地之后的、具有下一个分支指令实例的下一个块，将识别出的下一个块以及当前块与识别出的下一个块之间的任何中间块添加到取指队列中，并针对预测的下一个分支指令实例启动分支预测。

branch sequencer detector简称BSD

简介

为了简单解释什么是BSD，专利对分支预测进行简单介绍，即将其分为两个部分，分支目标缓冲器 (BTB) 160 和分支预测缓冲器 (BPB) 。典型的处理器前端如下所示

预测器使用BTB与BPB中的信息预测待提取的程序代码块，并将识别此类块的数据添加到取指队列，再由取指对列发往取指模块。预测是推测性的，正确的信息将由PE进行提供（这里PE就泛指执行单元）PE可以将与执行期间实际遇到的分支指令及其实际结果相关的信息反馈给 BTB 和 BPB 。

这是前代高性能核如N2的做法，具体实现可以参考香山v2文档

下图给出一个常见代码块

给出了六条指令块.“X”指令是非分支指令。“BR”指令是分支指令，其可以根据做出分支决策的一个或多个参数导致程序流的非线性改变。

指令块可以具有一致的基本长度（以字节为单位），例如是 2 的幂或至少是 2 的倍数，并且在存储器中地址对齐到代表基本长度倍数的位置。例如，每个部分可以具有 16 字节的基本长度，并且这些部分可以对齐到存储器中的 16 字节边界。

参照第一个示例分支指令 210，如果该指令代表的分支发生跳转，则程序流被转移到另一个程序计数器值 A, 如果不跳转，程序流继续到下一条顺序指令 220.

类似地，如果分支指令 230 处的分支发生跳转，程序流被转移到程序计数器值 B，但如果不跳转，继续到下一条顺序指令 240。

因此，作为执行部分 200 的结果，程序流可以：重定向到程序计数器值 A；重定向到程序计数器值 B；或继续到下一个顺序程序计数器值 C。

图 3 示意性地示出了连续程序代码块颗粒 (Gr) Gr0、Gr1、Gr2、Gr3 ,每个颗粒 Gr0 . . . Gr2 都包含一条分支指令。

图 3 的上部 300 示出了当分支发生跳转时的示例情况，使得程序流以非线性方式从 Gr0 转移到 Gr2，然后到 Gr1，然后到 Gr3。如果分支不发生跳转，程序流将如图的下部 310 所示，从 Gr0 顺序继续到 Gr1 到 Gr2 再到 Gr3。

每个程序代码块颗粒被取指时，或者被预测取指时会对 BTB 和 BPB 进行查找以对下一个代码块颗粒进行预测，那么如果新预测要提取的程序代码块颗粒实际上不包含任何分支指令，则无需进行耗电的 BTB 和 BPB 查找来检测下一个程序代码块颗粒是什么；它仅仅是程序代码顺序中的下一个程序代码块颗粒。

下面是一个例子：

第一个颗粒是 branching granule (BG)，称为 BG1。 branching granule (BG) 表示该颗粒包含至少一条分支指令.

BG1被预测为not taken。下一个fetchq entry 425 指示在下一个 BG2 之前，程序流序列中有两个中间 granule不包含分支指令（NBG）。因此，预测电路可以确定，在执行BG1并获得该granule 的预测分支结果后，从预测结果开始的接下来两个granule 可以排队等待取指，而无需在 BTB 或 BPB 中查找这些条目进行预测。

实现

现在将参照图 6 至图 8 描述实现此功能的示例技术

BTB的改进

600：分支目标缓冲器存储程序计数器值

610：先前在该程序计数器值处检测到分支的情况下，存储分支目标地址

620：是基于当前块中的分支不跳转后的在下一个具有分支指令的块之前的块的数量。

630，其指示跳转情况下，从该target开始到在下一个具有分支指令的块之前的块的数量。

分支目标缓冲器中的条目可以具有相关的有效性标志 640。

需要注意的是，预测快可能包含多个分支指令，每个指令都有对应的target

但是，对于不跳转情况下的NBG_OFFSET：对于整组分支指令来说是相同的，因为预测都为一个顺序块（图 2 中的地址 C）。因此，可以提供单个分支不跳转偏移值 700，而不是为每个分支指令的每个程序计数器值关联单独的偏移值。

此外可以保存一些信息，用于指示要在下一次分支预测中使用的预测器算法或一些使能信息

其中分支目标存储器配置为结合指示下一个块的序列数据，存储指示适用于识别出的下一个块的分支预测方面的元数据。

具体实现

BSD 可以看作是预测电路 150 的一部分。系统启动或引导后，BSD 会把 BTB（如图 6-8 所示）里的偏移（序列）数据全部初始化为零。这能确保系统处于一个安全的初始状态，即默认对每一个块都进行预测。之后，随着序列数据的不断填充，一旦检测到连续的非分支块（NBG），系统就会把非零的偏移量更新到 BTB 中。

(48) 运行时，BTB 根据处理元件 110 反馈的信息 180 来记录分支的 PC 和目标地址。BSD 900 会检查取指电路 120 提取的代码，寻找含有分支指令的块。
具体的检测逻辑是：BSD 900 会统计程序流中连续块的数量作为偏移数据（这当然基于前一个分支是否跳转）。它每发现一个非分支块（NBG），就将偏移值加一，直到遇到下一个分支块（BG）。
一旦检测到下一个 BG，BSD 900 就会把统计好的偏移值存入 BTB：如果是分支不跳转的情况，就存为与 PC 600 关联的偏移值 620；如果是分支跳转的情况，就存为与目标地址 610 关联的偏移值 630。
因此，BSD 900 实际上就是一个分支检测器的实例：它检测取指块中是否有分支，并据此生成序列数据存入分支目标存储器。

BSD 900 可以包括：代码监视模块 1000，用于监视提取的代码；分支检测器 1010，用于检测提取代码中的 NBG；以及更新模块 1020，用于更新相关的存储序列数据值。

推测性检测实现

在上文中介绍其实是根据实际的取指流进行预测分析，但实际上实现时候使用推测性填充，其判断是否为NBG依托于BTB的预测结果

参照图 12，在一个具体示例中，分支序列检测器 (BSD 1100) 由以下四个关键模块组成：

1.
2. 错误检测器 1200：负责“纠错”。它会对比预测出的非分支块（NBG）偏移量与实际提取到的代码。一旦发现不一致，它就会向分支目标缓冲器（BTB）发送一个“无效信号 1205”，告知预测出错了。
3. 监视模块 1210：负责“盯着” BTB 中的条目 1215。
4. 分支检测器 1220：负责“定性”。它判断一个代码块到底是分支块（BG）还是非分支块（NBG）。
5. 更新模块 1230：负责“记录”。它将计算好的序列数据更新存储到 BTB 中。

在上述示例中，序列数据的作用是帮我们找到紧邻的下一个含有分支指令的代码块。
但在更高级的示例中，序列数据甚至能实现“连环预测”：在识别出第一个分支块后，它还能进一步识别出再后面一个含有分支指令的块。
这带来的好处是：处理器可以在一次操作中，将这一连串的多个块（包括中间所有没有分支的块）一次性加入取指队列，极大地提高了效率。

此外在子程序调用（Subroutine Call）

当发生子程序调用（且调用被执行/Taken）时：

1.
2. 保存现场：处理器将当前状态（主要是返回地址）压入“堆栈（Stack）”。
3. 跳转：程序流跳转去执行子程序代码。
4. 返回：子程序结束后执行“返回（Return）”指令，从堆栈中取回之前的状态，程序流跳回到调用指令后面紧跟着的那条指令继续执行。

虽然“调用”指令确实发生了跳转（去执行子程序了），但在某种意义上，它的最终结果和“分支不跳转”非常相似。为什么？因为无论子程序里发生了什么，程序最终都会回归到主程序流的下一条指令。

在子程序调用发生时，它不仅把返回地址存入堆栈，还会将“适用于分支不跳转情况的序列数据 1310”也一起存入返回堆栈 1300。
这样一来，当子程序执行完毕（如图 14 所示的 1410），处理器执行返回指令回到主程序（1420）时，就能顺便从堆栈中取回这个序列数据。有了这个数据，预测器就能立即知道主程序后面有哪些块是无分支的，从而快速提取。

总结

作为在ARM 能效核中使用的feature，我认为这个专利主要是解决的功耗问题，减少预测器查询的巨额功耗。其次在一定程度上能让预测比取指更快一步，每次预测产生的取指块会更多。但是实现时需要分支预测warm up之后才能提供较为准确的序列预测，所以不确定在25年后的超大核身上是否还有类似feature。