7.1.1 流水线的基本概念#

在非流水线的 CPU 中，每条指令必须完整执行完毕后，下一条指令才能开始。这种串行执行方式意味着 CPU 的各个功能部件在大部分时间里处于空闲状态。

流水线借鉴了工业装配流水线的思想：将一条指令的执行过程划分为若干个功能段（阶段），每个功能段由独立的硬件部件完成。当第一条指令完成第一个阶段进入第二个阶段时，第二条指令就可以进入第一个阶段开始执行，依此类推。

流水线的核心优势

流水线并不缩短单条指令的执行时间（延迟），而是通过多条指令的重叠执行来提高单位时间内完成指令的数量（吞吐率）。在理想情况下，$k$ 段流水线的吞吐率是非流水线方式的 $k$ 倍。

7.1.2 MIPS 指令流水线#

MIPS 处理器的经典五级流水线将每条指令的执行过程划分为以下五个阶段：

1
指令 1:  IF → ID → EX → MEM → WB
2
指令 2:       IF → ID → EX  → MEM → WB
3
指令 3:            IF → ID  → EX  → MEM → WB
4
指令 4:                 IF  → ID  → EX  → MEM → WB

在理想流水线中，每个时钟周期都有一条指令完成（流出），每个时钟周期也有一条新指令进入流水线。

7.1.3 流水线的时空图表示#

时空图是描述流水线工作状态的直观工具，横轴为时间（以时钟周期为单位），纵轴为流水线的各个功能段。

时空图示例（4 段流水线执行 6 条指令）：

从时空图可以直观看到：

• 前 $k-1$ 个周期（$k$ 为段数）是流水线的装入阶段（建立时间），流水线尚未满载。
• 从第 $k$ 个周期开始，流水线进入满载阶段，每个周期都有一条指令流出。
• 最后 $k-1$ 个周期是排空阶段。

7.2.1 单周期数据通路的流水改造#

将单周期数据通路改造为流水线数据通路，关键在于在相邻的两个功能段之间插入流水线寄存器（又称段间寄存器、锁存器）。

五级流水线需要 4 组流水线寄存器：

1
IF/ID 寄存器 → ID/EX 寄存器 → EX/MEM 寄存器 → MEM/WB 寄存器

流水线寄存器的作用：

• 将前一个阶段的处理结果和控制信号暂存，供下一个阶段在下一个时钟周期使用。
• 实现各功能段之间的物理隔离，使不同指令的不同阶段可以在同一时刻独立工作。

7.2.2 流水线中的控制信号及传递#

在流水线结构中，控制信号在 ID 阶段由译码逻辑统一生成，但不同的控制信号在不同的阶段才会被使用。因此，控制信号必须跟随指令一起在流水线寄存器中逐级向后传递，在需要使用的那个阶段从对应的流水线寄存器中取出。

例如：

• RegWrite 信号在 ID 阶段生成，但直到 WB 阶段才用于控制写回操作。
• MemRead / MemWrite 信号在 MEM 阶段才使用。
• ALUOp 信号在 EX 阶段使用。

7.2.3 指令在流水线中的执行过程#

以 lw $t0, 0($s0) 为例，该指令在五级流水线中的数据流动过程：

1. IF 阶段：PC 送入指令存储器读出指令，指令存入 IF/ID 寄存器，PC+4 同时保存。
2. ID 阶段：从 IF/ID 寄存器取出指令进行译码，读出 $s0 的值，符号扩展立即数 0，控制信号生成并存入 ID/EX 寄存器。
3. EX 阶段：ALU 将 $s0 的值与立即数 0 相加，得到访存有效地址，结果存入 EX/MEM 寄存器。
4. MEM 阶段：以有效地址访问数据存储器，读出数据存入 MEM/WB 寄存器。
5. WB 阶段：将 MEM/WB 寄存器中的数据写回寄存器堆的 $t0。

7.3.1 流水线冲突的分类#

流水线冲突分为三类：

7.3.2 结构冲突处理#

结构冲突的典型场景：指令存储器与数据存储器共用同一个存储器端口时，取指阶段与访存阶段在同一时刻都需要访问存储器。

常见解决方法：

• 资源重复配置：将指令存储器和数据存储器分开（哈佛结构），使取指和访存互不干扰。这是现代处理器的标准做法。
• 流水线停顿：当冲突发生时，暂停流水线中后续指令的推进，等待资源释放。

7.3.3 控制冲突处理#

当 CPU 执行到分支指令（如 beq）时，分支的目标地址和分支条件通常要到 EX 阶段甚至 MEM 阶段才能确定。而在此之前，流水线已经按照 PC+4 的顺序取入了后续指令。如果分支成立，这些已取入的指令全部无效，必须被清除（称为分支延迟惩罚）。

常见处理方法：

1. 冻结/排空流水线：检测到分支指令后，暂停取指，等到分支结果确定后再取下一条指令。简单但性能损失大。

2. 预测分支不发生：总是假设分支不成立，继续按顺序取指。如果预测正确则无性能损失；如果预测错误，则清除已取入的无效指令（冲刷流水线）。

