三亩地 三亩地SAN MU DI · CODE DIARY
交流投稿
ARTICLE DETAIL

日记详情

真实记录编程学习的某一天，欢迎挑你感兴趣的翻一翻。

首页/学习日记/日记详情

MIPS流水线指令调度实战：填充分支延迟槽提升CPU性能

发布时间：2026/8/6 7:59:57 三亩地 编程学习日记
MIPS流水线指令调度实战：填充分支延迟槽提升CPU性能

1. 项目概述：指令调度与分支延迟的实战意义

在计算机体系结构的学习中，流水线技术是提升CPU性能的核心手段，它让指令像工厂流水线上的产品一样被分阶段处理，从而实现了指令级的并行。然而，理想很丰满，现实却很骨感。流水线并非完美无缺，其中两个最令人头疼的“拦路虎”就是数据冒险和控制冒险。我们之前可能通过“转发”或“暂停”解决了数据冒险，但控制冒险，特别是由分支指令（比如if-else、循环）引起的延迟，对性能的拖累更为显著。这次实验，我们将直面这个经典难题。

简单来说，分支延迟指的是当CPU遇到一条分支指令（如beq,bne）时，它无法立即知道下一条要执行的指令是分支跳转的目标指令，还是顺序执行的下一条指令。在早期的经典五级流水线（取指IF、译码ID、执行EX、访存MEM、写回WB）中，分支指令的目标地址通常要在EX阶段才能计算出来。这意味着，在分支指令之后已经进入流水线的1到2条指令（具体取决于流水线设计），可能被错误地取入并开始执行。一旦分支方向确定，这些已经被部分执行的“错误”指令就必须被作废（清空流水线），导致几个时钟周期的性能白白浪费，这个浪费的周期数就是分支延迟槽。

本次实验的核心指令调度，正是为了“填平”这个延迟槽而生的一种编译器优化技术。它的思想是：既然分支指令后的一个或几个时钟周期注定要“空转”或“冒险执行”，那我们何不利用编译器（或者聪明的程序员）的智慧，在这几个周期里塞入一些无论分支是否跳转都必须执行且结果正确的指令呢？这样一来，原本被浪费的周期就被有效利用了，程序的整体执行效率得以提升。这就像在等红绿灯时提前准备好零钱，绿灯一亮就能立刻启动，而不是等到绿灯才手忙脚乱地找钱。

这个实验通常基于MIPS指令集架构进行，因为MIPS的设计相对简洁清晰，是学习流水线和体系结构的绝佳模型。通过动手编写或修改汇编代码，并利用模拟器（如MARS, SPIM）观察流水线的执行过程，我们将深刻理解分支延迟的成因、影响以及指令调度这一关键优化技术的原理与实现。无论你是正在学习《计算机组成原理》的学生，还是对CPU底层工作原理感兴趣的技术爱好者，这次实践都能让你对“程序如何被高效执行”有一个从理论到实践的飞跃性认识。

2. 实验环境搭建与核心工具解析

工欲善其事，必先利其器。要进行指令调度实验，我们首先需要一个能清晰展示MIPS流水线执行过程的模拟环境。这里我强烈推荐MARS (MIPS Assembler and Runtime Simulator)。它不仅仅是一个汇编器和模拟器，更内置了一个功能强大的流水线模拟可视化工具，能让我们直观地看到每一条指令在流水线各个阶段的状态，这对于理解数据冒险、控制冒险以及我们的调度效果至关重要。

2.1 MARS模拟器的安装与配置

MARS是一个用Java编写的绿色软件，因此你需要在电脑上先安装好Java运行时环境（JRE）。前往Oracle官网或OpenJDK项目下载并安装即可。随后，从官方或可靠的大学课程网站获取MARS的jar包（例如Mars4_5.jar）。在命令行中运行java -jar Mars4_5.jar或在图形界面双击即可启动。

第一次使用，我们需要进行关键设置以启用流水线模拟：

  1. 在菜单栏选择Settings->Memory Configuration。对于教学实验，选择Compact, Data at Address 0这个默认配置通常就足够了，它能简化内存布局。
  2. 接着，前往Settings->Tool。在这里，你需要勾选Data Segment Window、Labels Window以及最重要的Pipeline。勾选Pipeline后，MARS界面会出现一个额外的标签页，里面将以周期为单位动态展示流水线的执行情况。

