# C.1 引言 本书的许多读者可能已经通过其他教材（例如我们编写的基础教材 *Computer Organization and Design*）或其他课程学习过流水线基础。第 3 章高度依赖这些知识，因此，继续阅读前，应确保自己已经熟悉本附录介绍的概念。阅读第 3 章时，也可以随时回到这里快速复习。 本附录首先介绍流水线基础，包括它对数据通路的影响、冒险，以及流水线性能。本节描述基本的五级 RISC 流水线，后续内容均以此为基础。C.2 节介绍冒险为何影响性能，以及如何处理冒险；C.3 节讨论简单五级流水线的实际实现，重点是控制和冒险处理。 C.4 节讨论流水线与指令集设计各方面的相互作用，其中包括异常以及异常与流水线的关系这一重要主题。如果读者还不熟悉精确与非精确中断，以及异常后的恢复，这些内容会很有帮助，因为它们是理解第 3 章更高级方法的关键。 C.5 节讨论如何扩展五级流水线，以处理执行时间较长的浮点指令。C.6 节通过深流水线处理器 MIPS R4000/4400 的案例，将这些概念联系起来，同时介绍它的八级整数流水线和浮点流水线。MIPS R4000 与单发射嵌入式处理器相似，例如 2010 年推出、曾用于多款智能手机和平板电脑的 ARM Cortex-A5。[^r40000] C.7 节引入动态调度，以及用记分牌（scoreboard）实现动态调度的方法。这一内容作为贯穿各层的问题介绍，因为它可以作为第 3 章核心概念的导论；第 3 章着重讨论动态调度方法。C.7 节也为理解第 3 章更复杂的 Tomasulo 算法提供了平缓的入门路径。虽然不先介绍记分牌也能讲解和理解 Tomasulo 算法，但记分牌方法更简单，也更容易掌握。 [^r40000]: **译注：** 此处原文写作“MIPS R40000”，与本段及 C.6 节的 R4000/4400 不一致。这里按明确的上下文写作 R4000。 ## 什么是流水线？ **流水线**是一种让多条指令重叠执行的实现技术；它利用执行一条指令所需的各项操作之间存在的并行性。如今，流水线是实现高速处理器的关键技术，甚至售价不足一美元的处理器也采用流水线。 流水线类似装配线。汽车装配线有许多工序，每道工序都完成汽车制造的一部分。各道工序并行工作，但处理的是不同的汽车。计算机流水线的每一步完成一条指令的一部分；与装配线一样，不同的步骤并行完成不同指令的不同部分。每一步称为一个**流水级**或**流水段**。各级首尾连接，构成流水线：指令从一端进入，逐级前进，再从另一端离开，就像装配线上的汽车。 汽车装配线的吞吐量以每小时生产的汽车数量定义，取决于成品汽车驶离装配线的频率。同样，指令流水线的吞吐量由指令离开流水线的频率决定。由于各级相互连接，就像装配线一样，所有流水级都必须同时做好前进一步的准备。指令沿流水线前进一级所需的时间，称为一个**处理器周期**。所有级同时推进，因此处理器周期的长度由最慢一级所需的时间决定，正如汽车装配线上最耗时的工序决定了车辆向前推进的间隔。在计算机中，处理器周期几乎总是一个时钟周期。 流水线设计者的目标，是使各级的处理时间均衡，就像装配线设计者努力均衡各道工序的耗时一样。如果各级完全均衡，那么在理想条件下，流水线处理器平均每条指令所需的时间为： $$ \frac{\text{非流水线机器每条指令的时间}}{\text{流水级数}} $$ 此时，流水线的加速比等于流水级数，就像具有 \(n\) 道工序的装配线，理想情况下可以将汽车产出速度提高到原来的 \(n\) 倍。不过，各级通常不能完全均衡，流水线本身也有额外开销。因此，流水线处理器平均每条指令的时间达不到理论最小值，但可以接近它。 流水线降低了每条指令的平均执行时间。如果原来的处理器执行每条指令需要多个时钟周期，那么流水线会降低 CPI。本附录主要采用这一观察角度。 流水线是一种开发顺序指令流中指令间并行性的实现技术。它有一个显著优势：与某些加速技术不同（见第 4 章），程序员看不到它的存在。 ## RISC-V 指令集基础 本书使用加载—存储体系结构 RISC-V 说明基本概念。书中介绍的几乎所有思想也适用于其他处理器，但复杂指令的实现可能复杂得多。本节使用 RISC-V 体系结构的核心部分；完整描述见第 1 章。虽然我们使用 RISC-V，但这些概念具有很强的共通性，同样适用于包括 ARM、MIPS 核心体系结构在内的各种 RISC。所有 RISC 体系结构都有几个关键特征： - 所有数据运算都针对寄存器中的数据，并且通常修改整个寄存器；每个寄存器为 32 位或 64 位。 - 只有加载和存储操作影响存储器：前者把数据从存储器送入寄存器，后者把寄存器中的数据送入存储器。通常也提供加载或存储小于整个寄存器宽度的数据的操作，例如字节、16 位或 32 位。 - 指令格式数量很少，所有指令通常具有相同长度。在 RISC-V 中，寄存器说明符 `rs1`、`rs2` 和 `rd` 总在固定位置，从而简化控制。 这些简单特征极大地简化了流水线实现，这正是这些指令集采用这种设计的原因。第 1 章完整介绍了 RISC-V ISA，这里假定读者已经读过该章。 ## RISC 指令集的一种简单实现 要理解 RISC 指令集的流水线实现，先要理解非流水线实现。本节给出一种简单方案，每条指令最多需要 5 个时钟周期。我们将把它扩展成流水线版本，大幅降低 CPI。这里的非流水线方案既不是最经济的，也不是性能最高的；选择它，是因为它能自然地过渡到流水线实现。实现指令集需要引入若干不属于体系结构状态的临时寄存器，本节引入它们是为了简化流水线。我们只关注 RISC 体系结构的一个整数子集，包含字加载/存储、分支和整数 ALU 操作。 这个 RISC 子集的每条指令都可以在最多 5 个时钟周期内完成。这 5 个周期如下。 1. **取指周期（IF）：** 将程序计数器（PC）送至存储器，取出当前指令。PC 加 4，更新为下一条顺序指令的地址，因为每条指令长 4 字节。 2. **指令译码／寄存器读取周期（ID）：** 对指令译码，从寄存器堆读出源寄存器说明符指定的寄存器。在读取寄存器时，检查它们是否相等，以备分支使用。对指令的偏移字段进行符号扩展，留待可能使用。将符号扩展后的偏移加到已递增的 PC 上，计算可能的分支目标地址。 译码与寄存器读取并行进行，因为 RISC 体系结构的寄存器说明符位置固定。这种技术称为**固定字段译码**。可能读出了实际上用不到的寄存器，这既无益于性能，也不会损害性能；不过，读取不需要的寄存器会浪费能量，因此重视功耗的设计可能避免这样做。对于加载和 ALU 立即数操作，立即数字段始终在相同位置，因此容易进行符号扩展。若要更完整地实现 RISC-V，就需要计算两个不同的符号扩展值，因为存储指令的立即数字段位于不同位置。 3. **执行／有效地址计算周期（EX）：** ALU 对上一周期准备的操作数执行操作，具体功能取决于指令类型： - **存储器访问：** ALU 将基址寄存器与偏移相加，得到有效地址。 - **寄存器—寄存器 ALU 指令：** ALU 按 ALU 操作码指定的运算，对从寄存器堆读出的值进行操作。 - **寄存器—立即数 ALU 指令：** ALU 按 ALU 操作码指定的运算，对第一个读出的寄存器值和符号扩展后的立即数进行操作。 - **条件分支：** 判断条件是否成立。 在加载—存储体系结构中，有效地址计算与执行可以合并在同一个周期，因为没有指令需要同时计算数据地址并对该数据进行运算。[^three-functions] 4. **存储器访问周期（MEM）：** 对加载指令，存储器使用上一周期算出的有效地址读取数据；对存储指令，则以该有效地址，把从寄存器堆读出的第二个寄存器值写入存储器。 5. **写回周期（WB）：** 对寄存器—寄存器 ALU 指令或加载指令，将结果写回寄存器堆。加载结果来自存储系统，ALU 指令结果来自 ALU。 [^three-functions]: **译注：** 原文说执行“三种功能之一”，随后实际列出四项。 在这一实现中，分支指令需要 3 个周期，存储指令需要 4 个周期，其余指令需要 5 个周期。假定分支频率为 12%、存储频率为 10%，这种典型指令分布对应的总体 CPI 为 4.66。不过，无论是追求最佳性能，还是在给定性能下尽量减少硬件，这个实现都不是最优的。改进这一设计留作练习，下面集中讨论如何把它流水线化。 ## RISC 处理器的经典五级流水线 只要每个时钟周期启动一条新指令，上一节的执行过程几乎不需要改变，就能实现流水线。这也说明了我们为什么选择这一设计。前面每个时钟周期现在成为一个流水级，也就是流水线中的一个周期，形成图 C.1 所示的执行模式；这也是绘制流水线的典型方式。虽然每条指令需要 5 个周期才能完成，但每个周期硬件都会启动一条新指令，并执行五条不同指令的某一部分。 | 指令／时钟周期 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | | --- | --- | --- | --- | --- | --- | --- | --- | --- | --- | | 指令 \(i\) | IF | ID | EX | MEM | WB | | | | | | 指令 \(i+1\) | | IF | ID | EX | MEM | WB | | | | | 指令 \(i+2\) | | | IF | ID | EX | MEM | WB | | | | 指令 \(i+3\) | | | | IF | ID | EX | MEM | WB | | | 指令 \(i+4\) | | | | | IF | ID | EX | MEM | WB | {#fig-C.1 .wide .expand num="C.1" caption="简单 RISC 流水线。每个周期取出另一条指令，开始其五周期执行。若每周期启动一条指令，性能最多可达到非流水线处理器的五倍。各级名称与非流水线实现的各周期相同：IF＝取指，ID＝译码，EX＝执行，MEM＝访问存储器，WB＝写回。"} 流水线真有这么简单吗？当然没有。本节和后续各节将解决流水线引入的问题，使这条 RISC 流水线真正可行。 首先，必须确定处理器每个周期发生什么，确保不会在同一周期让同一数据通路资源执行两种不同操作。例如，不能要求一个 ALU 同时计算有效地址并执行减法。因此，必须保证指令在流水线中重叠时不会引发这类冲突。幸运的是，RISC 指令集足够简单，资源使用情况较容易分析。图 C.2 以流水线形式画出简化的 RISC 数据通路。主要功能部件在不同周期使用，因此重叠执行多条指令时，冲突相对较少。这基于三个观察。 首先，指令存储器与数据存储器分离，通常由独立的指令缓存和数据缓存实现（见第 2 章）。如果只有一个存储器，取指与访问数据就会冲突；独立缓存消除了这一冲突。注意，若流水线处理器的时钟周期与非流水线版本相等，存储系统必须提供五倍带宽。这种需求增长，是提高性能的代价之一。 其次，寄存器堆在两个阶段使用：在 ID 读取，在 WB 写入。两种用途不同，所以图中把同一寄存器堆画在两个位置。因此，每个周期需要完成两次读取和一次写入。为处理对同一寄存器的读写，以及稍后就会说明的另一个原因，我们在周期前半段写入，后半段读取。 ![RISC 数据通路中各条指令随时间重叠](/figures/app-c/fig-c-2.png) {#fig-C.2 .wide .expand num="C.2" caption="流水线可视为沿时间错开的一组数据通路。图中展示各部分如何重叠，时钟周期 5（CC 5）已进入稳态。寄存器堆在 ID 中提供源操作数，在 WB 中接收结果，所以出现两次。右侧或左侧的实线分别表示在该阶段的一部分时间读取或写入，另一侧为虚线。IM＝指令存储器，DM＝数据存储器，CC＝时钟周期；Reg＝寄存器堆，ALU＝算术逻辑单元。横轴为时间，纵轴为指令的程序执行顺序。"} 第三，图 C.2 没有处理 PC。要每个周期启动一条新指令，就必须每周期递增并保存 PC；这必须在 IF 阶段完成，以准备下一条指令。此外，还需要一个加法器，在 ID 阶段计算可能的分支目标地址。另一个问题是，我们需要在 ALU 阶段使用 ALU 判断分支条件。实际上，比较两个寄存器并不需要完整的 ALU，但所需功能已足以使这项工作必须放在这一流水级进行。 除了确保流水线中的不同指令不会同时争用硬件资源，还必须保证处于不同级的指令不会互相干扰。为此，在相邻流水级之间加入流水线寄存器：周期结束时，把某一级的全部结果保存到寄存器中，作为下一周期下一级的输入。图 C.3 给出了包含这些寄存器的流水线。 为简洁起见，许多图省略了流水线寄存器，但流水线正常工作必须有它们。即使是没有流水线的多周期数据通路，也需要类似寄存器，因为只有寄存器中的值能够跨时钟边界保留。在流水线处理器中，这些寄存器还承担一个关键作用：把中间结果从一级送往另一级，而源级和目的级不一定直接相邻。例如，存储指令要写入存储器的寄存器值在 ID 读出，到 MEM 才真正使用，因此必须经过两个流水线寄存器。ALU 指令在 EX 产生结果，到 WB 才真正写回，同样要经过两个流水线寄存器。为便于引用，我们按它们连接的两个流水级命名：IF/ID、ID/EX、EX/MEM 和 MEM/WB。 ![相邻流水级之间的流水线寄存器](/figures/app-c/fig-c-3.png) {#fig-C.3 .wide .expand num="C.3" caption="相邻流水级之间加入流水线寄存器。它们避免相邻级中的两条指令相互干扰，也把同一条指令的数据从一级传递到另一级。寄存器的边沿触发特性至关重要，即寄存器值在时钟边沿瞬时改变；否则，一条指令的数据就可能干扰另一条指令的执行。CC＝时钟周期，IM＝指令存储器，DM＝数据存储器，Reg＝寄存器堆；横轴为时间。"} ## 流水线的基本性能问题 流水线提高了处理器的指令吞吐量，即单位时间完成的指令数，却不缩短单条指令的执行时间。事实上，由于流水线控制开销，每条指令的执行时间通常还会略有增加。吞吐量提高意味着程序运行更快、总执行时间更短，尽管没有任何一条指令本身执行得更快。 单条指令执行时间不缩短这一事实，限制了实际可采用的流水线深度；下一节会看到这一点。除了流水线延迟的限制，还有各级不均衡与流水线额外开销的限制。各级不均衡会降低性能，因为时钟不能快于最慢一级所需的时间。 流水线开销来自流水线寄存器延迟和时钟偏斜。寄存器会给时钟周期增加建立时间与传播延迟：建立时间指触发写入的时钟信号到来前，寄存器输入必须保持稳定的时间。时钟偏斜是时钟到达任意两个寄存器的时刻之差的最大值，也限制了时钟周期的下限。一旦时钟周期已经缩短到时钟偏斜与锁存器开销之和，继续加深流水线便没有意义，因为周期内已没有时间用于有效工作。感兴趣的读者可参见 Kunkel and Smith（1986）。 **例题** 考虑上一节的非流水线处理器。假定时钟频率为 4 GHz（或周期为 0.5 ns），ALU 操作和分支需要 4 个周期，访存操作需要 5 个周期；三者相对频率分别为 40%、20% 和 40%。由于时钟偏斜和建立时间，流水线化会给周期增加 0.1 ns 开销。忽略延迟影响，指令执行速率可以获得多大加速比？ **解答** 非流水线处理器的平均指令执行时间为： $$ \begin{aligned} \text{平均指令执行时间} &=\text{时钟周期}\times\text{平均 CPI}\\ &=0.5\ \mathrm{ns}\times[(40\%+20\%)\times4+40\%\times5]\\ &=0.5\ \mathrm{ns}\times4.4=2.2\ \mathrm{ns}. \end{aligned} $$ 流水线实现的周期，必须等于最慢一级的时间加上开销，即 \(0.5+0.1=0.6\ \mathrm{ns}\)；这也是平均指令执行时间。因此： $$ \text{流水线加速比} =\frac{\text{非流水线平均指令时间}}{\text{流水线平均指令时间}} =\frac{2.2\ \mathrm{ns}}{0.6\ \mathrm{ns}}\approx3.7. $$ 0.1 ns 的开销实际上限制了流水线的效果。如果开销不随时钟周期变化，Amdahl 定律告诉我们，它会限制加速比。 > **译注：** 原页确实同时写“4 GHz”和“0.5 ns”，两者不对应；4 GHz 对应 0.25 ns。原解答始终按 0.5 ns 计算。 如果流水线中的每条整数指令都独立于其他指令，这条简单 RISC 流水线就能正常工作。实际指令可能相互依赖；这是下一节的主题。