3. 预测分支发生：总是假设分支成立，立即取分支目标处的指令。

4. 延迟分支：编译器将与分支无关的指令调度到分支指令之后的”延迟槽”中，无论分支是否成立，延迟槽中的指令都会被执行。

7.3.4 插入气泡解决数据冲突#

数据冲突是流水线中最常见的冲突类型。考虑以下指令序列：

1
add $t0, $t1, $t2    # 指令 1：在 WB 阶段写 $t0
2
sub $t3, $t0, $t4    # 指令 2：在 ID 阶段读 $t0

指令 2 在 ID 阶段需要读取 $t0 的新值，但此时指令 1 尚未到达 WB 阶段完成写回。如果不做处理，指令 2 读到的将是 $t0 的旧值，导致运算结果错误。

插入气泡（stall）：当检测到数据冲突时，硬件自动在流水线中插入空操作（NOP），使后续指令延迟若干周期，直到所需数据被正确写回。

1
add $t0, $t1, $t2:  IF  ID  EX  MEM  WB
2
                             ↓ 数据在 WB 阶段才写回
3
sub $t3, $t0, $t4:  IF  ID  ○   ○    ID  EX  MEM  WB
4
                        需要读$t0     等数据就绪后重新读

其中 ○ 表示插入的气泡（空闲周期）。插入气泡虽然能保证正确性，但会严重降低流水线吞吐率。

7.3.5 使用重定向解决数据冲突#

重定向（又称数据旁路、转发）是现代流水线处理器解决数据冲突的核心技术。其基本思想是：不必等到前驱指令将结果写回寄存器堆，而是在结果刚刚产生时，就通过专用的旁路通路直接转发给需要该数据的后续指令。

1
add $t0, $t1, $t2:  IF  ID  EX  MEM  WB
2
                             ↓ EX 阶段末尾结果已产生
3
sub $t3, $t0, $t4:  IF  ID  EX  MEM  WB
4
                             ↑ 通过旁路直接获取 $t0 的新值

重定向的典型转发路径

• EX/MEM 转发：前一条 ALU 指令的运算结果从 EX/MEM 流水线寄存器直接转发给下一条指令的 EX 阶段输入。
• MEM/WB 转发：前一条指令的结果从 MEM/WB 流水线寄存器转发给间隔一条指令的 EX 阶段输入。

注意：对于 lw 指令，数据要到 MEM 阶段末尾才从存储器中读出。如果紧随其后的指令在 EX 阶段就需要该数据，即使有重定向也无法完全消除停顿，此时仍需插入一个气泡。这种情况称为加载-使用型数据冲突（load-use hazard）。

7.3.6 动态分支预测技术#

静态预测方法（如总是预测不跳转）在分支频繁且方向不固定的程序中效果不佳。动态分支预测技术根据分支指令的历史执行记录来预测本次的分支方向。

1
强不跳转(00) ←→ 弱不跳转(01) ←→ 弱跳转(10) ←→ 强跳转(11)

7.3.7 流水线性能分析#

流水线性能计算公式（高权重考点）

设流水线有 $k$ 个功能段，需要执行 $n$ 条指令。

1. 流水线执行时间

若各段执行时间相等，均为 $\Delta t$（即一个时钟周期）：

$T_{\text{流水}} = k \cdot \Delta t + (n - 1) \cdot \Delta t = (k + n - 1) \cdot \Delta t$

其中 $k \cdot \Delta t$ 是第一条指令流过全部 $k$ 个段的时间（建立时间），之后每个 $\Delta t$ 流出一条指令。

若各段执行时间不等，分别为 $\Delta t_1, \Delta t_2, \ldots, \Delta t_k$，则流水线时钟周期取最慢段：

$\Delta t_{\max} = \max(\Delta t_1, \Delta t_2, \ldots, \Delta t_k)$

关于流水线寄存器（锁存器）延迟 $d$：

• 理想公式（不含延迟）：$T_{\text{流水}} = \sum_{i=1}^{k} \Delta t_i + (n-1) \cdot \Delta t_{\max}$
• 实际公式（考虑锁存延迟）：每个功能段的实际耗时应为 $\Delta t_{\max} + d$。此时流水线时钟周期变为 $\Delta t_{\max} + d$。第一条指令耗时 $k \cdot (\Delta t_{\max} + d)$，剩余 $n-1$ 条指令各耗时 $\Delta t_{\max} + d$，总时间变为：

$T_{\text{流水}} = k \cdot (\Delta t_{\max} + d) + (n-1) \cdot (\Delta t_{\max} + d) = (k + n - 1) \cdot (\Delta t_{\max} + d)$考试时需仔细审题是否给出了锁存器延迟时间。

2. 非流水线（串行）执行时间

若各段时间相等： $T_{\text{串行}} = n \cdot k \cdot \Delta t$

若各段时间不等： $T_{\text{串行}} = n \cdot \sum_{i=1}^{k} \Delta t_i$

3. 加速比

$S = \frac{T_{\text{串行}}}{T_{\text{流水}}}$

各段时间相等时：

$S = \frac{n \cdot k \cdot \Delta t}{(k + n - 1) \cdot \Delta t} = \frac{nk}{k + n - 1}$