注意：MARS模拟的是一种经典的5级MIPS流水线，并且它默认假设没有采用任何硬件层面的分支预测或延迟槽优化。这意味着分支指令会在EX阶段确定目标地址，导致其后的两条指令（位于IF和ID阶段）可能被错误取指，形成两个周期的分支延迟。我们的调度工作正是基于这个模型来进行的。

2.2 理解MARS的流水线可视化界面

打开Pipeline标签页，你会看到一个表格，行代表时钟周期，列代表流水线的五个阶段（F, D, E, M, W）。表格里填充的就是在每个周期、每个阶段正在被处理的指令。

  • 指令着色：MARS会用颜色高亮显示正在被执行的指令。特别需要注意的是红色高亮的指令，这通常表示该指令由于数据冒险（如未就绪的寄存器）而被暂停（Stall），或者因为控制冒险（分支误预测）而被清空（Flush）。看到红色，就意味着性能损失发生了。
  • 转发路径显示：在高级设置里，你可以启用显示数据转发（Forwarding）路径。虽然本次实验重点在控制冒险，但理解转发如何解决数据冒险，能让你更全面地认识流水线优化。
  • 周期步进：使用Tools->Pipeline子菜单下的Step或Step Back功能，可以单周期执行或回退，仔细观察每条指令的推进和冒险的发生时机。

2.3 编写与调试MIPS汇编代码

实验的核心是编写一段包含循环或条件分支的MIPS汇编代码。例如，一个简单的数组求和或者寻找最大值的程序就非常合适。在编写时，你需要刻意关注分支指令（如beq $t0, $t1, label）的位置。

编写完成后，使用Run->Assemble进行汇编，确保没有语法错误。然后，不要直接Run，而是切换到Pipeline标签页，使用单步执行（Step）来观察。你会清晰地看到，当执行到分支指令时，其后进入流水线的指令如何被标记为“误取”，并在分支方向确定后被清空，从而产生空泡（Bubble）导致流水线停顿。

这个直观的观察过程，是理解问题本质的关键。只有亲眼看到性能损失发生在哪里，你才能有的放矢地思考如何通过指令调度去填补它。

3. 分支延迟的根源与影响深度剖析

在深入调度技巧之前，我们必须像医生诊断病情一样，彻底搞清楚“分支延迟”这个病症的病理。为什么它会发生？具体会损失多少性能？这对整个CPU的设计又意味着什么？

3.1 经典五级流水线中的控制冒险时间线

让我们追踪一条分支指令beq $s1, $s2, target在经典流水线中的生命历程：

  1. 周期T（IF阶段）：指令被从内存中取出。此时，CPU只知道这是一条指令，但不知道其具体内容。
  2. 周期T+1（ID阶段）：指令被译码。CPU识别出这是一条beq指令，并从寄存器文件$s1和$s2中读取操作数的值。但是，此时还无法进行数值比较，因为比较操作通常在ALU中完成，这属于下一个阶段。
  3. 周期T+2（EX阶段）：指令进入执行单元。ALU对$s1和$s2的值进行比较，并计算出条件是否成立，同时计算出目标地址（PC + offset）。直到这个周期的末尾，CPU才真正知道下一条指令的地址应该是target还是PC+4。
  4. 问题所在：在周期T+1（ID阶段）和周期T+2（EX阶段）期间，流水线并没有停止。在周期T+1，下一条顺序指令（PC+4）已经被取指（IF）。在周期T+2，下下条顺序指令（PC+8）又被取指（IF），而之前取入的（PC+4）指令则进入了ID阶段。

当周期T+2结束时，分支方向确定。如果分支发生跳转，那么已经被取入流水线的（PC+4）和（PC+8）这两条指令就是无效的，必须被清空。清空操作会导致流水线出现“气泡”，需要额外的周期才能让正确的指令（target）流入流水线。在这个模型下，产生了2个时钟周期的延迟。这就是“分支延迟槽”为2的由来。有些教材或模拟器为了简化，也可能模型化为1个延迟槽，原理相同。

3.2 性能损失的量化评估

