指令流水线

发表于 更新于 阅读次数： Waline： 本文字数： 6.6k 阅读时长 ≈ 24 分钟

流水线概述

如果将指令的每个阶段看成相应的流水段，则指令的执行过程构成了一条指令流水线。

一条指令流水线由如下 5 个流水段组成：

  • 取指令（IF）：从存储器取指令；
  • 指令译码（ID）：产生指令执行所需的控制信号；
  • 取操作数（OF）：读取操作数；
  • 执行（EX）：对操作数完成指定操作；
  • 写回（WB）：将结果写回。

当后一条指令的第 i 步与前一条指令的第 i+1 步同时进行，可以使一串指令总的完成时间大为缩短。

理想情况下，每个时钟都有一条指令进入流水线，每个时钟周期都有一条指令完成，每条指令的时钟周期数（即 CPI）都为 1。

load 指令流水线

对于 load 指令的五个阶段：

  1. Ifetch（取指）：取指令并计算 PC + 4
    • 指令存储器、Adder
  2. Reg/Dec（取数和译码）：取数的同时译码
    • 寄存器堆读口、指令译码器
  3. Exec（执行）：计算内存单元地址
    • 扩展器、ALU
  4. Mem（读存储器）：从数据存储器中读
    • 数据存储器
  5. Wr（写寄存器）：将数据写到寄存器中
    • 寄存器堆写口

load 指令的流水线如上所示，每个周期有五个功能部件同时在工作，后面指令在前面完成取指后马上开始。每个load 指令仍需要 5 个周期，但吞吐率（throughput）提高了许多。

理想情况下有：

  • 每个周期有一条指令进入流水线
  • 每个周期都有一条指令完成
  • 每条指令的有效周期（CPI）为 1

流水线方式下，单条指令执行时间不能缩短，但能大大提高指令吞吐率。

适合流水线的指令集特征

「规整」「简单」和「一致」等特性有利于指令的流水线执行：

  • 长度尽量一致：有利于简化取指令和指令译码操作。
  • 格式少，且源寄存器位置相同：有利于在指令未知时就可取操作数。
    • 若位置随指令不同而不同，则需先确定指令类型才能取寄存器编号。
  • load 和 store 指令才能访问寄存器：有利于减少操作步骤，规整流水线。
    • load 和 store 指令的地址计算和运算指令的执行步骤规整在同一个周期。
  • 内存中「对齐」存放：有利于减少访存次数和流水线的规整。

流水线处理器的实现

指令功能段划分

load 指令的流水线

如下图所示：

R-型指令功能段划分

如下图所示：

I-型指令功能段划分与 R-型指令相同。

store 指令功能段划分

如下图所示：

beq 指令功能段划分

如下图所示：

j 指令功能段划分

如下图所示：

5 段流水段数据通路

取指令阶段（Ifetch）

指令部件 IUnit 的设计：

勘误：上图中的「10」应为「12」。

译码/取数阶段（Reg/Dec）

执行阶段（Exec）：load 指令的地址计算阶段

执行部件 Exec Unit 的设计：

执行部件功能：

  • 计算内存地址
  • 计算转移目标地址
  • 一般 ALU 运算

存储器访问阶段（Mem）：load 的存储器读周期

写回阶段（Wr）：load 指令的回写（Write Back）阶段

流水线中的控制信号

PC 无需写使能，因为每个时钟都会改变 PC。流水段寄存器同理。

  • Ifetch 和 Dec/Reg 阶段都没有控制信号。
  • Exec 阶段控制信号
    • ExtO（扩展器操作）：1 是符号扩展，0 是零扩展。
    • ALUSrc（ALU 的 B 口来源）：1 来源于扩展器，0 来源于 BusB
    • ALUOp（主控制器输出，用于辅助局部 ALU 控制逻辑来决定 ALUCtrl）
    • RegDst（指定目的寄存器）：1 为 Rd，0 为 Rt
  • Mem 阶段的控制信号：
    • MemWr（DM 的写信号）：store 指令为 1，其他指令为 0
    • Branch（是否为分支指令）：分支指令时为 1，其他指令为 0
  • Wr 阶段的控制信号：
    • MemtoReg（寄存器的写入源）：1 DM 输出，0 为 ALU 输出
    • RegWr（寄存器堆写信号）：结果写寄存器的指令为 1，其他指令为 0