当 $n \to \infty$ 时：

$S = \frac{nk}{k + n - 1} = \frac{k}{1 + \frac{k-1}{n}} \xrightarrow{n\to\infty} k$

即理想加速比等于流水线段数。

4. 吞吐率

吞吐率是单位时间内流水线完成的指令条数：

$TP = \frac{n}{T_{\text{流水}}}$

各段时间相等时：

$TP = \frac{n}{(k + n - 1) \cdot \Delta t}$

当 $n \to \infty$ 时：

$TP = \frac{n}{(k + n - 1) \cdot \Delta t} = \frac{1}{\left(1 + \frac{k-1}{n}\right) \cdot \Delta t} \xrightarrow{n\to\infty} \frac{1}{\Delta t}$

即理想吞吐率为每个时钟周期完成一条指令。

5. 效率

流水线效率是指各功能段的实际利用率：

$E = \frac{n \cdot k \cdot \Delta t}{k \cdot (k + n - 1) \cdot \Delta t} = \frac{n}{k + n - 1}$

当 $n \to \infty$ 时：

$E = \frac{n}{k + n - 1} = \frac{1}{1 + \frac{k-1}{n}} \xrightarrow{n\to\infty} 1$

即理想效率为 100%。

做题注意事项

1. 区分”各段时间相等”和”各段时间不等”两种情况，后者的流水线时钟周期由最慢段决定。
2. 题目若问”至少”的时钟周期，答案为最慢段的执行时间。
3. 有的题目会额外考虑流水线寄存器的延迟（锁存延迟），此时 $\Delta t_{\max}$ 要加上锁存延迟。

异常的精确处理#

现代处理器要求实现精确异常：当某条指令发生异常时，该指令之前的所有指令必须全部完成执行并写回结果，该指令之后的所有指令必须被取消（不能产生任何副作用）。

流水线中处理异常的基本步骤：

1. 在发生异常的流水线阶段标记该指令为”异常”。
2. 将异常信息随指令一起在流水线寄存器中向后传递。
3. 当异常指令到达可提交点（通常在写回 WB 或专门的 Commit 阶段）时，统一进行异常处理：保存 PC（异常返回地址）、冲刷流水线中该指令之后的所有指令、跳转到异常处理程序入口。不能在异常发生的早期直接处理，以防该指令原本就该因前面的分支被冲刷而取消。

外部中断的处理#

外部中断通常在每条指令的 WB 阶段末尾进行检测和响应。处理器完成当前正在 WB 阶段的指令，冲刷流水线中其余指令，保存断点后转入中断服务程序。

超标量流水线#

超标量处理器在每个时钟周期内可以同时发射多条指令（如 2 发射、4 发射），这些指令进入多条并行的流水线中同时执行。

• 需要配置多套功能部件（多个 ALU、多个访存端口等）。
• 需要更复杂的硬件逻辑来检测指令间的依赖关系。
• 理想情况下，$m$ 发射的超标量处理器吞吐率是普通流水线的 $m$ 倍。

超流水线#

超流水线将流水线的每个功能段进一步细分为更多的子段，从而提高时钟频率。

• 段数增加使得时钟周期缩短，单位时间内流出的指令增多。
• 但段数过多会增加流水线寄存器开销，且冲突惩罚增大（冲刷更多阶段）。

超长指令字（VLIW）#

由编译器在编译阶段就将多个可以并行执行的操作打包到一条超长指令字中，硬件直接并行执行这些操作。

• 将指令调度和并行性检测的责任从硬件转移到了编译器。
• 硬件设计简单，但对编译器的优化能力要求极高。

7.9.1 概念与选择题#

【1】流水CPU是由一系列称为“段”的处理线路组成的，一个m段流水线稳定时的CPU的吞吐能力，与m个并行部件的CPU的吞吐能力相比（ ）。（2020-2021第2学期A） A. 具有同等水平的吞吐能力 B. 不具备同等水平的吞吐能力 C. 吞吐能力大于前者的吞吐能力 D. 吞吐能力小于前者的吞吐能力 答案：A

解析：

• A [正确]：在理想满载且没有冲突的情况下，一个 $m$ 段流水线稳定运行时，每个时钟周期可以流出一条指令，其吞吐能力为每个周期 1 条指令。而 $m$ 个并行部件的 CPU，如果其协同机制是每 $m$ 个周期同时流出 $m$ 条指令，则平均下来吞吐率同样是每个周期 1 条指令。因此在特定的协同模型下，两者的吞吐能力具有同等水平。
• B [错误]：在规定两者的协同工作机制等同（如并行部件协同每 $m$ 个周期完成 $m$ 条指令）时，两者的吞吐率相同，具备同等水平的吞吐能力。
• C [错误]：在理想模型下，流水线稳定时的吞吐率最多与相同并行规模的 CPU 持平。若每个并行部件都能在单个周期内独立且并行地完成一条指令，其吞吐率可达 $m$ 条指令/时钟周期，此时流水 CPU 的吞吐能力会小于前者，绝不可能大于前者。
• D [错误]：根据前面的分析，在相同的协同工作模型下，流水 CPU 与并行 CPU 具有同等水平的吞吐率，因此无法判定其吞吐能力必定小于前者。