分支延迟对性能的影响有多大？这可以用一个简单的公式来估算：分支惩罚 = 误取指令数 * 每条指令的平均周期损失。假设分支指令占程序总指令数的20%（在循环密集的科学计算、控制程序中很常见），每次分支产生2个周期的停顿，那么仅分支延迟一项，就可能使理想流水线的加速比下降高达40%。这是一个不可忽视的巨大开销。

3.3 硬件优化与软件优化的分工

面对分支延迟，计算机体系结构设计师们从硬件和软件两个层面提出了解决方案：

  • 硬件方案：包括分支预测（静态预测、动态预测）、延迟分支（即本次实验关注的，为软件调度提供机会）、甚至更激进的推测执行。硬件方案透明，无需修改程序，但会增加CPU设计的复杂性。
  • 软件方案：即指令调度或称为填充延迟槽。这是编译器的职责（在本实验中由我们手动完成）。它的优点是不需要改变硬件，直接提升现有硬件的效率；缺点是需要编译器具备强大的代码分析能力，并且不是所有延迟槽都能找到合适的指令来填充。

我们的实验聚焦于软件方案，理解编译器在幕后为我们所做的优化工作之一。这能让你在编写高级语言（如C）循环时，明白为什么某些写法可能比另一些写法效率更高。

4. 指令调度的三大策略与实战演练

知道了问题所在，接下来就是解决问题的艺术。编译器或程序员如何找到合适的指令来填充分支延迟槽呢？主要有三种经典策略，我们将通过具体的MIPS代码示例来逐一剖析。

假设我们有一段简单的C语言代码，用于计算数组前N个元素中正数的个数：

int count = 0; for (int i = 0; i < N; i++) { if (arr[i] > 0) { count++; } }

将其直接翻译成未调度的MIPS汇编，其循环体核心部分可能如下：

loop: lw $t0, 0($s0) # $s0指向arr[i]，加载到$t0 blez $t0, skip # 如果arr[i] <= 0，跳转到skip addi $s1, $s1, 1 # count++ (这条指令在分支延迟槽内？不，目前它位于分支之后) skip: addi $s0, $s0, 4 # i++，指针移动 addi $s2, $s2, -1 # N-- (循环计数器) bnez $s2, loop # 如果N!=0，继续循环

在MARS中模拟，你会发现bnez指令每次都会导致其后的指令（循环开始处的lw）被误取，造成停顿。

4.1 策略一：从前调度（From Before）

这是最常用也最安全的策略。将分支指令之前、且与分支结果无关的指令，移动到延迟槽中。这条被调度的指令无论分支是否跳转，都必须被正确执行。

在我们的例子中，查看bnez $s2, loop指令之前的指令。addi $s2, $s2, -1是循环计数器递减，它必须在判断之前完成，且它的结果正是分支判断的依据。移动它会导致逻辑错误。再往前看，addi $s0, $s0, 4是移动数组指针，它与分支判断$s2无关。我们可以尝试将它调度到延迟槽。

调度后的代码片段：

loop: lw $t0, 0($s0) blez $t0, skip addi $s1, $s1, 1 skip: addi $s2, $s2, -1 # 原本在分支前 bnez $s2, loop # 分支指令 addi $s0, $s0, 4 # 【调度】从分支前移动过来的指令，现在位于延迟槽

效果分析：现在，bnez之后延迟槽里的是addi $s0, $s0, 4。无论循环是否继续（即bnez是否跳转），数组指针$s0都需要为下一次迭代（或循环结束）做好准备。这条指令的执行是必须且正确的。通过MARS单步执行，你会发现原来由bnez造成的流水线气泡消失了，延迟槽被有效利用。

4.2 策略二：从目标处调度（From Target）

当无法从前面找到合适指令时，可以考虑从分支跳转的目标地址处寻找指令。前提是：这条指令在分支发生跳转时必须被执行，并且在分支不跳转（即顺序执行）时，执行它也不会产生错误（通常是空操作或对全局状态无影响的指令）。这通常需要复制指令，可能增加代码大小。

假设分支beq跳转到一个标签target处，而target处的第一条指令inst_target与分支条件无关。我们可以将inst_target复制到分支的延迟槽中。这样，如果分支跳转，我们提前执行了必要的指令；如果分支不跳转，我们执行了一条本不该执行的指令，因此必须保证这条指令的执行是“无害”的。

