第3章 流水线技术
流水线技术的基本概念：
把一个重复的过程分为若干子过程，每个子过程由专门的部件来实现。
基本概念详细解释：
把多个处理过程在时间上错开，依次通过各功能段，这样每个子过程就可以与其他子过程并行执行。
流水线的级或段：
流水线中的每个处理过程或功能部件称为流水线的“级”或“段”，多个段组成一个流水线。
流水线的深度：
段的数量。
指令流水线：
把流水线技术应用于指令的解释执行过程中。
运算操作流水线：
把流水线技术应用到运算的执行过程中。
流水线的工作过程：
从时间和空间两方面来描述流水线的工作过程，横坐标代表时间，纵坐标代表空间。
-
通过时间：从第一个任务进入流水线到流出结果所需的时间。
-
排空时间：最后一个任务进入流水线到流出结果所需的时间。
流水线技术特点：
-
流水线技术把一个完整过程分解成若干子过程，每个子过程都有一个专门的功能部件来实现。
-
流水线都有通过时间和排空时间。
-
流水线技术适用于大量重复的顺序过程，只有输入端不断地提供任务，才能充分发挥流水线的效率。
-
流水线中各段的时间应尽可能相同，否则容易发生阻塞或断流，时间最长的段称为“瓶颈”。
-
流水线的每一段后面都要有一个缓冲寄存器，用于在相邻的两段之间传输数据，为后续流水段提供所需信息，并把各段之间的处理工作相互隔离。
流水线的分类：
按级别分类：
-
部件级流水线：把处理机部件分段，并把各段连接起来，使各种不同运算操作可以按流水线方式进行。
-
处理机级流水线：把指令的执行过程按流水线方式进行，把一个完整过程分解成若干子过程来执行，每个子过程由专门的功能部件执行。
例如：IF段 → ID段 → EX段 → MEM段 → WB段（指令流水线中的典型阶段）
按功能分类：
-
单功能流水线：各段之间的连接固定不变，只能完成一种固定功能的流水线。
-
多功能流水线：流水线中的各段可以进行不同连接，以实现不同的流水功能。
3.2 流水线分类（续）
静态流水线 vs 动态流水线
-
静态流水线
在同一时间内，各段只能按同一种功能的连接方式进行工作。
当流水线要执行其他功能时，必须等待前面的任务全部完成并排空后，才能改变连接方式。 -
动态流水线
在同一时间内，允许流水线中某些段以不同方式进行连接，同时执行多种功能。
例如：一部分段在执行一个流水线功能的同时，另一些段在执行另一个功能。
✅ 优点：相比静态流水线，能够提高各段的利用率，从而提升流水线效率。
⚠️ 缺点：控制更复杂，必须确保各段之间不发生冲突。
线性流水线 vs 非线性流水线
-
线性流水线
各段之间串行连接，没有反馈回路，数据在流水线中只流过一次。 -
非线性流水线
存在反馈回路，数据可能在流水线中多次循环。
顺序流水线 vs 无序流水线
-
顺序流水线
输出任务的顺序必须与输入顺序一致。 -
无序流水线
输出任务的顺序可以与输入顺序不同。
3.3 性能指标
1. 吞吐率（Throughput, TP）
- 定义：单位时间内流水线所完成的任务数量或输出结果数。
- 公式：
设任务数为
n，完成时间为Tk，则 - TP = n / Tk
若每段处理时间为 `Δt`，且流水线有 `K` 段，则
Tk = (K + n - 1) · Δt TP = n / [(K + n - 1) · Δt]
当 `n ≫ K` 时，**最大吞吐率**为
TP_max = 1 / Δt
若各段时间不等，则最大吞吐率由**最慢段（瓶颈）**决定：
TP_max = 1 / max(Δt_i)
2. 加速比（Speedup, S）
- 定义：完成同一批任务，不使用流水线与使用流水线所用时间的比值。
- 公式： S = T_不使用 / T_使用 = (n · K · Δt) / [(K + n - 1) · Δt] = nK / (K + n - 1)
当 `n → ∞` 时，**最大加速比**为
S_max = K
3. 效率（Efficiency, E）
- 定义：流水线中设备的实际工作时间与总运行时间的比值。
- 由于存在通过时间和排空时间，在完成
n个任务的时间内，流水线并非全程满载。 - 效率公式：
- E = n / (K + n - 1)
当 `n → ∞` 时，**最大效率**为
E_max = 1
3.4 流水线瓶颈问题与解决方案
瓶颈问题：
- 多个任务集中在某一段，造成重复设置瓶颈段。
- 缺点：增加硬件成本，控制复杂。
3.5 非流水线 vs 流水线执行过程
非流水线方式下，一条指令的执行分为以下周期：
- 取指周期（IF）
- 指令译码（ID）
- 读寄存器周期
- 执行周期（EX）
- 存储访问（MEM）
- 写回寄存器（WB）
采用流水线方式实现时，应注意以下问题：
- 同一时钟周期内，不能要求同一功能段实现两种功能
→ 避免结构冲突（如 IF 段与 MEM 段同时访问内存） - 避免 ID 段与 WB 段对同一通用寄存器的访问冲突
→ 数据读写冲突（如读后写、写后读） - PC 更新问题
→ 需专门设置一个加法器用于 PC+4 操作
3.6 指令间相关（Hazard）
定义：
两条指令之间存在相互依赖关系，可能导致执行错误。
三种相关类型：
| 类型 | 说明 |
|---|---|
| 数据相关 | 后一条指令需要前一条指令的结果（RAW） |
| 名相关 | 指令使用相同的寄存器名，但无数据依赖（WAR、WAW） |
| 控制相关 | 由分支指令引起，后续指令是否执行取决于分支结果 |
数据相关特点：
- 具有传递性
若i → j相关，j → k相关，则i → k也相关。
注意事项：
- 当数据流经寄存器时，检测机制较简单；
- 当数据流经存储器时，检测机制较复杂（需地址比较）。
3.7 名相关（Name Dependence）
定义：
指令所访问的寄存器或存储器的名称相同，但没有数据传递关系，则称为名相关。
类型：
| 类型 | 说明 |
|---|---|
| 反相关（WAR） | 指令 i 写入某个名，指令 j 读取该名 |
| 输出相关（WAW） | 指令 i 和指令 j 都写入同一个名 |
特点：
- 名相关不涉及数据传递，只是名字冲突；
- 若其中一条指令被推迟或换名，不会影响另一条指令的执行。
解决方法：换名技术
- 通过改变操作数的名字来消除名相关；
- 对于寄存器名冲突，使用寄存器换名（Register Renaming）。
3.8 控制相关（Control Dependence）
定义：
由分支指令引起的相关，决定是否执行后续指令。
限制：
- 与某条指令存在控制相关的指令，不能移动到该分支指令之前；
- 与某条指令不存在控制相关的指令，不能移动到该分支指令之后。
3.9 流水线冲突（Hazard）
定义：
由于相关或其他原因，使得指令流中的指令不能在指定的时钟周期中执行。
三大类冲突：
| 类型 | 原因 | 解决方法 |
|---|---|---|
| 结构冲突 | 硬件资源不够，无法同时执行多条指令 | 插入“气泡”周期、增加独立指令/数据存储器 |
| 数据冲突 | 指令间存在数据相关，导致不能并行执行 | 停顿（stall）、转发（forwarding）、寄存器换名 |
| 控制冲突 | 分支指令导致下一条指令地址不确定 | 提前计算目标地址、分支预测、延迟槽 |
3.10 数据冲突详解
三种数据冲突类型：
| 类型 | 全称 | 说明 |
|---|---|---|
| RAW | Read After Write | 后一条指令读取前一条指令的写入结果（真相关） |
| WAR | Write After Read | 后一条指令写入前一条指令正在读取的寄存器（反相关） |
| WAW | Write After Write | 两条指令写入同一个寄存器（输出相关） |
解决方法：
- 转发技术（Forwarding）：将结果直接从一个段传递到需要它的段，避免等待写回；
- 停顿（Stall）：插入“气泡”周期，等待数据就绪；
- 寄存器换名：消除 WAR 和 WAW 冲突。
3.11 控制冲突处理
分支指令带来的问题：
- 下一条指令地址不确定 → PC值无法立即更新
最简单处理方法：停顿（Flush）
- ✅ 优点：实现简单
- ❌ 缺点：带来分支延迟
优化方法：
- 尽早计算出分支目标地址；
- 将分支判断提前到 ID 段完成；
- 分支预测：静态或动态预测是否跳转；
- 延迟槽（Delay Slot）：在分支后安排一条无论如何都会执行的指令。
3.12 数据冲突与控制冲突处理（续）
数据冲突解决方法总结：
| 方法类别 | 具体措施 |
|---|---|
| 插入停顿 | 插入“气泡”周期，等待数据就绪 |
| 转发技术 | 将前一条指令的结果直接转发给后一条指令，避免等待写回 |
| 寄存器换名 | 消除 WAR 和 WAW 类型的名相关冲突 |
控制冲突处理方法
最简单方法：排空流水线（Flush）
- ✅ 优点：实现简单
- ❌ 缺点：带来分支延迟
减少分支延迟的基本思路：
- 尽早计算出分支目标地址；
- 将分支判断提前到 ID 段完成；
- 通过编译器优化进一步减少分支延迟。
3.13 编译器减少分支延迟的三种方法
| 方法名称 | 说明 |
|---|---|
| 预测失败 | 假设分支不会跳转，继续顺序执行指令；若预测错误再回滚 |
| 预测成功 | 假设分支会跳转，提前从目标地址取指；若预测错误再回滚 |
| 延迟分支 | 在分支指令后插入延迟槽，编译器调度一条无论如何都会执行的指令 |
3.14 延迟槽调度策略（由编译器完成）
| 调度方式 | 说明 |
|---|---|
| 从前调度 | 从分支之前找一条无关指令放入延迟槽 |
| 从目标处调度 | 从分支目标地址处找一条指令放入延迟槽（适用于预测成功） |
| 从失败处调度 | 从分支下一条地址找一条指令放入延迟槽（适用于预测失败） |
3.15 延迟槽调度的限制条件
- 被放入延迟槽的指令必须满足以下条件：
- 不与分支指令存在数据相关或控制相关；
- 在分支成功与失败路径上都安全执行（或编译器能确保其副作用可接受）；
- 编译器具备预测分支方向的能力（静态预测或 profiling 支持）。
3.16 小结：编译器在流水线优化中的作用
| 优化目标 | 编译器策略 |
|---|---|
| 减少数据冲突 | 指令调度、寄存器换名 |
| 减少控制冲突 | 分支预测、延迟槽调度 |
| 提高流水线效率 | 静态调度、循环展开、预测导向优化 |
第四章 向量处理机
向量：是一组有序的、具有相同类型和位数的元素组成。
向量的优点：适合大量、重复、没有相互关联的（流水线处理）。
向量流水处理机：设置向量数据表示和相应的向量指令。
标量流水处理机：不具备向量数据表示和相应的向量指令。
典型的向量处理机：Cray-1，每秒 1 亿次。
向量处理机的应用领域：科学运算。
向量的处理方式
横向处理方式
-
按行的方式计算
-
特点：只适合一般处理机
-
数据相关和功能切换：n n
纵向处理方式
-
按照列的方式计算
-
特点：适用于向量处理的并行处理
-
数据相关和功能切换：1 1
纵横处理方式
-
把向量分成多组，组内纵向、组间横向
-
特点：对长度 N 无限制，但需按固定 n 个元素为一组
-
数据相关和功能切换：1 1
向量处理机的结构
结构：存储器-存储器型结构；寄存器-寄存器型结构。
存储器-存储器结构
适用范围：纵向处理方式的向量处理机。
结构特点：
-
向量指令的源向量和目的向量都存放在存储器中，运算的中间结果需要送回到存储器中。
-
运算部件的输入和输出都直接与存储器相连。
运行条件：每拍从存储器中读取两个数据，并且向存储器写回一个结果。
问题：对存储器的带宽和存储器与处理部件之间的通信带宽有很高的要求。
解决方案：采用多体交叉并行存储器和缓冲器技术。
寄存器-寄存器型结构
适用范围：分组处理的向量处理机。
结构特点：
-
能设置快速访问的向量寄存器，存放源向量、目标向量和中间结果。
-
运算部件的输入和输出都直接与寄存器相连。
CRAY-1 向量处理机
基本结构
- 功能部件
- 共 12 条单功能流水线
- 支持运算：整数加、逻辑运算、移位、浮点加、浮点乘、浮点迭代求倒数
| 单功能流水部件 | 流水线通过时间（一拍 12.5 ns） |
|----------------|-------------------------------|
| 整数加 | 3 拍 |
| 逻辑运算 | 2 拍 |
| 移位 | 4 拍 |
| 浮点加 | 6 拍 |
| 浮点乘 | 7 拍 |
| 浮点迭代求倒数 | 14 拍 |
- 向量寄存器组 V
- 512 个 64 位寄存器，分成 8 小组（每组 64 个寄存器）
- 每个小组可存放元素个数 ≤64 的向量，元素位宽 ≤64 位
- 每拍可从功能部件接收一个数据元素或返回一个结果元素
- 标量寄存器 S 和快速暂存器 T
- 标量寄存器 8 个
- T 暂存器为标量寄存器与存储器之间提供缓冲
- 向量屏蔽器 VM
- 用于向量的归并、压缩、还原、测试或单独运算
CRAY-1 的显著特点
-
每个向量寄存器都有一条连接到六个流水线单功能部件的单独总线。
-
每个向量功能部件都有把运算结果返回到向量寄存器的总线。
-
只要不发生
vi冲突和功能部件冲突，各功能部件可并行处理，提高效率。
vi 冲突和功能部件冲突
-
vi 冲突：并行工作的向量指令使用了相同
vi的源向量或结果向量。 -
功能部件冲突：并行工作的向量指令使用了相同功能部件。
CRAY-1 的四种向量指令
-
两个操作数都来自向量寄存器。
-
一个操作数来自向量寄存器，一个来自标量寄存器。
-
从主存向向量寄存器成组传送数据。
-
从向量寄存器向主存成组传送数据。
提高向量处理机性能的方法
-
采用多个功能部件
-
循环开采技术
-
链接技术
-
多处理机技术
设置多个功能部件：各部件按各自流水线工作，形成并行流水线，互不干扰。
链接技术：适用于上一步结果寄存器是下一步源寄存器且无其他冲突的情况。
第五章 指令级并行（ILP）
指令级并行：指令具有并行性，在没有结构冲突和数据冲突的情况下可并行执行；指两条及以上指令同时执行。
开发 ILP 的方法：
-
基于软件的静态开发方法
-
基于硬件的动态开发方法
增加指令并行性的方法：
-
循环级并行：不同迭代间存在并行性，最简单
-
采用向量指令和向量数据表示
相关的三种类型
-
数据相关
-
名相关
-
控制相关
流水线冲突类型
-
结构冲突
-
数据冲突
-
控制冲突
相关与冲突
相关是指令间的依赖关系，是程序属性；相关造成的冲突及停顿属于流水线属性。
解决思路：
-
保持相关：通过调度减小影响
-
消除相关：通过寄存器换名
程序顺序与正确性
-
程序顺序：完全串行，前一条执行完才能执行后一条。
-
正确性：包括数据流和异常行为。数据流指数据值从产生者到消费者指令的实际流动；无法消除的异常必须保持。
静态调度
定义：编译器在编译阶段对代码进行调度，减少相关与冲突。
特点：在编译器完成，非运行时。
方法：拉开指令距离减少停顿，如定向、延迟槽、停顿等。
动态调度
定义：在程序执行过程中，通过硬件对代码进行调度，减少数据相关造成的停顿。
优点：可解决编译时无法确定的依赖，动态调度结果可被其他流水线利用。
缺点：硬件复杂度明显提高。
方法：硬件调整指令执行顺序。
动态调度基本思想
-
最大局限：指令按序流出、按序执行。
-
冲突检测：检测结构和数据冲突；无冲突即可流出。
-
解决方案：等待数据冲突解决；无结构冲突即可执行；操作数就绪立即执行。
乱序执行与乱序完成
-
流出：无结构冲突即可流出。
-
读操作数：等待数据冲突解决后读操作数。
-
可能出现 写后读（WAR） 和 读后写（WAW） 冲突。
-
乱序完成：指令完成顺序与程序顺序不同。
动态调度流水线要求
-
多条指令可同时处于执行阶段
-
需多个功能部件或部件流水化，或二者兼有
典型动态调度算法
-
记分牌算法
-
Tomasulo 算法
记分牌动态调度算法
核心：维护三张表——指令状态表、功能部件状态表、结果寄存器状态表。
目标：无结构冲突时尽早执行无数据冲突指令，每周期执行一条。
前提：具有多个功能部件。
指令执行四阶段
-
流出：功能部件空闲且目标寄存器无冲突 → 记录信息并修改状态表（解决写后写、结构冲突）。
-
读操作数：操作数可用 → 取寄存器值并开始执行（解决写后读，可能乱序）。
-
执行：取到操作数即执行，执行完通知记分牌。
-
写结果：检查写后读冲突；存在则等待，否则写回寄存器。
Tomasulo 算法
核心：记录并检测指令相关，操作数就绪立即执行；通过寄存器换名消除 WAR、WAW 冲突。
部件：
-
保留站（保留已流出等待执行的指令）
-
公共数据总线（CDB，广播结果）
-
Load/Store 缓冲器（记录地址与数据）
-
浮点寄存器（FP）
-
指令队列（FIFO）
-
运算部件
指令执行三阶段
-
流出
-
执行
-
写结果
保留站字段
-
Busy：保留站忙 -
Op：操作类型 -
Vj, Vk：源操作数值 -
Qj, Qk：将产生源操作数的保留站号 -
A：初始存立即数/偏移，地址计算后存有效地址
寄存器状态表
记录哪个保留站将写入哪个寄存器。
Tomasulo 算法优点
-
冲突检测逻辑分布式
-
消除 WAR 和 WAW 冲突
Some information may be outdated