【2】把一个重复的过程分解为若干个子过程，前一子过程为下一子过程创造执行条件，每个子过程可以与其他子过程同时执行的技术是（ ）技术。（2020-2021第二学期B）

• 正确答案：流水线
• 解析：这是流水线技术最标准的书面定义，核心在于时间上的重叠执行与空间上子部件的独立并行。

【3】某计算机的指令流水线由4个功能段组成，指令流经各功能段的时间（忽略各功能段之间的缓存时间）分别为95ns、80ns、70ns和60ns，则该计算机的CPU时钟周期至少是（ ）。（2022-2023-2考试 / 2020-2021第2学期A变体） A. 95ns B. 80ns C. 70ns D. 60ns 答案：A

解析：

• A [正确]：流水线的时钟周期（即流水线的节拍时长）受制于所有功能段中最慢（即耗时最长）的一段，以此保证该段的操作能够在单个时钟周期内顺利且完整地执行。题目中耗时最长的功能段为 95ns，因此该计算机的 CPU 时钟周期至少是 95ns。
• B [错误]：如果时钟周期设为 80ns，那么耗时 95ns 的流水段无法在单个时钟周期内完成，这会导致流水线无法正常工作。
• C [错误]：如果时钟周期设为 70ns，那么耗时 95ns 和 80ns 的流水段均无法在单个时钟周期内完成。
• D [错误]：如果时钟周期设为 60ns，只有耗时最少的 60ns 流水段能在一个时钟周期内完成，其余所有流水段均会因为周期过短而无法完成相应操作。

【4】请简述影响流水线的三种相关？（2020-2021第2学期A / 计组2019秋18级测试填空题）

• 解答： 影响流水线性能的有控制相关、结构相关（或结构冲突）和数据相关（或数据冲突）：
  1. 控制相关：主要是指遇到了程序转移指令（如跳转或中断）时，流水线因为无法确定下一步正确的执行路径，而不能正确且连续地处理后继指令。
  2. 结构相关（资源相关）：是指多条指令进入流水线后，在同一机器时钟周期内争用同一个功能部件（如算术部件或存储器端口）所发生的物理资源冲突。
  3. 数据相关：即前一条指令执行过程中的数据结果是后一条指令执行过程中所需的源数据。由于流水线在时间上重叠，后一条指令急需该数据时前一条指令尚未将其写回，导致数据依赖冲突。

7.9.2 综合计算题#

【1】四级流水线吞吐率计算（2022-2023-2考试） 题干：某 CPU 主频为 1.03 GHz，采用 4 级指令流水线，每个流水段的执行需要 1 个时钟周期。假定 CPU 执行了 100 条指令，在其执行过程中，没有发生任何流水线阻塞，此时流水线的吞吐率为___条指令/秒。

• 解答：$1 \times 10^9$（或 $10^9$）
• 解析：
  1. 计算执行 100 条指令所需的总时钟周期数： 公式：$T = k + n - 1$，其中段数 $k=4$，指令数 $n=100$。 执行 100 条指令共需时钟周期数 = $4 + 100 - 1 = 103$ 个时钟周期。
  2. 计算所需总时间： 时钟频率 $f = 1.03 \text{ GHz} = 1.03 \times 10^9 \text{ Hz}$。 总时间 $t = 103 \div (1.03 \times 10^9) = \frac{103}{1.03} \times 10^{-9} = 100 \times 10^{-9}$ 秒。
  3. 计算实际吞吐率（TP）： $\text{TP} = n \div t = 100 \div (100 \times 10^{-9}) = \frac{100}{100} \times 10^{9} = 1 \times 10^9$ 条指令/秒。
  • (注：吞吐率计算严格遵守公式，切勿直接以主频作答。只有当指令数 $n$ 趋于无穷大时，流水线的吞吐率才无限逼近于主频 $1.03 \times 10^9$)。

习题7.1 解释下列名词#

题干：

流水线技术、指令流水线、运算流水线、流水寄存器、流水时空图、数据冲突、结构冲突、控制相关、先写后读冲突、先读后写冲突、写后写冲突、气泡、重定向、延迟槽、动态分支预测、超标量技术、超流水线技术、动态多发射技术、静态多发射技术、同步中断、异步中断。

解析：