示例场景：

... 一些计算 ... beq $t0, $zero, error_handler # 如果$t0为0，跳转到错误处理 add $v0, $s1, $s2 # 正常路径的重要指令（不能移动） ... error_handler: la $a0, error_msg # 错误处理的第一条指令：加载错误信息地址 jal print_msg

这里，beq之后是重要的add指令，不能移动。我们可以考虑将目标地址error_handler处的第一条指令la $a0, error_msg复制到延迟槽。

... 一些计算 ... beq $t0, $zero, error_handler la $a0, error_msg # 【调度】从目标处复制来的指令 add $v0, $s1, $s2 ... error_handler: # la $a0, error_msg # 这条指令被移动到上面了，这里可能需要一个nop或调整 jal print_msg

关键点：这种调度非常危险。因为当分支不跳转（即$t0 != 0）时，我们仍然执行了la $a0, error_msg，这修改了寄存器$a0的值。如果后续的正常路径代码依赖于$a0的原始值，程序就会出错。因此，只有当我们能确保该指令在两条路径上执行都安全，或者其副作用可接受时，才能使用此策略。更常见的做法是从目标处调度一个nop（空操作）的等价指令，但这没有优化意义。在实践中，编译器会非常谨慎地使用此策略。

4.3 策略三：从反方向调度（From Fall-through）

与策略二相反，此策略是从分支不跳转时的顺序执行路径（即fall-through路径）上寻找指令，复制到延迟槽中。其安全性与策略二类似：要求该指令在分支不跳转时必须执行，在分支跳转时执行也无害。

由于在大多数情况下，分支跳转（如循环继续、错误处理）被认为是“不常见”路径，而顺序执行（循环退出、正常流程）是“常见”路径，因此从常见路径调度指令可能更安全，但同样需要严格的数据流分析。

实操心得： 在手动调度的实验中，策略一（从前调度）是首选且最安全的。你应该首先检查分支指令之前的指令，寻找那些：

  1. 与分支判断条件无关（数据独立）。
  2. 其执行结果对分支跳转与不跳转的两种后续路径都是必需的。

如果找不到，再考虑是否存在可以安全地复制到延迟槽中的、来自目标处或反方向的“无害”指令。很多时候，我们可能不得不接受一个无法被完美填充的延迟槽，这时编译器或模拟器可能会在其中插入一条nop（空操作）指令。我们的优化目标就是尽可能地减少nop的数量。

5. 综合实验：优化一个复杂循环序列

现在，让我们综合运用以上策略，对一个更复杂的代码段进行调度优化。考虑以下未调度的MIPS代码片段，它模拟了一个内层循环：

# 假设: $s0 = 数组A基址, $s1 = 数组B基址, $s2 = 循环计数器N # $f0 用于累加和 (假设为浮点寄存器，此处用$t9模拟) li $t9, 0 # sum = 0 loop: lw $t0, 0($s0) # 加载 A[i] lw $t1, 0($s1) # 加载 B[i] mul $t2, $t0, $t1 # A[i] * B[i] add $t9, $t9, $t2 # sum += product addi $s0, $s0, 4 # A指针++ addi $s1, $s1, 4 # B指针++ addi $s2, $s2, -1 # N-- bgtz $s2, loop # 如果 N>0，继续循环 # 循环结束...

我们的目标是优化bgtz指令的分支延迟槽。

逐步调度分析：

  1. 识别分支指令：bgtz $s2, loop

  2. 寻找候选指令（从前调度）：

    • addi $s2, $s2, -1：这条指令计算了分支判断所用的值$s2，移动它会导致分支判断基于错误的值，不可行。
    • addi $s1, $s1, 4：这条指令更新了数组B的指针。无论本次循环是否继续（即$s2减1后是否大于0），只要进入了当前这次循环，B指针就需要更新。更重要的是，它不依赖于分支判断的结果，也不影响分支判断的条件（$s2）。这是一个优秀的候选！
    • addi $s0, $s0, 4：同理，更新数组A的指针，也是优秀候选。
    • add $t9, $t9, $t2及之前的指令：它们都位于更前面，且是本次循环计算的核心，移动它们可能破坏循环语义，需要更复杂的分析（例如循环展开），我们优先考虑指针更新指令。

  3. 执行调度：我们可以选择addi $s1, $s1, 4或addi $s0, $s0, 4移动到延迟槽。选择哪一个？通常选择那个在后续循环体中更早被用到的指针的更新指令。但在这个例子中，下一次循环的lw指令同时需要两个指针，所以任意一个都可以。我们选择移动addi $s1, $s1, 4。