流水线冒险及其处理

冒险（Hazards）指流水线遇到无法正确执行后续指令，或执行了不该执行的指令。

  • 结构冒险（Structural Hazards）：硬件资源冲突
    • 现象：同一个部件同时被不同指令所使用
    • 解决方法：
      • 一个部件每条指令只能使用1次，且只能在特定周期使用
      • 设置多个部件，以避免冲突。如指令存储器 IM 和数据存储器 DM 分开
  • 数据冒险（Data hazards）：数据冲突
    • 现象：后面指令用到前面指令结果数据时，前面指令的结果还没产生
    • 解决方法：
      • 采用转发（Forwarding/Bypassing）技术
      • Load-use 冒险需要一次阻塞（stall）
      • 编译程序优化指令顺序
  • 控制冒险（Control hazards）：指令执行顺序改变
    • 现象：转移或异常改变执行流程，后继指令在目标地址产生前已被取出
    • 解决方法：
      • 采用静态或动态分支预测
      • 编译程序优化指令顺序（分支延迟）

结构冒险

现象

只有一个存储器时，在 load 指令取数据同时又取指令的话，就会发生冲突。

若不对寄存器堆的写口和读口独立设置的话，就会发生冲突。

结构冒险也成为「硬件资源冲突」：同一个执行部件被多条指令使用。

解决方案

为了避免结构冒险，规定流水线数据通路中功能部件的设置原则为：

  • 每个部件在特定的阶段被用（如：ALU总在第三阶段被用！）
  • 将指令存储器（Im）和数据存储器（Dm）分开
  • 将寄存器读口和写口独立开来

数据冒险

现象与解决方案

对于以下的指令序列，寄存器 r1 会发生数据冒险：

1
2
3
4
5
add r1,  r2, r3
sub r4,  r1, r3  # 读 r1 时，add 指令正在执行加法（EXE），老值
and r6,  r1, r7  # 读 r1 时，add 指令正在传递加法结果（MEM），老值
or  r8,  r1, r9  # 读 r1 时，add 指令正在写加法结果到 r1（WB），老值
xor r10, r1, r11 # 读 r1 时，add 指令已经把加法结果写到 r1，新值

最后一条指令的 r1 才是新的值。

三类数据冒险现象：

  • RAW：写后读（基本流水线中经常发生，如上例）
  • WAR：读后写（基本流水线中不会发生，乱序执行时会发生）
  • WAW：写后写（基本流水线中不会发生，乱序执行时会发生）

本节仅考虑 RAW 冒险。

有几种解决方案：

  1. 硬件阻塞（stall）
  2. 软件插入 NOP 指令
  3. 合理实现寄存器堆的读/写操作（但不能解决所有的数据冒险）
    • 前半时钟周期写，后半时钟周期读，若同一个时钟内前面指令写入的数据正好是后面指令所读数据，则不会发生数据冒险。
  4. 转发（Forwarding 或 Bypassing 旁路）技术
    • 若相关数据是 ALU 结果，可通过转发解决
    • 若相关数据是上条指令 DM 读出内容，不能通过转发解决，随后指令需被阻塞一个时钟或加 NOP 指令 （称为 Load-use 数据冒险）
  5. 编译优化：调整指令顺序（不能解决所有数据冒险）

实现「转发」和「阻塞」需要修改数据通路。

硬件阻塞

在硬件上采取措施，使相关指令延迟执行。

硬件上通过阻塞（stall）方式阻止后续指令执行，延迟到有新值以后。这种做法称为流水线阻塞，也称为插入「气泡」（Bubble）。

缺点：

  • 控制比较复杂，需要修改数据通路
  • 指令被延迟三个时钟执行

软件插入无关指令

由编译器插入三条 NOP 指令，浪费了三条指令的空间和时间。是最差的做法。

优点：无需修改数据通路。

