# C.6 融会贯通：MIPS R4000 流水线
<!-- source: p0849 -->

本节考察 MIPS R4000 处理器家族（包括 4400）的流水线结构与性能。MIPS 体系结构与 RISC-V 非常相似，只在少数指令上不同，例如 MIPS ISA 中的延迟分支。R4000 实现 MIPS64，但整数和浮点程序都采用比前述五级设计更深的流水线。它把五级整数流水线拆成八级，以获得更高的时钟频率。由于缓存访问的时间尤为关键，新增的阶段来自对存储器访问过程的拆分。这种较深的流水线有时称为**超流水线**（superpipelining）。

<!-- source: p0850 -->

图 C.36 用抽象数据通路表示八级流水线结构，图 C.37 则表示连续指令在其中的重叠。虽然指令存储器和数据存储器访问都占多个周期，但它们完全流水线化，所以仍可每周期启动一条新指令。实际上，在缓存命中检测完成以前，流水线就已经使用了数据；第 3 章会更详细地讨论其实现。

各级的功能如下：

- **IF：** 取指的前半部分。此时实际完成 PC 选择，并启动指令缓存访问。

<!-- source: p0851 -->

- **IS：** 取指的后半部分，完成指令缓存访问。
- **RF：** 指令译码、读取寄存器、检查冒险，以及检测指令缓存是否命中。
- **EX：** 执行，包括有效地址计算、ALU 操作，以及分支目标计算与条件判断。
- **DF：** 取数据，即数据缓存访问的前半部分。
- **DS：** 取数据的后半部分，完成数据缓存访问。
- **TC：** 检查标签，判断数据缓存访问是否命中。
- **WB：** 加载指令和寄存器—寄存器操作写回。

除了显著增加所需转发通路，这条延迟更长的流水线也增加了加载和分支的延迟。图 C.37 显示，加载延迟为两周期，因为数据在 DS 结束时可用。图 C.38 用简略时序表示了加载之后立即使用结果的情况，也说明：加载结果需要转发给比加载晚三或四周期的使用者。

<!-- source: p0852 -->

