动态分支预测
AP SHANTHI博士
本模块的目标是讨论如何在 MIPS 架构中处理控制风险，并研究更现实的分支预测器。
在上一个模块中，我们讨论了控制风险的基础知识，并讨论了编译器如何处理控制风险。我们已经看到，较长的流水线不能很容易地提前确定分支结果，在这种情况下，停顿惩罚变得不可接受。就 MIPS 流水线而言，我们可以预测分支未被采用，并在分支之后获取指令，没有延迟。图 14.1 显示了预测未采用的方法，预测正确时和预测错误时。当预测正确时，即没有采取分支时，则无需支付任何惩罚。另一方面，当预测错误时，会产生一个气泡，并从目标地址取出下一条指令。在这里，我们假设分支是在 IF 阶段本身解决的。
让我们考虑以下操作序列。
36 子 10 美元、4 美元、8 美元
40 贝克 $1, $3, 7 # PC 相对分支到 40 + 4 + 7 * 4 = 72
44 和 12 美元、2 美元、5 美元
48 或者 13 美元、2 美元、6 美元
52 添加 14 美元、4 美元、2 美元
56 slt 15 美元、6 美元、7 美元
. . .
72 体重 4 美元、50 美元（7 美元）
图 14.2 显示了分支被采用时 MIPS 流水线中发生的情况。时钟周期 3 的 ID 阶段决定必须采取分支，因此它选择目标地址作为下一个 PC 地址（地址 72），并将为下一个时钟周期取出的指令归零。时钟周期 4 显示了位置 72 处的指令被提取以及流水线中作为所采取分支的结果的单个冒泡或 nop 指令。在第二阶段解决分支时，流水线中可能出现的 相关数据危险已经在前面的模块中讨论过。
现在，我们将讨论第二种类型的分支预测，即。动态分支预测。分支预测是对分支将走的方向进行有根据的猜测的能力 - 分支是否被采用。在动态分支预测的情况下，硬件通过记录每个分支的最近历史来测量实际的分支行为，假设未来的行为将以相同的方式继续并做出预测。如果预测出错，管道将在重新获取时停顿，硬件也会相应地更新历史记录。前面模块中讨论的静态预测与动态预测之间的比较如下：
• 静止的
– 技巧
• 延迟分支
• 静态预测
– 没有关于程序实时行为的信息
– 更容易/足够单次发行
– 需要硬件支持才能更好地预测
• 动态的
– 技巧
• 基于历史的预测
– 使用有关实时行为的信息
– 对于多问题更重要
– 提高预测的准确性
在动态分支预测的情况下，硬件可以根据指令寻找线索，也可以使用过去的历史。它维护一个历史表，其中包含有关分支上次（或最后几次）执行的信息。这个预测器的性能是
性能 = ƒ（准确度，错误预测的成本）
有不同类型的动态分支预测器。我们将详细讨论它们中的每一个。我们将讨论的七个方案如下：
1. 1 位分支预测缓冲器
2. 2 位分支预测缓冲器
3. 相关分支预测缓冲区
4.锦标赛分支预测器
5. 分支目标缓冲区
6. 返回地址预测器
7. 集成取指令单元
1 位分支预测缓冲器：在这种情况下，分支历史表 (BHT) 或分支预测缓冲器存储 1 位值以指示是否预测采用/不采用分支。PC 地址的低位索引此表的 1 位值并得到预测。这表示该分支是否最近被采用。基于此，处理器从目标地址/顺序地址中取出下一条指令。如果预测错误，则刷新管道并翻转预测。因此，每次做出错误预测时，都会翻转预测位。仅使用一些地址位可能会给我们一个错误分支的预测。但是，最好的选择是仅使用 PC 地址的一些最低有效位。
The prediction accuracy of a single bit predictor is not very high. Consider an example of a loop branch taken nine times in a row, and then not taken once. Even in simple iterative loops like this, the 1-bit BHT will cause 2 mispredictions (first and last loop iterations): first time through the loop, when it predicts exit instead of looping, and the end of the loop case, when it exits instead of looping as before. Therefore, the prediction accuracy for this branch that has taken 90% of the time is only 80% (2 incorrect predictions and 8 correct ones). So, we have to look at predictors with higher accuracy.
2 位预测器：此预测器仅在两个连续的错误预测时更改预测。预测缓冲器中保留了两位，并且有四种不同的状态。两个状态对应于一个被采用的状态，两个对应于未被采用的状态。下面给出了这种预测器的状态图。
图 14.3
这种方法的优点是少数非典型分支不会影响预测（更好地衡量“常见情况”）。只有当我们连续出现两次错误预测时，我们才会切换预测。这在多个分支共享同一个计数器时特别有用（分支 PC 的某些位用于索引分支预测器）。这可以很容易地扩展到 N 位。假设我们有 3 个比特，那么就有 8 种可能的状态，只有当连续出现 3 个错误预测时，预测才会改变。但是，研究表明，2 位预测器本身就足够准确。
相关分支预测器：2 位预测器方案仅使用单个分支的最近行为来预测该分支的未来行为。但是，很多时候，我们发现一个分支的行为依赖于其他分支的行为。不同分支之间存在相关性。使用其他分支的行为进行预测的分支预测器称为相关或两级预测器。他们利用全局信息而不是局部行为信息。可以维护关于任意数量的较早分支的信息。例如，如果我们维护有关三个较早分支 B1、B2 和 B3 的信息，则当前分支的行为现在取决于这三个较早分支的行为方式。有八种不同的可能性，从他们三个没有被带走（000）到他们都被带走（111）。维护了八种不同的预测器，并且如上所述，它们中的每一个都将作为 1 位或 2 位预测器进行维护。将根据较早分支的行为及其使用的预测来选择这些预测器之一。通常，它是一个 (m,n) 预测器，具有关于 m 个分支的全局信息，并且每个预测器都作为 n 位预测器维护。图 14.4 显示了相关预测变量的示例，其中 m=2。具有有关 m 个分支的全局信息，并且每个预测器都保持为 n 位预测器。图 14.4 显示了相关预测变量的示例，其中 m=2。具有有关 m 个分支的全局信息，并且每个预测器都保持为 n 位预测器。图 14.4 显示了相关预测变量的示例，其中 m=2。
锦标赛预测器：下一种预测器是锦标赛预测器。这使用了“预测预测器”的概念，希望为正确的分支选择正确的预测器。维护了两种不同的预测器，一种基于全局信息，一种基于局部信息，预测器的选项基于选择策略。例如，可以使用局部预测器，每次出错时，可以将预测更改为全局预测器。否则，只有在连续出现两次错误预测时才能进行切换。此类预测器非常流行，自 2006 年以来，Power5 和 Pentium 4 等处理器中使用了使用 » 30K 位的锦标赛预测器。它们能够在中等大小（8K – 32K 位）下实现更好的准确性，并且还可以非常有效地利用非常大量的预测位。它们是最受欢迎的形式多级分支 预测器使用多个级别的分支预测表以及在多个预测器中进行选择的算法。
Branch Target Buffer (BTB)：使用前面讨论的所有分支预测方案，我们仍然需要计算目标地址。这为所采取的分支提供了 1 个周期的惩罚。如果我们需要进一步减少分支惩罚，我们需要从分支的目的地快速获取一条指令。在进行预测的同时，您还需要下一个地址。如果您在找到分支之前不知道该指令在哪里，这可能会很困难。解决方案是使用一个表来记住先前分支的结果目标地址。该表称为分支目标缓冲区 (BTB)，它缓存目标地址，并在获取指令时按完整的 PC 值进行索引。也就是说，甚至在我们解码指令并确定它是一个分支之前，我们就对 BTB 进行索引。当 PC 用于获取下一条指令时，它也用于索引到 BTB。BTB 存储一些最近采用的分支的 PC 值和相应的目标地址。如果命中并且指令是预测采用的分支，我们可以立即获取目标。这为条件分支提供了零周期惩罚。如果 BTB 中没有条目，我们遵循通常的程序，如果它是一个被采取的分支，则在 BTB 中创建一个条目。另一方面，如果预测错误，则必须支付罚款，并且必须删除 BTB 条目。如图 14.5 所示。如果命中并且指令是预测采用的分支，我们可以立即获取目标。这为条件分支提供了零周期惩罚。如果 BTB 中没有条目，我们遵循通常的程序，如果它是一个被采取的分支，则在 BTB 中创建一个条目。另一方面，如果预测错误，则必须支付罚款，并且必须删除 BTB 条目。如图 14.5 所示。如果命中并且指令是预测采用的分支，我们可以立即获取目标。这为条件分支提供了零周期惩罚。如果 BTB 中没有条目，我们遵循通常的程序，如果它是一个被采取的分支，则在 BTB 中创建一个条目。另一方面，如果预测错误，则必须支付罚款，并且必须删除 BTB 条目。如图 14.5 所示。
让我们讨论一个示例问题来说明所研究的概念。考虑下表。
使用上述数据确定 BTB 的总分支惩罚。认为
• 90% 的预测准确率
• 缓冲区中 90% 和 60% 的分支被采用的命中率
分支惩罚 = 缓冲区命中率百分比 X 错误预测百分比 X 2 + ( 1 – 缓冲区命中率百分比) X
取树枝 X 2
分支惩罚 = ( 90% X 10% X 2) + (10% X 60% X 2)
分支惩罚 = 0.18 + 0.12 = 0.30 个时钟周期
返回地址预测器：接下来我们将看看预测间接跳转的挑战，即目标地址在运行时变化的跳转。很难预测间接跳转（间接过程调用、返回、case 语句）的地址。如果我们查看 SPEC89，85% 的此类分支来自过程返回。尽管可以使用分支目标缓冲区来预测过程返回，但是如果从多个站点调用该过程并且来自一个站点的调用没有及时聚类，则这种预测技术的准确性可能会很低。例如，在 SPEC CPU95 中，激进分支预测器对此类返回分支的准确度低于 60%。为了克服这个问题，一些设计使用一个小的返回地址缓冲区作为堆栈操作。此结构缓存最近的返回地址：在调用时将返回地址推入堆栈，并在返回时弹出一个。如果缓存足够大（即与最大调用深度一样大），它将完美地预测返回。
集成指令提取单元：为了满足每个时钟周期发出多条指令的现代处理器的需求，许多最近的设计人员选择实现集成指令提取单元，作为一个单独的自治单元，将指令馈送到管道的其余部分。一个集成的取指令单元集成了几个功能：
1. 集成分支预测——分支预测器成为取指单元的一部分，不断地预测分支，从而驱动取指流水线。
2. 指令预取——要在每个时钟传送多条指令，指令取指单元可能需要提前取指。该单元自主管理指令的预取，将其与分支预测相结合。
3. 指令存储器访问和缓冲——当每个周期提取多条指令时，会遇到各种复杂性，包括提取多条指令可能需要访问多条高速缓存线的困难。取指令单元封装了这种复杂性，使用预取来尝试隐藏跨越缓存块的成本。指令提取单元还提供缓冲，本质上充当按需单元，根据需要和所需数量向发布阶段提供指令。
因此，随着设计人员试图增加每个时钟执行的指令数量，指令获取将成为一个越来越重要的瓶颈，并且需要聪明的新想法以必要的速度交付指令。
总而言之，我们在本模块中指出预测对于处理分支危险很重要，而动态分支预测更有效。我们已经讨论了不同类型的预测变量。一位预测器使用一位预测，但不是很准确。2 位预测器提高了预测精度，并且仅在有两次成功的错误预测时才更改预测。相关分支预测器将最近执行的分支与下一个分支相关联。锦标赛预测器使用更多资源来竞争解决方案并在这些解决方案之间进行选择。分支目标缓冲区包括分支地址和预测。返回地址栈用于预测间接跳转。最后，
网页链接/支持材料
计算机组织与设计——硬件/软件接口，David A. Patterson 和 John L. Hennessy，第 4 版，Morgan Kaufmann，Elsevier，2009 年。
计算机组织，Carl Hamacher、Zvonko Vranesic 和 Safwat Zaky，第 5 版，McGraw-Hill 高等教育，2011 年。