处理控制危害
AP SHANTHI博士
本模块的目标是讨论如何处理控制风险，区分静态和动态分支预测，并研究延迟分支的概念。
指令序列中的分支会导致问题。必须在每个时钟周期提取一条指令以维持流水线。然而，在分支解决之前，我们将不知道从哪里获取下一条指令，这会导致问题。与数据危险相反，这种确定要获取的正确指令的延迟称为控制 危险或分支危险。我们在前面的模块中进行了检查。控制风险是由控制依赖引起的。控制依赖于分支的指令不能移动到分支的前面，使得分支不再控制它，不依赖分支的指令不能移动到分支之后，从而分支控制它。这将引起控制危险。
与控制依赖相关的两个主要问题是异常行为和数据流的处理和保存。保留异常行为要求指令执行顺序的任何更改不得改变程序中引发异常的方式。也就是说，不应产生新的异常。
• 例子：
添加 R2,R3,R4
北京 R2,L1
LD R1,0(R2)
L1：
在 BEQZ 之前移动 LD 会发生什么？这可能会导致内存保护违规。分支指令是一个保护分支，它检查地址零并跳转到 L1。如果将其提前，则会引发额外的异常。数据流是数据值在产生结果的指令和使用结果的指令之间的实际流动。分支使流程动态化并确定哪条指令是数据的提供者
• 例子：
达度 R1,R2,R3
BEQZR4,L
德苏 R1,R5,R6
吕：……
或者 R7,R1,R8
指令 OR 取决于 DADDU 或 DSUBU？我们必须确保在执行时保留数据流。
减少分支惩罚的一般规则是尽早解决分支问题。在 MIPS 流水线中，寄存器的比较和目标地址的计算通常在执行阶段完成。这会导致三个时钟周期的损失。如图 13.1 所示。如果我们通过添加硬件来解决 ID 阶段中的分支来进行更积极的实现，则可以减少惩罚。
更早地解析分支需要发生两个动作——计算分支目标地址和尽早评估分支决策。此更改的简单部分是将分支地址计算向上移动。我们在IF/ID流水线寄存器中已经有了PC值和立即数字段，所以我们只需将分支加法器从EX阶段移到ID阶段即可；当然，所有指令都会进行分支目标地址计算，但只在需要时使用。更难的部分是分支决策本身。对于分支相等，我们将比较在 ID 阶段读取的两个寄存器，以查看它们是否相等。可以通过首先对它们各自的位进行异或运算，然后对所有结果进行 OR 运算来测试是否相等。将分支测试移至 ID 阶段还意味着需要额外的转发和危险检测硬件，因为依赖于仍在管道中的结果的分支必须仍然可以通过此优化正常工作。例如，要实现平等分支（及其逆），我们需要将结果转发到在 ID 期间运行的平等测试逻辑。有两个复杂因素：
在ID的时候，我们必须对指令进行译码，决定是否需要绕过相等单元，并完成相等比较，这样如果指令是分支，我们就可以将PC设置为分支目标地址。分支操作数的转发以前是由 ALU 转发逻辑处理的，但 ID 中相等性测试单元的引入将需要新的转发逻辑。请注意，分支的绕过源操作数可以来自 ALU/MEM 或 MEM/WB 流水线锁存器。
因为在 ID 期间需要分支比较中的值，但可能会在稍后产生，所以可能会发生数据危险并且需要停顿。例如，如果紧接在分支之前的 ALU 指令产生了一个用于在分支中进行比较的操作数，则将需要停顿，因为 ALU 指令的 EX 阶段将在分支的 ID 周期之后发生。
尽管存在这些困难，但将分支执行移至 ID 阶段是一种改进，因为如果采用分支，则将分支的惩罚减少到只有一条指令，即当前正在获取的指令。
基本上有两种处理控制危害的方法：
1. 停止直到知道分支结果或再次执行提取
2. 预测分支的行为
一个。编译器的静态预测
湾 硬件动态预测
暂停流水线直到分支被解析的第一个选项，或者从解析的地址再次获取会导致太多的惩罚。分支非常频繁，如果没有有效地处理它们会降低性能。我们也违反了“速成案件”的原则。
第二种选择是预测分支的行为。分支预测是对分支将走的方向进行有根据的猜测的能力 - 分支是否被采用。首先，我们将讨论编译器所做的静态预测。这是基于典型的分支行为。例如，for循环和if语句分支，我们可以预测会采用后向分支，不会采用前向分支。因此，主要采用三种方法。他们是：
– 预测未采取的方法
• 假设没有采用分支，即条件不会被评估为真
– 预测采取的方法
• 假设分支被采用，即条件将评估为真
– 延迟分支
• 更有效的解决方案
在预测未采用的方法中，将每个分支都视为“未采用”。请记住，寄存器是在 ID 期间读取的，我们还执行相等性测试来决定是否分支。我们只需加载下一条指令 (PC+4) 并继续。当分支评估为真并且我们最终需要实际采用分支时，复杂性就会出现。在这种情况下，管道将清除从“未采用”路径加载的任何代码，然后继续执行。
在预测采用的方法中，我们假设分支总是被采用。此方法适用于在下一条指令的 IF 阶段及时计算目标地址的处理器，因此没有延迟，并且可能不会单独评估条件。这不适用于具有 5 级流水线的 MIPS 架构。这里，分支目标是在 ID 周期或之后计算的，并且条件也在同一时钟周期内进行评估。
第三种方法是延迟分支方法。在这种情况下，一条有用且不依赖于是否采用分支的指令被插入到流水线中。确定延迟分支指令是编译器的工作。根据分支的结果，由可能会或可能不会被执行的指令填充的 槽称为分支延迟槽。编译器必须用有用/独立的指令填充这些槽。如果延迟槽的数量较少，编译器会更容易。
在延迟槽中引入指令的方式有以下三种：
• 分支指令前
• 来自目标地址：仅在采取分支时才有价值
• 从失败开始：仅在不采取分支时才有价值
• 取消分支允许填充更多插槽
Figure 13.2 shows the three different ways of filling in instructions in the branch delay slots.
当采取第一选择时，分支必须不依赖于重新调度的指令，并且无论分支走向何方，性能总是会得到提升。当从目标路径中选取指令时，编译器会预测分支将采用。即使没有采取分支，也必须执行重新调度的指令。也就是说，工作可能会被浪费，但程序仍然会正确执行。这可能需要重复说明。只有采用分支时，性能才会有所提高。当不进行分支时，额外的指令可能会增加代码大小。当从 fall through 路径中挑选指令时，编译器预测该分支将不会采用。即使采取了分支，也必须执行重新调度的指令。这 只有在不采用分支的情况下才可能导致性能的提高。作为补偿代码添加的额外指令可能是开销。
延迟分支调度的局限性源于（1）对调度到延迟槽中的指令的限制以及（2）我们在编译时预测分支是否可能被采用的能力。如果编译器找不到有用的指令，它可能会用 nops 填充插槽，这不是一个好的选择。
为了提高编译器填充分支延迟槽的能力，大多数带有条件分支的处理器都引入了取消或无效化分支。在取消分支中，指令包括预测分支的方向。当分支行为与预测一致时，分支延迟槽中的指令将像通常使用延迟分支一样简单地执行。当分支被错误预测时，分支延迟槽中的指令简单地变成无操作。此类分支的示例是 Cancel-if-taken 或 Cancel-if-not-taken 分支。在这种情况下，编译器在填充分支延迟槽时不必过于保守，因为它知道如果分支行为违背预测，硬件将取消指令。
管道加速由下式给出
让我们看一个计算加速比的例子，假设如下：
14% 有条件和无条件，65% 已采取；52% 延迟槽没有被有效地填充。下表提供了各种方案的详细信息。
• 失速：1+.14（分支）*3（循环失速）
• 占用：1+.14（分支）*（.65（占用）*1（延迟查找地址）+.35（未占用）*1（罚分）)
• 未采用：1+.14*(.65(采用)*1+[.35(未采用)*0])
• 延迟：1+.14*(.52(未有用填充)*1)
其他示例问题：
给定一个应用程序，其中执行的指令中有 20% 是条件分支，其中 59% 被采用。对于 MIPS 5 级流水线，使用所有分支都被预测为采用没有分支预测的方案（即分支总是会导致 1 个周期的损失）的方案将实现什么加速？忽略所有其他摊位。
• 无分支预测的 CPI
= 0.8 x 1 + 0.2 x 2 = 1.2
• 带分支预测的 CPI
= 0.8 x 1 + 0.2 x 0.59 x 1 + 0.2 x 0.41 x 2 = 1.082
• 加速 = 1.2 / 1.082 = 1.109
我们想比较两台机器的性能。哪个机器更快？
• 机器 A：双端口内存——因此没有内存停顿
• 机器 B：单端口内存，但其流水线实现的时钟速率快 1.05 倍
认为：
• 两者的理想 CPI = 1
• 负载是已执行指令的 40% SpeedUpA
= 管道深度/(1 + 0) x (clockunpipe/clockpipe)
= 管道深度
加速B
= 管道深度/(1 + 0.4 x 1) x (clockunpipe/(clockunpipe / 1.05)
=（管道深度/1.4）x 1.05
= 75 x 管道深度
提速A /提速B
= 管道深度 / (0.75 x 管道深度) = 1.33 机器 A 快 1.33 倍
总而言之，我们已经讨论了由于分支引起的控制依赖性而引起的控制风险。分支非常频繁，因此必须妥善处理。有多种处理分支风险的方法。流水线可以停止，但这不是处理分支的有效方法。我们讨论了预测采用、预测未采用和延迟分支技术来处理分支风险。所有这些都是静态技术。我们将在下一个模块中进一步讨论分支危险。
网页链接/支持材料
计算机组织与设计——硬件/软件接口，David A. Patterson 和 John L. Hennessy，第 4 版，Morgan Kaufmann，Elsevier，2009 年。
计算机组织，Carl Hamacher、Zvonko Vranesic 和 Safwat Zaky，第 5 版，McGraw-Hill 高等教育，2011 年。