MIPS I如何在不停顿的情况下处理基于先前ALU指令的分支？

Question

MIPS I如何在不停顿的情况下处理基于先前ALU指令的分支？

8

        addiu   $6,$6,5
        bltz    $6,$L5
        nop
        ...
$L5:

这怎么安全而不会出现停顿，即使是经典的MIPS也只有在缓存未命中时才能做到，原始的MIPS指的是没有互锁流水线级别的微处理器，并且拥有一个负载延迟槽而非互锁。

原始的MIPS I是一种经典的5级RISC IF ID EX MEM WB设计，通过单个分支延迟槽在ID阶段尽早检查分支条件来隐藏所有分支延迟（更正：这是错误的，请阅读本答案;不要被此错误前提下的其他细节所误导）。这就是为什么它受限于等于/不等于，或者像小于零或大于等于零这样的标志位检查，而不是需要通过加法器进行进位传递的两个寄存器之间的小于检查。

这难道不意味着分支需要比ALU指令提前一个周期准备好输入吗？bltz与addiu同时进入ID阶段。

MIPS I（也称为R2000）使用EX输出到EX输入的bypass forwarding，因此普通整数ALU指令（例如一系列addu/xor）具有单周期延迟，并且可以在连续周期内运行。

MIPS代表“没有交错流水线级别的微处理器”，因此它不会检测RAW风险；代码必须避免它们。（因此第一代MIPS上有负载延迟槽，MIPS II添加了交错以在这种情况下停顿，使首字母缩写无效:P）。

但我从未看到有关计算分支条件多个指令的讨论，以避免停顿。（addiu/bltz示例是由MIPS gcc5.4发出的-O3 -march=mips1on Godbolt，它会尊重加载延迟槽，如有需要则填充nop。）

它是否使用了某种技巧，例如EX在时钟下降沿读取输入，而ID不需要转发的寄存器值直到上升沿？（前提是EX产生的结果足够早以使其起作用）

我猜如果时钟速度足够低以使缓存访问为单周期，则这将是有意义的。

MIPS中的停顿或气泡声称lw+对加载结果的beq需要2个停顿周期，因为它无法转发。但实际的MIPS I并非如此（除非gcc存在漏洞）。它确实提到了半个时钟周期，允许在同一个完整周期内写入并从寄存器文件中读取一个值。

- Peter Cordes

1

我似乎记得在过去几个月/半年中看到过一些各个阶段的实际MIPS传播延迟时间的图表。我认为它确实提前准备好了EX结果，并且ID直到时钟的第二阶段才需要它。但是我不记得我在哪里看到过，或者它是否真的是针对MIPS而不是其他ISA。 - Peter Cordes

1

这里的一部分混淆可能是因为MIPS I架构不是第一个MIPS架构，它之前有斯坦福MIPS架构。这个原始架构没有互锁，并且也没有字节寻址。https://www.ethz.ch/content/dam/ethz/special-interest/infk/inst-cs/lst-dam/documents/Publications/mips_retrospective.pdf - Ross Ridge

@RossRidge：不幸的是，我们不能假设gcc生成最优代码，但它在展开循环（https://godbolt.org/z/WLdSCz）时的指令调度并没有避免在测试之前计算分支输入（如果这会导致停顿，出于性能而非正确性原因，它应该这样做）。虽然通过对循环变体进行试验，当循环中有更多的工作时，它通常会避免这种情况。所以我们无法确定它是一个错过的优化还是在MIPS I上实际上是好的。（而GCC的MIPS调优关心一些超标量MIPS。） - Peter Cordes

1

依我之见，当 bltz 进入 ID 以及 addiu 进入 EX 时，它们有整整一个时钟周期来稳定其输出并将结果写入中间级联寄存器。所以 EX 只需直接转发这些寄存器，而 ID 最初使用旧值，但新值及时到达，使其值通过 ID 条件检查门展开。基本上，就像你所说的，这可能实际上是一种组合逻辑（而不是基于时钟的）而不是顺序网络（这将使其成为“流水线” ID 阶段）。 - Margaret Bloom

@MargaretBloom：原来MIPS不需要在时钟的第一半开始IF；这就是我记得的半时钟的地方。发布了一个回答，解决了这个终于有意义的谜团。 - Peter Cordes

显示剩余3条评论

2个回答

1

你实际上在问两个问题：

在MIPS I上是否安全？
如果是，如何实现？

在MIPS I上是否安全？

我看过不同的MIPS CPU块图。大多数CPU在EX甚至MEM阶段而不是ID阶段执行分支决策。

当然，这样的设计在执行示例代码时会有不同的反应。

如果没有您正在使用的CPU的官方手册的官方声明，那么无法确定地回答您的问题。

（保罗·克莱顿在Is that true if we can always fill the delay slot there is no need for branch prediction?上的回答认为，在MIPS R2000上，一个延迟槽完全隐藏了分支延迟，但不适用于MIPS R4000。因此，尽管存在各种可能不完全遵循MIPS ISA的实现，但这是实际商用MIPS CPU按照问题所假设的方式工作的良好证据。）