与上一个方案都是多三个时钟周期。

同一周期内寄存器堆先写后读

寄存器堆的读口和写口是相互独立的部件。

寄存器写口/读口分别在前/后半周期进行操作，使写入数据被直接读出。

但是只能解决部分数据冒险。

利用数据通路中的中间数据：转发 + 阻塞

流水段寄存器中已有需要的值 r1，可将数据从流水段寄存器中直接取到 ALU 的输入端，称为「转发」或「旁路」。

硬件上的改动以支持「转发」技术：加入 MUX，使得流水段寄存器值返回 ALU 输入端。

若指令序列为

1
2
3
lw  r3, 100(r1)
or  r6, r3, r1
sub r5, r3, r4

则不能通过「转发」技术来解决 1、2 条指令间的数据冒险。

load 指令最早在哪个流水线寄存器中开始有后续指令需要的值？

  • 实际上，在第四周期结束时，数据在流水段寄存器中已经有值。
  • 采用数据转发技术可以使load指令后面第二条指令得到所需的值；但不能解决 load 指令和随后第一条指令间的数据冒险，要延迟执行一条指令.

这种 load 指令和随后指令间的数据冒险，称为「装入-使用数据冒险（load-use Data Hazard）」.

采用「转发」后仅第二条指令 sub r7, r1, r3 不能按时执行。

发生「装入-使用数据冒险」时，需要对 load 后的指令阻塞一个时钟周期.

数据冒险处理最佳方案：「转发」+「Load-use 阻塞」

RAW(写后读) 数据冒险的「转发」条件：

指令的回写阶段：

以下两种情况，转发会发生错误：

  • 指令的结果不写入目的寄存器 Rd 时
    • 例如 beq 指令只对 rs 和rt 相减，不写结果到目的寄存器 Rt
  • Rd 等于 $0 时
    • 例如 sll $0, $1, 2 转发结果为 R[$1] << 2，但实际上应该是 0

因此修改转发条件如下：

转发路径和转发条件：

更复杂的数据冒险问题：

硬件阻塞方式（Load-use Data Hazard）：

编译器调整指令顺序

控制冒险

现象与解决方案

虽然 beq 指令在第四周期取出，但：

  • 「是否转移」在 Mem 阶段确定，目标地址在第七周期才被送到 PC 输入端
  • 第八周期才取出目标地址处的指令执行
  • 结果：在取目标指令之前，已有三条指令被取出，取错了三条指令。

发生转移时，要在流水线中清除 beq 后面的三条指令，分别在 EXE 、ID、 IF 段中

延迟损失时间片 C：发生转移时，给流水线带来的延迟损失。

  • 这里 C 为 3。

解决方案：

  1. 硬件上阻塞分支指令后三条指令的执行
    • 使后面三条指令清 0 或其操作信号清 0，以插入三条 NOP 指令
    • 效率低，需结合分支预测
  2. 软件上插入三条 NOP 指令
    • 效率低，需结合分支预测
  3. 分支预测（Predict）
    1. 简单（静态预测）：
      • 总是预测条件不满足（not taken），即：继续执行分支指令的后续指令
      • 可加启发式规则：在特定情况下总是预测满足（taken），其他情况总是预测不满足。如：循环顶部（底部）分支总是预测为不满足（满足）。能达 65% ~ 85% 的预测准确率
    2. 动态预测：
      • 根据程序执行的历史情况进行动态预测调整，能达 90% 的预测准确率
      • 流水线控制必须确保被错误预测指令的执行结果不能生效，而且要能从正确的分支地址处重新启动流水线工作
  4. 延迟分支（Delayed branch）
    • 通过编译程序优化指令顺序
    • 把分支指令前面与分支指令无关的指令调到分支指令后执行，也称延迟转移

另一种控制冒险：异常或中断控制冒险的处理。

简单（静态）分支预测

基本做法：

  • 总预测条件不满足（not taken），即：继续执行分支指令的后续指令
    • 可加启发式规则：在特定情况下总是预测满足（taken），其他情况总是预测不满足
  • 预测失败时，需把流水线中三条错误预测指令丢弃掉
    • 将被丢弃指令的控制信号值或指令设置为 0
    • 注：涉及到当时在 IF、ID 和 EX 三个阶段的指令