1. 流水线技术：把一个重复执行的处理过程分成若干个相互衔接的子过程，各子过程由不同功能部件并行工作，使多个任务在不同阶段重叠执行，从而提高系统吞吐率。
2. 指令流水线：把一条指令的执行过程划分为取指、译码、执行、访存、写回等阶段，使多条指令在不同阶段同时推进的 CPU 执行组织方式。
3. 运算流水线：把一个复杂运算划分为多个子运算阶段，使连续输入的数据在不同运算阶段中重叠处理的流水线。例如浮点加法、乘法流水线。
4. 流水寄存器：位于相邻流水段之间的寄存器，用来暂存上一段产生的数据、控制信号和状态信息，使这些信息在下一个时钟周期进入下一流水段。
5. 流水时空图：用横轴表示时间/时钟周期、纵轴表示指令或任务，表格中标出每条指令在各周期所处流水段，用来描述流水线重叠执行过程的图。
6. 数据冲突：后续指令需要使用前面指令尚未产生或尚未写回的数据，导致按原计划执行会得到错误结果的流水线冒险。
7. 结构冲突：同一时钟周期内多条指令竞争同一个硬件资源，例如统一存储器同时被 IF 取指和 MEM 访存使用。
8. 控制相关：分支、跳转、中断等改变程序控制流的指令使后续取指地址无法及时确定，由此产生的相关关系。
9. 先写后读冲突（RAW）：前一条指令先写某寄存器，后一条指令后读该寄存器；若后一条读得太早，会读到旧值。这是真数据相关。
10. 先读后写冲突（WAR）：前一条指令先读某寄存器，后一条指令后写该寄存器；若后一条写得过早，会破坏前一条应读的旧值。这属于反相关。
11. 写后写冲突（WAW）：两条指令都写同一个目的寄存器，若后发射指令先完成写回，会破坏程序规定的最终写入顺序。这属于输出相关。
12. 气泡：为解决冒险而插入流水线的空操作周期，相当于让部分流水段空转，使相关指令等待到安全时刻再执行。
13. 重定向：也称转发或旁路，把某流水段刚产生但尚未写回寄存器堆的结果，直接送到需要该结果的后续流水段输入端。
14. 延迟槽：分支或跳转指令之后的一条或若干条位置，这些位置中的指令不管分支是否发生都先被执行，用来隐藏控制冒险带来的延迟。
15. 动态分支预测：处理器运行时根据分支指令过去的执行历史预测其是否转移及目标地址，以减少控制冒险阻塞。
16. 超标量技术：在一个时钟周期内同时发射多条指令，并由多个功能部件并行执行，从而使理想 CPI 小于 1 的技术。
17. 超流水线技术：把原有流水段进一步细分成更多、更短的流水段，以提高时钟频率和指令吞吐率。
18. 动态多发射技术：由硬件在运行时判断多条指令之间是否独立，并动态决定同一周期发射哪些指令。
19. 静态多发射技术：由编译器在编译时把可并行执行的指令打包或调度好，硬件按编译器安排进行多发射，例如 VLIW/EPIC 的思想。
20. 同步中断：由当前正在执行的指令内部原因引起、可由指令执行位置精确定位的异常，例如溢出、缺页、非法指令。
21. 异步中断：由处理器外部事件引起、与当前指令没有固定同步关系的中断，例如 I/O 完成、时钟中断、外部设备请求。

习题7.2 选择题（考研真题）#

1
I1: ADD R1, R2, R3;   (R2)+(R3) -> R1
2
I2: ADD R5, R2, R4;   (R2)+(R4) -> R5
3
I3: ADD R4, R5, R3;   (R5)+(R3) -> R4
4
I4: ADD R5, R2, R6;   (R2)+(R6) -> R5

1
I1: add   s2, s1, s0      // R[s2] <- R[s1]+R[s0]
2
I2: load  s3, 0(t2)       // R[s3] <- M[R[t2]+0]
3
I3: add   s2, s2, s3      // R[s2] <- R[s2]+R[s3]
4
I4: store s2, 0(t2)       // M[R[t2]+0] <- R[s2]

1
I1  add  s2, s1, s0       // R[s2] <- R[s1]+R[s0]
2
I2  load s3, 0(s2)        // R[s3] <- M[R[s2]+0]
3
I3  beq  t2, s3, L        // if R[t2]==R[s3] jump to L
4
I4  addi t2, t2, 20       // R[t2] <- R[t2]+20
5
I5  L1:

习题7.3 简述指令流水线的特点#

题干：

简述指令流水线的特点。

解析：

1. 分段执行：把指令执行过程划分为若干功能段，例如 IF、ID、EX、MEM、WB。
2. 重叠执行：不同指令可同时处在不同流水段中，例如第 1 条执行 EX 时，第 2 条可译码，第 3 条可取指。
3. 提高吞吐率：流水线填满后，理想情况下每个周期可以完成 1 条指令。
4. 不必然缩短单条指令延迟：单条指令仍要依次经过所有阶段，甚至还会多出流水寄存器开销。
5. 要求流水段尽量均衡：时钟周期由最慢流水段决定，若某段明显较慢，会限制整体性能。
6. 需要处理冒险：数据冲突、结构冲突、控制冲突都会破坏理想流水，可能插入气泡或采用转发、预测等技术。
7. 控制更复杂：需要流水寄存器、冒险检测、转发控制、分支处理和异常处理机制。

习题7.4 简述采用插入气泡方式解决数据冲突的主要过程#

题干：

简述采用插入气泡方式解决数据冲突的主要过程。

解析：