如果需要，怎么做呢？这难道不意味着分支指令需要比ALU指令提前一个周期准备好它们的输入吗？不是的。关键在于旁路转发逻辑。让我们看下面的例子：

add  $A, $B, $C      ; Currently in MEM stage
or   $D, $E, $F      ; Currently in EX stage
bltz $G, someLabel   ; Currently in ID stage

（其中 A、B、... G 是 GPR 编号）

对于 EX 阶段的旁路转发逻辑（or 指令），包含一个多路复用器，其工作方式如下（伪代码）：

if E = A
    take ALU input from EX/MEM shift register output
else
    take ALU input from ID/EX shift register output
end-if

这个多路复用器使你能够在后续指令（or）中使用某些指令（add）的结果。

当然，对于ID阶段也可以使用3路复用器来实现相同的功能：

if G = D
    take branch decision input from ALU output
else if G = A
    take branch decision input from EX/MEM shift register output
else
    take branch decision input from register bank output
end-if

通过这样做，信号传播时间将增加所需的EX阶段时间。这意味着这将限制处理器的时钟频率。

然而，某些指令的结果已经可以在下一条指令的ID阶段中使用，而无需额外的时钟周期。

- Martin Rosenau

@PeterCordes 请查看我的“编辑2”部分。 - Martin Rosenau

我相信我的有关使用一个延迟槽来隐藏分支延迟的说法适用于真实的MIPS I（R2000）。这就是我所询问的CPU，因此查看gcc输出是有意义的。我怀疑这些信息是否公开可用 - 我不太确定。当它们与性能相关时，一些CPU手册确实会涉及到非常具体的细节。在当时，在没有其他预期停顿和缓存未命中的代码上测试IPC，通过测试真实的CPU可以很容易地进行测量。 - Peter Cordes

我在一本旧的MIPS书中找到了一个权威的解释。感谢您的贡献，但是您的答案从未解释过EX如何能够及时准备好新的PC，以便1个分支延迟槽就足够了。 - Peter Cordes

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- Peter Cordes · Accepted Answer

TL:DR: 经典MIPS I在EX的前半个周期检查分支条件，因此向它们进行转发并不特别。

IF仅需要在一个周期的后半段中使用地址，因此EX可以向其进行转发。

这些因素结合起来只会产生1个分支延迟周期（通过1个延迟槽隐藏），对于依赖于先前ALU指令的分支没有问题。

在MIPS I（R2000）上运行sltu / beq肯定是安全的。例如，在真实的MIPS手册和书籍中，这被列为bgeu伪指令的扩展，并没有任何关于它在MIPS R2000或任何其他MIPS上不安全的警告。

GCC在实践中使用这样的序列，即使使用march=mips1也可以遵守延迟槽和其他真实MIPS R2000功能。

MIPS的IF在时钟周期的第二个半部分之前不需要地址，因此EX可以足够快地生成它。

来自Dominic Sweetman的See MIPS Run（涵盖MIPS I到MIPS IV），第1.5.1章“指令约束”。

我们将在稍后看到，有效的条件分支意味着关于是否分支的决定必须挤压到仅占用半个流水线阶段；架构通过保持分支决策测试非常简单来帮助。因此，（在MIPS中）条件分支测试单个寄存器的符号/零或一对寄存器的相等性。

他们的图1.3：流水线和分支延迟显示了分支条件在EX的前半部分计算，并在IF的后半部分使用，总分支延迟仅为1个周期/流水线阶段（ID）/指令。 IF实际上直到时钟周期的后半部分才开始。 （并继续进入ID。ID的实际解码/寄存器获取仅占用时钟周期的最后一小部分。）

这与我在问题中提出的建议具有相同的最终结果（通过在ID结束时检查分支条件），只是它仅需要EX-> EX转发以基于先前ALU指令的结果进行分支。

也许我记错或误解了我之前读到的关于半周期分支决策的内容。这个半周期的事情可能恰好是我记得看到的。

进一步引用See MIPS Run 1.5.5程序员可见的流水线效果

• 延迟分支：[第一段解释了分支延迟槽] 如果硬件没有进行特殊处理，决定是否分支以及分支目标地址将在ALU管道阶段结束时出现，这时可以获取到分支目标指令而不是下两条指令。但是，分支非常重要，足以证明需要特殊处理。从图1.3 [上述描述] 可以看出，提供了一条特殊路径通过ALU，使得分支地址提前半个时钟周期可用。与指令获取阶段的奇数半个时钟周期移位一起，这意味着分支目标可以被获取，成为下一个指令，因此硬件运行分支指令，然后是分支延迟槽指令，最后是分支目标 - 没有其他延迟。 ... [不要浪费你的分支延迟槽] ... [许多MIPS汇编器会为您重新排序指令（如果安全），以隐藏分支延迟] < p > < em > 《See MIPS Run》由MIPS Technologies创始人John L. Hennessy作序等。这并不能证明他对书中所有内容的准确性都签字了，但这是一个很好的证据，证明该书描述MIPS如何处理此技巧的准确性。 < p > 它易于理解且百分之百可信; 我们已经知道数据缓存具有单周期获取延迟（在EX阶段后进行地址生成）。