第一次调度后代码：

loop: lw $t0, 0($s0) lw $t1, 0($s1) mul $t2, $t0, $t1 add $t9, $t9, $t2 addi $s0, $s0, 4 # addi $s1, $s1, 4 # 被移走 addi $s2, $s2, -1 bgtz $s2, loop addi $s1, $s1, 4 # 【调度】移动到延迟槽

现在，bgtz的延迟槽被填充了。但观察代码，我们发现addi $s0, $s0, 4和addi $s2, $s2, -1之间，以及addi $s2, $s2, -1和bgtz之间，仍然存在依赖关系吗？addi $s2, $s2, -1依赖于它自己的前一条指令吗？不依赖。它只依赖于$s2的旧值。bgtz依赖于addi $s2, $s2, -1的结果。这里存在一个数据冒险！bgtz在ID阶段需要读$s2，但addi $s2, $s2, -1的结果在WB阶段才写回。在经典五级流水线中，这会导致一个周期的暂停（Stall）。

  1. 进一步优化（结合数据冒险）：我们可以尝试通过调整指令顺序来同时缓解这个数据冒险。注意addi $s0, $s0, 4与addi $s2, $s2, -1和bgtz都无关。我们可以交换它们的位置吗？交换后，addi $s0, $s0, 4插在了addi $s2, $s2, -1和bgtz之间，这增加了一个周期，让addi $s2, $s2, -1的结果有更多时间“赶上来”，从而可能通过转发（Forwarding）机制解决冒险，避免停顿。

最终优化版代码：

loop: lw $t0, 0($s0) lw $t1, 0($s1) mul $t2, $t0, $t1 add $t9, $t9, $t2 addi $s2, $s2, -1 # 先递减计数器 addi $s0, $s0, 4 # 然后移动A指针（这条指令在bgtz之前，且与bgtz无关） bgtz $s2, loop addi $s1, $s1, 4 # 【调度】移动B指针到延迟槽

在这个版本中：

  • bgtz的延迟槽被addi $s1, $s1, 4填充。
  • addi $s2, $s2, -1和bgtz之间插入了一条无关指令addi $s0, $s0, 4。在具有转发机制的流水线中，addi $s2, $s2, -1在EX阶段末尾产生新值，可以在下一个周期的EX阶段开始时通过转发路径直接送给处于ID阶段的bgtz使用，从而避免了停顿。

通过MARS模拟（需开启转发功能观察），你将看到这个版本的流水线执行更加流畅，同时解决了控制冒险和潜在的数据冒险。这体现了指令调度作为一种编译器优化，其威力不仅在于填充延迟槽，更在于通过指令重排来最大化指令级并行度，减少各种冒险。

6. 常见问题、调试技巧与性能评估

在实际操作和理论分析中，你会遇到各种问题。这里我总结了一些典型的“坑”和解决技巧。

6.1 调度失败：引入了新的数据冒险

问题描述：当你将一条指令移动到延迟槽后，程序模拟结果错误，或者MARS流水线显示出现了新的红色暂停（Stall）。原因分析：这通常是因为被移动的指令与新的上下文产生了数据依赖。例如，你将一条使用寄存器$t0的指令移到了产生$t0的指令之前，造成了“写后读”（RAW）冒险。排查技巧：

  1. 仔细画出移动前后指令的数据流图。追踪每个寄存器的定义（写）和使用（读）位置。
  2. 利用MARS的单步执行和流水线视图，观察新出现的暂停发生在哪两条指令之间，重点关注寄存器的依赖关系。
  3. 牢记黄金法则：被调度到延迟槽中的指令，其数据流必须独立于分支指令的判断条件，并且它的执行不能破坏分支跳转与不跳转两种路径上的正确语义。