1. 检测相关：在译码/读寄存器阶段检查当前指令的源寄存器是否等于前面尚未写回指令的目的寄存器。
2. 发现冲突：若当前指令需要的操作数还没有写回寄存器堆，就产生 RAW 数据冲突。
3. 冻结相关流水段：保持 PC 和 IF/ID 流水寄存器不变，使当前指令停留在 ID 段，后继指令不能继续向前推进。
4. 插入空操作：向后面的 EX 段送入一个空操作 NOP，也就是在流水线中插入一个气泡。
5. 让前序指令继续前进：产生数据的指令继续执行，直到结果写回寄存器或达到可被使用的时刻。
6. 恢复流水：当相关数据已可安全读取后，解除冻结，原来被阻塞的指令继续进入 EX 段。

这种方法硬件简单，但牺牲流水线性能，因为气泡周期内没有完成有效工作。

习题7.5 简述采用重定向方式解决数据冲突的主要过程#

题干：

简述采用重定向方式解决数据冲突的主要过程。

解析：

1. 检测源/目的寄存器关系：判断当前指令的源寄存器是否与前面流水段中指令的目的寄存器相同。
2. 判断结果是否已经产生：如果前面指令的结果已经在 EX/MEM 或 MEM/WB 等流水寄存器中产生，但尚未写回寄存器堆，就可以转发。
3. 选择旁路输入：通过多路选择器，把前面流水段中的运算结果或访存结果直接送到后续指令的 ALU 输入端、比较器输入端或 store 数据输入端。
4. 避免等待写回：后续指令不必等结果写回寄存器堆再读寄存器，从而减少气泡。
5. 必要时仍需阻塞：若结果尚未产生，例如 load-use 情况中 load 数据到 MEM 段末才可用，而下一条指令 EX 段已经需要该值，则仍需插入 1 个气泡。

习题7.6 流水线方式缩短的是指令的执行时间还是程序的执行时间？#

题干：

流水线方式缩短的是指令的执行时间还是程序的执行时间？

解析：

流水线方式主要缩短的是程序的总执行时间，不是单条指令的执行时间。

推导如下：

1. 非流水方式下，若一条指令需要经过 5 个阶段，则一条指令完成后，下一条指令才开始。
2. 流水方式下，第 1 条指令进入 ID 段时，第 2 条指令就可以进入 IF 段，多条指令重叠执行。
3. 对单条指令而言，它仍然要经过 IF、ID、EX、MEM、WB 等所有阶段。
4. 由于阶段之间还要加入流水寄存器，单条指令的延迟甚至可能略有增加。
5. 但对整个程序而言，流水线填满后可以接近每周期完成 1 条指令，因此程序总执行时间明显缩短。

结论：流水线提高的是指令吞吐率，缩短的是大量指令组成的程序的执行时间。

习题7.7 简述流水线中断和非流水线中断处理的差异#

题干：

简述流水线中断和非流水线中断处理的差异。

解析：

1. 非流水线处理器中断处理较简单：同一时刻通常只有一条指令处于执行过程中，因此只要当前指令执行完毕，再保存断点和状态即可。
2. 流水线处理器同一时刻有多条指令在执行：发生异常或中断时，前面可能有较早指令尚未完成，后面可能有较晚指令已经部分执行。
3. 流水线需要保证精确中断：中断处理时应表现为某条指令之前的指令都已完成，而该指令及其之后的指令都未改变机器状态。
4. 流水线需要清除或冻结部分指令：通常要让中断点之前的指令完成，取消中断点之后已经进入流水线的指令。
5. 流水线还要保存更多状态：可能需要保存 PC、异常原因、流水线控制状态，并恢复到可重新执行的精确位置。
6. 异步中断可在指令边界处理：外部中断一般可等到合适的指令边界再响应；同步异常通常与具体指令相关，要精确指出引发异常的指令。

习题7.8 气泡流水线时空图#

题干：

如果采用气泡流水线执行下述程序，请给出流水线时空图。注意时空图中最后一个时钟周期第 5 条指令进入 ID 段。

1
addi $s0, $s0, 4
2
lw   $s1, ($s0)
3
add  $s2, $s2, $s1
4
and  $s3, $s1, $s2
5
sub  $s4, $s2, $s2

解析：

本题按 5 段流水线 IF、ID、EX、M、WB 分析。气泡流水线不采用转发，相关指令要等前序指令写回后才能继续。

数据相关关系如下：

1. I1 写 $s0，I2 读 $s0，所以 I2 要等待 I1 的结果。
2. I2 写 $s1，I3 读 $s1，所以 I3 要等待 I2 的结果。
3. I3 写 $s2，I4、I5 都读 $s2，所以 I4、I5 要等待 I3 的结果。

流水线时空图如下：

说明：

1. I2 在 ID 段等待 I1 写回 $s0。
2. I3 在 ID 段等待 I2 写回 $s1。
3. I4 在 ID 段等待 I3 写回 $s2。
4. 第 12 个周期 I5 进入 ID 段，符合题目要求的截止位置。

习题7.9 重定向流水线时空图#

题干：

如果采用重定向流水线执行 7.8 中程序，请给出流水线时空图。注意时空图中最后一个时钟周期第 5 条指令进入 ID 段。

解析：

重定向/转发流水线可以把尚未写回的结果直接送给后续指令使用。

逐条分析：