预测错误的代价与何时能确定是否转移有关。越早确定代价越少。

可以将判断转移的工作提前，而不等到 MEM 阶段才确定。

缩短分支延迟，减少错误预测代价

  • 可以将 「转移地址计算」和「分支条件判断」操作调整到 ID 阶段来缩短延迟
    • 将转移地址生成从 MEM 阶段移到 ID 阶段是可能的：IF/ID 流水段寄存器中已经有 PC 的值和立即数）
    • 将「判 0」操作从 EX 阶段移到 ID 阶段：
      • 用逻辑运算（如，先按位异或，再结果各位相或）来直接比较 Rs 和 Rt 的值
      • 简单判断用逻辑运算，复杂判断可以用专门指令生成条件码
      • 许多条件判断都很简单

预测错误的检测和处理（称为「冲刷、冲洗」Flush）

  • 当 Branch=1 并且 Zero=1 时，发生转移（taken）
  • 增加控制信号：IF.Flush=Branch and Zero，取值为 1 时，说明预测失败
  • 预测失败（条件满足）时，完成以下两件事（延迟损失时间片 C=1 时）：
    • 将转移目标地址->PC
    • 清除 IF 段中取出的指令，即：将 IF/ID 中的指令字清 0，转变为 NOP 指令

动态分支预测

简单的静态分支预测方法的预测成功率不高，应考虑动态预测。

动态预测基本思想：

  • 利用最近转移发生的情况，来预测下一次可能转移还是不转移
  • 根据实际情况来调整预测
  • 转移发生的历史情况记录在 BHT 中（有多个不同的名称）
    • 分支历史记录表 BHT（Branch History Table）
    • 分支预测缓冲 BPB（Branch Prediction Buffer）
    • 分支目标缓冲 BTB（Branch Target Buffer）
  • 每个表项由分支指令地址低位作索引，故在 IF 阶段就可以取到预测位
    • 低位地址相同的分支指令共享一个表项，所以，可能取的是其他分支指令的预测位。但由于仅用于预测，所以不影响执行结果

动态预测基本方法：

  • 一位预测位：总是按上次实际发生的情况来预测下次
    • 1 表示最近一次发生过转移（taken），0 表示未发生（not taken）
    • 预测时，若为1，则预测下次taken，若为0，则预测下次not taken
    • 实际执行时，若预测错，则该位取反，否则，该位不变
      可用一个简单的预测状态图表示
    • 缺点：当连续两次的分支情况发生改变时，预测错误
      • 例如，循环迭代分支时，第一次和最后一次会发生预测错误，因为循环的第一次和最后一次都会改变分支情况，而在循环中间的各次总是会发生分支，按上次的实际情况预测时，都不会错。
  • 采用二位预测位
    • 用 2 位组合四种情况来表示预测和实际转移情况
    • 按照预测状态图进行预测和调整
    • 在连续两次分支发生不同时，只会有一次预测错误

采用较多的是二位或二位以上预测位。

一位预测状态图：

二位预测状态图：

分支延迟时间片的调度

控制冒险（异常和中断）

异常和中断会改变程序的执行流程：

  • 某条指令发现异常时，后面多条指令已被取到流水线中正在执行
    • 例如 ALU 指令发现「溢出」时，已经到 EX 阶段结束了，此时，它后面已有两条指令进入流水线了。

流水线数据通路处理异常思路：假设指令 add r1, r2, r3 产生了溢出，MIPS 异常处理程序首地址为 0x8000 0180。

  • 清除 add 指令以及后面的所有已在流水线中的指令
  • 关中断（将中断允许触发器清 0）
  • 保存 PC 或 PC - 4（断点） 到 EPC
  • 0x8000 0180 送 PC（从 0x8000 0180 处开始取指令）

异常的处理：

异常处理的流水线数据通路：