![R4000 八级整数流水线数据通路](/figures/app-c/fig-c-36.png)
{#fig-C.36 .wide .expand num="C.36" caption="R4000 的八级流水线使用流水线化的指令缓存和数据缓存。各阶段名称及功能见正文。竖虚线既表示阶段边界，也表示流水线锁存器的位置。指令在 IS 结束时实际已可用，但标签检查与寄存器读取同在 RF 中进行，因此图中让指令存储器延伸到 RF。数据访问需要 TC，因为确认缓存命中之前不能将数据写入寄存器。Instruction memory 为指令存储器，Data memory 为数据存储器，Reg 为寄存器。"}

![R4000 中加载结果的转发与两周期延迟](/figures/app-c/fig-c-37.png)
{#fig-C.37 .wide .expand num="C.37" caption="R4000 整数流水线结构带来两周期加载延迟。数据值在 DS 结束时可用并可通过旁路送出，因此能够做到这一延迟。如果 TC 的标签检查表明未命中，则在正确数据可用时将流水线回退一周期。横轴为时钟周期，Instruction 1、2 为后续指令 1、2；其余部件标注同图 C.36。原图注将延迟排作 x1，译文依据相邻正文及图 C.38 明确的两个停顿周期译为两周期。"}

图 C.39 中，分支条件在 EX 阶段判断，因此基本分支延迟为三周期。MIPS 体系结构有一个周期的延迟分支槽；R4000 对剩余两周期采用预测不跳转策略。如图 C.40，不跳转的分支只有一个周期的延迟槽；跳转的分支则在延迟槽之后还有两个空闲周期。指令集中提供了前面介绍的 branch-likely 指令，有助于填充分支延迟槽。流水线互锁既负责落实分支跳转时的两周期停顿代价，也负责因使用加载结果而引起的数据冒险停顿。

<!-- source: p0853 -->

R4000 之后的所有 MIPS 处理器实现都使用了动态分支预测。

| 指令 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 |
|---|---|---|---|---|---|---|---|---|---|
| `ld x1,…` | IF | IS | RF | EX | DF | DS | TC | WB | |
| `add x2,x1,…` | | IF | IS | RF | 停顿 | 停顿 | EX | DF | DS |
| `sub x3,x1,…` | | | IF | IS | 停顿 | 停顿 | RF | EX | DF |
| `or x4,x1,…` | | | | IF | 停顿 | 停顿 | IS | RF | EX |
{#fig-C.38 .wide .expand num="C.38" caption="加载后立即使用结果，会导致两周期停顿。两周期后可以使用正常转发通路，因此 add 和 sub 在停顿后通过转发取得值，or 则从寄存器堆读取。若加载之后的两条指令与它无关，它们就不必停顿，因此旁路的接收者也可能是比加载晚三或四周期的指令。原图注把停顿长度排作 x1，但表内明确列出两周期停顿；图中沿用了 RISC-V 风格的指令和寄存器名。"}

![R4000 分支的三周期基本延迟](/figures/app-c/fig-c-39.png)
{#fig-C.39 .wide .expand num="C.39" caption="由于在 EX 阶段判断条件，基本分支延迟为三周期。横轴为时钟周期；BEQZ 是分支，Instruction 1–3 是顺序后继指令，Target 是分支目标指令，其他部件名称同图 C.36。"}

较深流水线不仅增加加载和分支停顿，也增加 ALU 操作所需的转发层数。在五级 RISC-V 流水线中，两条寄存器—寄存器 ALU 指令之间可以从 ALU/MEM 或 MEM/WB 转发；在 R4000 中，ALU 旁路有四个可能的来源：EX/DF、DF/DS、DS/TC 和 TC/WB。

<!-- source: p0854 -->

| 情形与指令 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 |
|---|---|---|---|---|---|---|---|---|---|
| **跳转：分支指令** | IF | IS | RF | EX | DF | DS | TC | WB | |
| 延迟槽 | | IF | IS | RF | EX | DF | DS | TC | WB |
| 停顿 | | | 停顿 | 停顿 | 停顿 | 停顿 | 停顿 | 停顿 | 停顿 |
| 停顿 | | | | 停顿 | 停顿 | 停顿 | 停顿 | 停顿 | 停顿 |
| 分支目标 | | | | | IF | IS | RF | EX | DF |
| **不跳转：分支指令** | IF | IS | RF | EX | DF | DS | TC | WB | |
| 延迟槽 | | IF | IS | RF | EX | DF | DS | TC | WB |
| 分支后第 2 条指令 | | | IF | IS | RF | EX | DF | DS | TC |
| 分支后第 3 条指令 | | | | IF | IS | RF | EX | DF | DS |
{#fig-C.40 .wide .expand num="C.40" caption="表的上半部分是跳转的分支：一个周期的延迟槽之后有两周期停顿。下半部分是不跳转的分支，只有一个周期的延迟槽。分支可以是普通延迟分支，也可以是 branch-likely；后者在不跳转时取消延迟槽指令的效果。原图注把停顿长度排作 x1，图中时序和相邻正文则明确为两周期。"}

## 浮点流水线

R4000 的浮点部件包含浮点除法器、乘法器和加法器三个功能单元。乘法或除法的最后一步也会使用加法器逻辑。双精度浮点运算的时间从取负的两周期，到平方根的 112 周期不等；各单元的启动频率也不同。可以把浮点部件看作由图 C.41 所列的八种阶段组成；它们按不同次序组合，执行各种浮点操作。

每种阶段只有一份硬件，不同指令可能按不同次序使用某级零次或多次。图 C.42 给出最常见双精度浮点操作的延迟、启动间隔及所用阶段。

根据图 C.42，可以判断一串相互独立但类型不同的浮点操作能否无停顿地发射。如果时序会导致共享流水级冲突，就需要停顿。图 C.43–C.46 给出四种常见的双指令序列：乘法后接加法、加法后接乘法、除法后接加法，以及加法后接除法。各图列出第二条指令所有值得考察的起始位置，以及在该位置能够发射还是必须停顿。当然，也可能同时有三条活动指令，那样停顿的可能性更大，图也更复杂。

<!-- source: p0855 -->

| 阶段 | 功能单元 | 说明 |
|---|---|---|
| A | 浮点加法器 | 尾数相加 |
| D | 浮点除法器 | 除法流水级 |
| E | 浮点乘法器 | 异常检测 |
| M | 浮点乘法器 | 乘法器第一阶段 |
| N | 浮点乘法器 | 乘法器第二阶段 |
| R | 浮点加法器 | 舍入 |
| S | 浮点加法器 | 操作数移位 |
| U | — | 拆解浮点数的编码 |
{#fig-C.41 .wide .expand num="C.41" caption="R4000 浮点流水线使用的八种阶段。原表未为 U 指定单独的功能单元。"}

| 浮点指令 | 延迟 | 启动间隔 | 流水阶段（按使用次序） |
|---|---:|---:|---|
| 加法、减法 | 4 | 3 | U, S+A, A+R, R+S |
| 乘法 | 8 | 4 | U, E+M, M, M, M, N, N+A, R |
| 除法 | 36 | 35 | U, A, R, D²⁸, D+A, D+R, D+A, D+R, A, R |
| 平方根 | 112 | 111 | U, E, (A+R)¹⁰⁸, A, R |
| 取负 | 2 | 1 | U, S |
| 绝对值 | 2 | 1 | U, S |
| 浮点比较 | 3 | 2 | U, A, R |
{#fig-C.42 .wide .expand num="C.42" caption="浮点操作的延迟和启动间隔都取决于它必须使用哪些浮点阶段。延迟值假定使用结果的指令是浮点运算；若使用者是存储指令，延迟少一周期。阶段按实际使用次序列出。S+A 表示同一周期同时使用 S 和 A；D²⁸ 表示连续 28 次使用 D 阶段。"}

<!-- source: p0856 -->

| 操作 | 发射/停顿 | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12 |
|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
| 乘法 | 发射 | U | E+M | M | M | M | N | **N+A** | **R** |  |  |  |  |  |
| 加法 | 发射 |  | U | S+A | A+R | R+S |  |  |  |  |  |  |  |  |
| 加法 | 发射 |  |  | U | S+A | A+R | R+S |  |  |  |  |  |  |  |
| 加法 | 发射 |  |  |  | U | S+A | A+R | R+S |  |  |  |  |  |  |
| 加法 | 停顿 |  |  |  |  | U | S+A | **A+R** | **R+S** |  |  |  |  |  |
| 加法 | 停顿 |  |  |  |  |  | U | **S+A** | **A+R** | R+S |  |  |  |  |
| 加法 | 发射 |  |  |  |  |  |  | U | S+A | A+R | R+S |  |  |  |
| 加法 | 发射 |  |  |  |  |  |  |  | U | S+A | A+R | R+S |  |  |
{#fig-C.43 .wide .expand num="C.43" caption="周期 0 发射一次浮点乘法，随后只在周期 1–7 中的某个位置发射一条浮点加法。第二列表示在乘法之后 n 周期发射加法时，能否发射或必须停顿；n 就是第二条指令进入 U 的周期号。造成冲突的阶段用粗体表示。这里各加法行是互斥的起始位置，并非同时执行多条加法。若加法在乘法之后四或五周期开始，就会停顿；其他位置可以直接发射。周期 4 开始的加法须停顿两周期，因为下一周期仍有冲突；周期 5 开始则只停顿一周期，即可消除冲突。"}

| 操作 | 发射/停顿 | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12 |
|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
| 加法 | 发射 | U | S+A | A+R | R+S |  |  |  |  |  |  |  |  |  |
| 乘法 | 发射 |  | U | E+M | M | M | M | N | N+A | R |  |  |  |  |
| 乘法 | 发射 |  |  | U | M | M | M | M | N | N+A | R |  |  |  |
{#fig-C.44 .wide .expand num="C.44" caption="在加法之后发射的乘法总能无停顿地进行：较短的指令在较长指令到达共享阶段之前，就已经离开这些阶段。两条乘法行代表不同的起始位置。"}

<!-- source: p0857 -->

| 操作 | 发射/停顿 | 25 | 26 | 27 | 28 | 29 | 30 | 31 | 32 | 33 | 34 | 35 | 36 |
|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
| 除法 | 周期 0 已发射… | D | D | D | D | D | **D+A** | **D+R** | **D+A** | **D+R** | A | **R** |  |
| 加法 | 发射 |  | U | S+A | A+R | R+S |  |  |  |  |  |  |  |
| 加法 | 发射 |  |  | U | S+A | A+R | R+S |  |  |  |  |  |  |
| 加法 | 停顿 |  |  |  | U | S+A | **A+R** | **R+S** |  |  |  |  |  |
| 加法 | 停顿 |  |  |  |  | U | **S+A** | **A+R** | R+S |  |  |  |  |
| 加法 | 停顿 |  |  |  |  |  | U | S+A | **A+R** | **R+S** |  |  |  |
| 加法 | 停顿 |  |  |  |  |  |  | U | **S+A** | **A+R** | R+S |  |  |
| 加法 | 停顿 |  |  |  |  |  |  |  | U | S+A | **A+R** | **R+S** |  |
| 加法 | 停顿 |  |  |  |  |  |  |  |  | U | **S+A** | **A+R** | R+S |
| 加法 | 发射 |  |  |  |  |  |  |  |  |  | U | S+A | A+R |
| 加法 | 发射 |  |  |  |  |  |  |  |  |  |  | U | S+A |
| 加法 | 发射 |  |  |  |  |  |  |  |  |  |  |  | U |
{#fig-C.45 .wide .expand num="C.45" caption="浮点除法可能使在其即将结束时开始的加法停顿。除法在周期 0 开始、周期 35 完成；图注称这里显示其最后 10 个周期。除法大量使用加法也需要的舍入硬件，因此周期 28–33 开始的加法都会停顿。原图注称，周期 28 开始的加法会一直停顿到周期 36。如果加法紧接除法开始，就不会冲突，因为在除法用到共享阶段之前，加法已经完成，类似图 C.44 中的乘法与加法。与前图相同，各加法行是不同的候选起始位置，只考虑其中一条加法。原图注给出的 U 起始范围是周期 26–35，原表还列出了周期 36 的 U，译表照录。"}

| 操作 | 发射/停顿 | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12 |
|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
| 加法 | 发射 | U | S+A | **A+R** | **R+S** |  |  |  |  |  |  |  |  |  |
| 除法 | 停顿 |  | U | **A** | **R** | D | D | D | D | D | D | D | D | D |
| 除法 | 发射 |  |  | U | A | R | D | D | D | D | D | D | D | D |
| 除法 | 发射 |  |  |  | U | A | R | D | D | D | D | D | D | D |
{#fig-C.46 .wide .expand num="C.46" caption="双精度加法之后跟随一条双精度除法。如果除法在加法之后一周期开始，就需要停顿；再晚则不会冲突。三条除法行分别表示不同的起始位置。"}

> 译注：图 C.44 最后一行在 U 后仅标 M，未标通常的 E+M，译表照录。图 C.45 原图注称周期 28 开始的加法要等到周期 36，但表内周期 34 和 35 的起始位置已标为可发射；两处不一致，均予保留。

## R4000 流水线的性能

<!-- source: p0855 -->

下面考察 SPEC92 基准在 R4000 流水线上运行时的停顿。流水线停顿或效率损失主要有四个来源：

1. **加载停顿：** 在加载之后一或两周期内使用结果而引起的延迟。
2. **分支停顿：** 每个跳转分支造成两周期停顿，再加上未填满或被取消的分支延迟槽。R4000 实现的 MIPS 指令集支持在编译时预测分支的指令；实际行为与预测不符时，取消延迟槽中的指令。这有助于填充分支延迟槽。

<!-- source: p0856 -->

3. **浮点结果停顿：** 因浮点操作数的 RAW 冒险而停顿。
4. **浮点结构停顿：** 浮点流水线中的功能单元冲突限制了发射，从而造成延迟。

图 C.47 给出 10 个 SPEC92 基准在 R4000 流水线上的 CPI 分解，图 C.48 以表格给出同一组数据。

这两图显示了加深流水线的代价。R4000 的分支延迟远长于经典五级流水线，显著增加了分支耗费的周期；分支较频繁的整数程序尤为明显。这也是后来的中等深度到深流水线处理器几乎都使用动态分支预测器的原因；原书这里以 8–16 级作为典型深度。

<!-- source: p0857 -->

浮点程序有一个有趣现象：浮点功能单元的延迟造成的结果停顿，多于结构冒险造成的停顿。后者既来自启动间隔限制，也来自不同浮点指令之间的功能单元冲突。因此，应先着力降低浮点操作延迟，再考虑进一步流水线化或复制功能单元。当然，降低延迟可能增加结构停顿，因为许多潜在结构停顿原先被数据冒险遮住了。

<!-- source: p0858 -->

![SPEC92 基准在 R4000 上的流水线 CPI 分解](/figures/app-c/fig-c-47.png)
{#fig-C.47 .wide .expand num="C.47" caption="假定缓存理想时，10 个 SPEC92 基准的流水线 CPI，范围为 1.2–2.8。最左边五个是整数程序，分支延迟是其 CPI 的主要增加项；最右边五个是浮点程序，主要增加项是浮点结果停顿。横轴为 SPEC92 基准程序，纵轴为流水线 CPI；图例依次为基础 CPI、加载停顿、分支停顿、浮点结果停顿和浮点结构停顿。图 C.48 给出原书列出的相应数值。"}

| 基准程序 | 流水线 CPI | 加载停顿 | 分支停顿 | 浮点结果停顿 | 浮点结构停顿 |
|---|---:|---:|---:|---:|---:|
| Compress | 1.20 | 0.14 | 0.06 | 0.00 | 0.00 |
| Eqntott | 1.88 | 0.27 | 0.61 | 0.00 | 0.00 |
| Espresso | 1.42 | 0.07 | 0.35 | 0.00 | 0.00 |
| Gcc | 1.56 | 0.13 | 0.43 | 0.00 | 0.00 |
| Li | 1.64 | 0.18 | 0.46 | 0.00 | 0.00 |
| **整数平均值** | **1.54** | **0.16** | **0.38** | **0.00** | **0.00** |
| Doduc | 2.84 | 0.01 | 0.22 | 1.39 | 0.22 |
| Mdljdp2 | 2.66 | 0.01 | 0.31 | 1.20 | 0.15 |
| Ear | 2.17 | 0.00 | 0.46 | 0.59 | 0.12 |
| Hydro2d | 2.53 | 0.00 | 0.62 | 0.75 | 0.17 |
| Su2cor | 2.18 | 0.02 | 0.07 | 0.84 | 0.26 |
| **浮点平均值** | **2.48** | **0.01** | **0.33** | **0.95** | **0.18** |
| **总体平均值** | **2.00** | **0.10** | **0.36** | **0.46** | **0.09** |
{#fig-C.48 .wide .expand num="C.48" caption="总流水线 CPI，以及四种主要停顿来源各自的贡献。主要贡献来自浮点结果停顿（包括分支和浮点输入所等待的结果）与分支停顿，加载和浮点结构停顿的贡献较小。表中名称、数值及舍入均按原表保留；原图 C.47 的程序顺序与图 C.48 不同，部分柱高、分项与表中数字亦不完全吻合。"}