1. I1 的 ALU 结果 $s0 可从 I1 的 EX/MEM 或 MEM/WB 旁路转发给 I2 的 EX 段地址计算，因此 I1→I2 不需要气泡。
2. I2 是 load 指令，$s1 到 MEM 段末才得到；I3 紧随其后在 EX 段就要使用 $s1，所以 I2→I3 是 load-use 冒险，需要 1 个气泡。
3. I3 的 ALU 结果 $s2 可转发给 I4、I5 使用，因此 I3→I4、I3→I5 不需要额外气泡。

流水线时空图如下：

说明：第 5 个周期插入 1 个气泡后，I3 在第 6 个周期进入 EX 段；第 7 个周期 I5 进入 ID 段。

习题7.10 无分支预测时程序执行周期#

题干：

假设重定向流水线中所有分支跳转指令均在 EX 段执行，无分支预测、无分支延迟槽技术，尝试计算下述程序的执行周期。

1
addi $s0,$s0,100      # i=100
2
while_loop:
3
    beq $s0,$0,done      # while (i>0)
4
    addi $s0,$s0,-1      # i=i-1
5
    j while_loop         # 继续循环
6
done:

解析：

按常见 5 段流水线约定：分支/跳转在 EX 段末确定下一条 PC，无预测且无延迟槽时，每条控制转移指令引起 2 个额外阻塞周期。

1. 初始化指令 addi $s0,$s0,100 执行 1 次。

2. beq 的执行次数：

   • 当 $i=100,99,\dots,1$ 时，beq 判断不跳转，共 100 次；
   • 当 $i=0$ 时，beq 判断跳转到 done，再执行 1 次；
   • 所以 $N_{beq}=101$。

3. 循环体中的 addi $s0,$s0,-1 执行次数：$N_{addi\_dec}=100$。

4. j while_loop 执行次数：$N_j=100$。

5. 动态指令总数：$N=1+101+100+100=302$。

6. 理想 5 段流水线执行 $N$ 条指令需要：$N+5-1=302+4=306$ 个周期。

7. 控制转移指令总数：$N_{ctrl}=101+100=201$。

8. 控制冒险额外阻塞周期：$201\times2=402$。

9. 总周期数：$306+402=708$。

答案：708 个时钟周期。

补充：若按”每条分支/跳转额外阻塞 3 个周期”计算，则 $306+201\times3=909$。

习题7.11 动态分支预测最优情况下程序执行周期#

题干：

假设重定向流水线中所有分支跳转指令均在 EX 段执行，采用动态分支预测技术，beq、j 指令都可以进行预测，计算最优情况下 7.10 中程序的执行周期。

解析：

最优情况下，beq 和 j 的方向及目标地址都预测正确，因此不产生控制冒险惩罚。

1. 7.10 已得动态指令总数 $N=302$。
2. 5 段流水线理想执行周期为 $N+5-1=302+4=306$。

答案：306 个时钟周期。

习题7.12 无分支预测时 for 循环程序执行周期#

题干：

假设重定向流水线中所有分支跳转指令均在 EX 段执行，设无分支预测、无分支延迟槽技术，尝试计算下述程序的执行周期。

1
addi $s0,$s0,0        # i=0
2
addi $s1,$s1,0        # sum=0
3
for_loop:
4
    slti $t1,$s0,10      # $t1=(i<10)?1:0
5
    beq $t1,$0,done      # for(i=0;i<10;i++)
6
    addi $s1,$s1,$s0     # sum=sum+i
7
    addi $s0,$s0,1       # i++
8
    j for_loop           # 继续 for 循环
9
done:

解析：

仍按 5 段流水线中分支/跳转在 EX 段确定、无预测时每条控制转移额外阻塞 2 个周期计算。

1. 初始化指令共有 2 条，均执行 1 次：$N_{init}=2$。

2. 循环条件 slti 的执行次数：

   • $i=0,1,\dots,9$ 时循环继续，共 10 次；
   • $i=10$ 时还要执行一次判断以退出循环；
   • 所以 $N_{slti}=11$。

3. beq 每次判断后都执行，次数与 slti 相同：$N_{beq}=11$。

4. 循环体中的 addi $s1,$s1,$s0 执行 10 次：$N_{sum}=10$。

5. addi $s0,$s0,1 执行 10 次：$N_{inc}=10$。

6. j for_loop 在前 10 次循环结束时执行：$N_j=10$。

7. 动态指令总数：$N=2+11+11+10+10+10=54$。

8. 理想 5 段流水线周期数：$N+5-1=54+4=58$。

9. 控制转移指令数：$N_{ctrl}=N_{beq}+N_j=11+10=21$。

10. 控制冒险额外阻塞周期：$21\times2=42$。

11. 总周期数：$58+42=100$。

答案：100 个时钟周期。

补充：若按”每条分支/跳转额外阻塞 3 个周期”计算，则 $58+21\times3=121$。

习题7.13 动态分支预测最优情况下 for 循环程序执行周期#

题干：

假设重定向流水线中所有分支跳转指令均在 EX 段执行，采用动态分支预测技术，beq、j 指令都可以进行预测，计算最优情况下 7.12 中程序的执行周期。