流水线方式下异常处理的难点问题：

  1. 流水线中同时有 5 条指令，到底是哪一条发生异常？
    • 根据异常发生的流水段可确定是哪条指令，因为各类异常发生的流水段不同
      • 「溢出」在 EXE 段检出
      • 「无效指令」在 ID 段检出
      • 「除数为 0」在 ID 段检出
      • 「无效指令地址」在 IF 段检出
      • 「无效数据地址」在 load/store 指令的 EXE 段检出
  2. 外部中断与特定指令无关，如何确定处理点？
    • 可在 IF 段或 WB 段中进行中断查询，需要保证当前 WB 段的指令能正确完成，并在有中断发生时，确保下个时钟开始执行中断服务程序
  3. 检测到异常时，指令已经取出多条，当前 PC 的值已不是断点，怎么办？
    • 指令地址存放在流水段 R，可把这个地址送到 EPC 保存，以实现精确中断非精确中断不能提供准确的断点，而由操作系统来确定哪条指令发生了异常
  4. 一个时钟周期内可能有多个异常，该先处理哪个？
    • 异常：检出异常后，其原因存到专门寄存器中并流到最后阶段处理，使前面指令的异常优先级高于后面指令
    • 中断：在中断查询程序或中断优先级排队电路中按顺序查询
  5. 系统中只有一个 EPC，多个中断发生时，一个 EPC 不够放多个断点，怎么办？
    • 总是把优先级最高的送到 EPC 中
  6. 在异常处理过程中，又发生了新的异常或中断，怎么办？
    • 利用中断屏蔽和中断嵌套机制来处理

高级流水线技术

实现指令流内部的并行流水线称为指令级并行（Instruction Level Parallelism, ILP）。

  • –
    超流水线（Super-pipelining）
    • 级数更多的流水线 CPI =1
    • 理想情况下，流水线的加速比与流水段的数目成正比（即：理想情况下，流水段越多，时钟周期越短，指令吞吐率越高）
    • 但是，它会增加开销，且是有极限的。可以怎样突破极限呢？
    • 开销体现在流水段寄存器。
  • 多发射流水线（Multiple issue pipelining）
    • 多条指令（如整数运算、浮点运算、装入/存储等） 同时启动并独立运行
    • 前提：有多个执行部件。如：定点、浮点、乘/除、取数/存数部件等
    • 结果：能达到小于 1 的 CPI，定义 CPI 的倒数为 IPC（例如：理想的四路多发射流水线的 IPC 为 4）
    • 需要实现以下两个主要任务
      • 指令打包：分析每个周期发射多少条？哪些指令可以同时发射？
      • 冒险处理：由编译器静态调整指令或在运行时由硬件处理
    • 实现上述两个主要任务的基础——推测技术
    • 两种实现方法
      • 静态多发射：由编译器在编译时静态完成指令打包和冒险处理
      • 动态多发射：由硬件在执行时动态完成指令打包和冒险处理

推测

推测技术：由编译器或处理器猜测指令执行结果，并以此来调整指令执行顺序，使指令的执行能达到最大可能的并行。

  • 软件推测：编译器通过推测来静态重排指令（一定要正确）
  • 硬件推测：处理器在运行时通过推测来动态调度指令

需有推测错误检测和回滚机制。推测错误时会增加额外开销。

静态多发射处理器

  • 指令打包（将同时发射的多条指令合并到一个长指令中）
    • 将同一个时钟周期内发射的多个指令看成是一条多个操作的长指令，称为一个「发射包」
    • 「静态多发射」也被称为「超长指令字」（Very Long Instruction Word, VLIW），采用这种技术的处理器被称为 VLIW 处理器
    • 在同一个周期内发射的指令类型是受限制的（举例：干洗/水洗）
      • （例如，只能是一条 ALU 指令/分支指令、一条 load/store 指令）
    • IA-64 采用这种方法，Intel 称其为 EPIC（Explicitly Parallel Instruction Computer——显式并行指令计算机）
  • 冒险处理（主要是数据冒险和控制冒险）两种做法：
    1. 完全由编译器通过代码调度和插入 NOP 指令来消除所有冒险，无需硬件实现冒险检测和流水线阻塞
    2. 由编译器通过静态分支预测和代码调度来消除同时发射指令间内部依赖，由硬件检测数据冒险并进行流水线阻塞
    • 即：保证打包指令内部不会出现冒险！