6.2 无法找到合适的指令进行调度

问题描述：分支指令前后似乎没有“安全”的指令可以移动。解决思路：

  1. 扩大搜索范围：不要只盯着紧邻的前后几条指令。有时需要将更前面的、但与当前循环体关联不大的指令（例如循环不变量的计算）进行“提升”（Loop Invariant Code Motion），然后再调度。
  2. 考虑循环展开：如果是一个小循环，可以尝试手动进行循环展开（例如，将循环体复制2-4次，同时调整循环计数器）。展开后，循环体内的指令增多，分支指令的相对频率降低，同时为指令调度创造了更多机会。这是编译器常用的高级优化手段。
  3. 接受部分优化：如果实在找不到，可以尝试填充一个对程序状态无影响的指令，例如对一个临时寄存器进行加0操作（add $t8, $t8, $0），但这并非真正的优化。更好的做法是承认此处存在限制，这有助于你理解硬件分支预测的必要性。

6.3 MARS模拟结果与理论分析不符

问题描述：你认为已经完美调度，但MARS中仍然显示有停顿。可能原因：

  1. 未启用转发（Forwarding）：MARS默认可能关闭了数据转发。前往Settings->Pipeline查看并启用转发选项。在具有转发的流水线中，许多数据冒险可以无需停顿地解决。
  2. 理解MARS的流水线模型：确认你使用的MARS版本模拟的是带有几个延迟槽的模型。有的模型是1个，有的是2个。这会影响你调度指令的数量。
  3. 结构冒险：除了数据和控-制冒险，还有结构冒险（如单端口内存访问冲突）。如果你的代码中连续出现lw和sw指令，可能会因为内存访问冲突导致停顿。指令调度对此帮助有限。

6.4 性能评估与量化对比

优化不能只凭感觉，需要数据支撑。MARS提供了强大的性能分析工具：

  1. 执行周期数（Cycles）：在Tools->Instruction Statistics中，可以看到程序执行的总周期数。优化前后对比这个数字。
  2. 指令数（Instructions）：同上，可以看到动态执行的指令总数。注意，调度本身不会减少指令数，甚至可能因复制指令（策略二、三）而略微增加。优化的目标是减少总周期数。
  3. CPI（Cycles Per Instruction）：平均每条指令消耗的周期数。理想流水线CPI为1，但冒险会导致CPI大于1。优化的目标就是降低CPI。
  • 优化前CPI = 总周期数 / 指令数
  • 优化后CPI = (总周期数 - 节省周期) / 指令数
  1. 加速比：优化前总周期数 / 优化后总周期数。例如，从1000周期降到900周期，加速比为1.11。

制作一个简单的对比表格来记录你的优化成果：

优化版本总指令数总周期数CPI分支指令数分支停顿周期总数
原始版本1502101.403060
调度后版本1501801.203030
提升0%-14.3%-14.3%0%-50%

从这个表格可以清晰看出，指令调度在指令数不变的情况下，通过减少分支停顿周期，显著降低了总执行时间和CPI。

6.5 从汇编回到高级语言

完成这个实验后，你应该建立起一个重要的认知：你在汇编层面手动进行的指令调度，正是现代编译器（如GCC, LLVM）的优化器在编译C/C++等高级语言代码时自动完成的工作之一。当你写出一个紧凑的循环时，编译器会尽力重排指令、填充延迟槽（对于支持延迟槽的架构）、甚至展开循环来提升性能。

因此，在编写高性能C代码时，一些看似微小的习惯可能有助于编译器优化：

  • 减少循环内部的条件分支：使用条件传送指令（如cmov）的架构可能更高效。
  • 尽量使循环体内部代码线性化：复杂的控制流会让调度变得困难。
  • 关注数据局部性：让数据访问更连续，这虽然不直接影响指令调度，但能提升缓存命中率，整体收益更大。

指令调度是连接编译器优化与计算机体系结构的桥梁。通过这次实验，你不仅学会了一项具体的优化技术，更重要的是，你开始以CPU流水线的视角去审视每一行代码的执行，这种底层思维是进行系统级性能分析和优化的宝贵起点。

编程学习 学习日记 实战经验
← 返回列表