解析：

最优情况下，beq 与 j 都预测正确，不产生控制冒险惩罚。

1. 7.12 已得动态指令总数 $N=54$。
2. 5 段流水线理想执行周期为 $N+5-1=54+4=58$。

答案：58 个时钟周期。

习题7.14 流水线功能部件关键延迟优化#

题干：

对于表 7.6 所示的 MIPS 指令流水线时间参数，如果可以优化流水线一个功能部件的关键延迟以提升处理器整体性能，应该选择哪个部件进行优化？如果这种优化与成本是线性关系，如何优化才能使处理器性能达到最优，且成本最低？

解析：

按流水线性能优化的一般原则，可得出如下确定性结论：

1. 流水线时钟周期由最慢流水段决定：$T_{clk}=\max(T_{IF},T_{ID},T_{EX},T_{MEM},T_{WB})$。
2. 若只能优化一个功能部件，应优先选择位于最大流水段延迟中的关键部件，也就是造成 $T_{clk}$ 最大的瓶颈部件。
3. 若最大延迟流水段只有一个，则优化该段可以直接缩短时钟周期。
4. 若有多个流水段并列最大，则只优化其中一个不能降低整体时钟周期；必须至少把所有并列最大段都优化到低于原最大值，整体性能才会提升。
5. 若优化成本与缩短的延迟线性相关，要使性能达到最优且成本最低，应把瓶颈段优化到刚好等于第二大流水段延迟，而不是继续优化得更短。

理由如下：

• 假设最大流水段延迟为 $T_1$，第二大流水段延迟为 $T_2$，且 $T_1>T_2$。
• 只要把瓶颈段从 $T_1$ 降到 $T_2$，新的时钟周期就变为 $T_2$。
• 若继续把该部件优化到小于 $T_2$，时钟周期仍然受第二大流水段 $T_2$ 限制，性能不再提升。
• 因此最低成本方案是 $T_1 \rightarrow T_2$，即只优化到刚好不再是唯一瓶颈为止。

答案概括：选择处于最长流水段的关键功能部件进行优化；在线性成本条件下，只需把它优化到与第二长流水段延迟相等，此时性能达到该单部件优化能达到的最优，且成本最低。

习题7.15 16 位计算机流水线问题#

题干：

某 16 位计算机中，带符号整数用补码表示，数据 cache 和指令 cache 分离。该计算机采用 5 段流水线方式执行指令：IF、ID、EX、M、WB；流水线按序发射、按序完成；没有采用转发技术处理数据相关问题；并且同一个寄存器的读和写操作不能在同一个时钟周期内进行。回答下列问题。

1
I1    LOAD    R1, [a]
2
I2    LOAD    R2, [b]
3
I3    ADD     R1, R2
4
I4    STORE   R2, [x]

1
I1    LOAD    R1, [x]     ; R1 <- x
2
I2    LOAD    R2, [a]     ; R2 <- a
3
I3    SHL     R1          ; R1 <- 2*x
4
I4    ADD     R2, R1      ; R1 <- R2+R1 = a+2*x
5
I5    STORE   R1, [x]     ; x <- R1

习题7.16 循环程序与分支指令问题#

题干：

某程序中有如下循环代码段 p：for(int i = 0; i < N; i++) sum+=A[i];。编译时变量 sum 和 i 分别分配在寄存器 R1 和 R2 中，常量 N 在寄存器 R6 中，数组 A 的首地址在寄存器 R3 中。程序段 p 的起始地址为 08048100H。M 采用 32 位定长指令字，分支指令 bne 采用相对寻址，OFFSET 为补码偏移量。回答下列问题并说明理由。

1
1  loop: sll  R4,R2,2       ; R4 <- R2 << 2
2
2        add  R4,R4,R3      ; R4 <- R4 + R3
3
3        load R5,0(R4)      ; R5 <- M[R4+0]
4
4        add  R1,R1,R5      ; R1 <- R1 + R5
5
5        add  R2,R2,1       ; R2 <- R2 + 1
6
6        bne  R2,R6,loop    ; if R2 != R6 goto loop

汇总答案#

• 7.2 选择题答案：1. C；2. A；3. D；4. B；5. C；6. C；7. A；8. D；9. A；10. C；11. B；12. C
• 7.8：气泡流水线截止到 I5 进入 ID 段为第 12 个周期
• 7.9：重定向流水线截止到 I5 进入 ID 段为第 7 个周期
• 7.10：按每个控制转移 2 个额外阻塞周期为 708 周期；若按 3 个额外阻塞周期为 909 周期
• 7.11：306 周期
• 7.12：按每个控制转移 2 个额外阻塞周期为 100 周期；若按 3 个额外阻塞周期为 121 周期
• 7.13：58 周期
• 7.15（1）：FEFFH；（2）：8 周期；（4）：17 周期
• 7.16：（1）字节编址；（2）32 位；（3）OFFSET=FFFAH=-6，目标地址公式为 $(PC+4)+(sign\_extend(OFFSET)<<2)$；（4）指令 2、3、4、6 因数据相关阻塞，指令 6 发生控制冒险