2 发射流水线数据通路：

优点：潜在性能将提高大约 2 倍

缺点：

  • 为消除结构冒险，需增加额外部件
  • 增加了潜在的由于数据冒险和控制冒险导致的性能损失
    • 例 1：对于 Load-use 数据冒险
      • 单发射流水线：只有一条指令延迟
      • 2 发射流水线：有一个周期（即 2 条指令）延迟
    • 例 2：对于 ALU-Load/Store 数据冒险
      • 单发射流水线：可用「转发」技术使 ALU 结果直接转发到 load/store 指令的 EXE 阶段
      • 2 发射流水线：两条指令同时进行，ALU 的结果不能直接转发，因而不能提供给与其配对的 load/store 指令使用，只能延迟一个周期

为更有效地利用多发射处理器的并行性，必须有更强大的编译器，能够充分消除指令间的依赖关系，使指令序列达到最大的并行性。

循环中访问数组更好的调度技术——「循环展开」技术：

  • 好处：充分利用并行，消除部分循环分支
  • 代价：多使用了临时寄存器，增加了代码大小（存储空间变大）

动态多发射处理器

由硬件在执行时动态完成指令打包或冒险处理，通常被称为超标量处理器（Superscalar）

  • 同一个时钟动态发射多条指令，一个周期内可执行一条以上指令

与 VLIW 处理器的不同点：

  • VLIW 处理器：与机器结构密切相关，在结构有差异的机器上要重新编译
  • 超标量处理器：编译器仅进行指令顺序调整（还是串行序列），不进行指令打包，而是由硬件根据机器结构决定同时发射哪几条指令。因此，编译后的代码能够被不同结构的机器正确执行。

超标量处理器多结合动态流水线调度（Dynamic pipeline scheduling）技术：

  • 通过指令相关性检测和动态分支预测等手段，投机性地不按指令顺序执行，当发生流水线阻塞时，可以到后面找指令来执行

动态多发射处理器的通用模型：

  • 指令预取和译码单元：预取的指令经译码后，放到指令队列中；
  • 指令分派器：确定何时发射哪条指令到哪个功能单元中；
  • 功能单元：如整数部件、浮点部件、存/取部件；
  • 重排序缓冲：保存已完成的指令结果，等待在可能时写回寄存器堆。

根据动态流水线指令发射和完成顺序，可分为三种执行模式：

  • 按序发射按序完成
    • 保守的，能简化异常检测及其处理，同时能在被推测指令完成前得知推测结果的正确性。
  • 按序发射无序完成
  • 无序发射无序完成

  • 重排序缓存（Reorder Buffer）：用于保存已完成的指令结果，等待在可能时写回寄存器堆。
  • 写回条件：与前面的所有指令不相关，并预测正确

按序发射按序完成：

按序发射无序完成：

无序发射无序完成：

动态流水线调度的必要性：编译器可依据数据依赖关系调度代码，为什么还要超标量处理器来动态调度？

  • 并不是所有阻塞都能事先确定，动态调度可在阻塞时，提前执行无关指令
    • 例如，Cache 缺失是不可预见的阻塞
  • 动态分支预测需要根据执行的真实情况进行预测
  • 采用动态调度使得硬件将处理器细节屏蔽起来
    • 不同处理器的发射宽度、流水线延时等可能不同，流水线的结构也会影响循环展开的深度。通过动态调度使得处理器细节被屏蔽起来，软件发行商无需针对同一指令集的不同处理器发行相应的编译器，并且，以前的代码也可在新的处理器上运行，无需重新编译

高性能微处理器并不能持续进行多条指令的发射，原因有：

  • 指令间的高度依赖关系限制了指令之间的并行执行，特别是隐含依赖关系的存在。例如，使用指针的代码段，存在隐含依赖。
  • 分支指令预测错误。
  • 内存访问引起的阻塞（Cache 缺失、缺页等）使得流水线难以满负荷运转。