体系结构（三）

第3章 流水线技术

1. 流水线概述

1.1 基本概念

流水线技术具有以下特点：

1. 流水过程由多个相联系的子过程组成，每个过程称为流水线的“级”或“段”。一条流水线的段数，也称为流水线的“深度”或“流水深度”。
2. 每个子过程由专用的功能段实现。
3. 每个功能段所需的时间应尽量相等，否则，时间长的功能段将成为流水线的瓶颈，会造成“堵塞”和“断流”，这个时间一般为一个时钟周期（拍）或机器周期。
4. 流水线需要有“通过时间”（第一个任务流出所需要的时间），在此之后流水过程才进入稳定状态，每一个时钟周期（拍）流出一个结果。
5. 流水线技术适合大量重复的时序过程，只有在输入端能连续地提供任务，流水线的效率才能充分发挥。

1.2 分类

1.单功能流水线和多功能流水线

单功能流水线（Unifunction Piplines）：

只能完成一种固定功能的流水线。

多功能流水线（Multifunction Piplines）：

流水线各段可以进行不同的连接，从而使流水线在不同的时间，或在同一时间完成不同的功能。

2.静态流水线和动态流水线

静态流水线（Static Pipelines）：

在同一时间内，流水线的各段只能按同一种功能的连接方式工作。

动态流水线（Dynamic Pipelines）：

同一时间内，当某些段正在实现某种运算（如定点乘）时，另一些段却在实现另一种运算（如浮点加）。

3.部件级、处理机级及处理机间流水线

部件级流水线，又称运算操作流水线（Arithmetic Pipelines）：

把处理机的算术逻辑部件分段，以便为各种数据类型进行流水操作。

处理机级流水，又叫指令流水线（Instruction Pipelines）：

把解释指令的过程按照流水的方式处理。

处理机间流水线，又叫宏流水线（Macro Pipelines）：

由两个以上的处理机串行的对同一数据流进行处理，每个处理机完成一项任务。

4.标量流水处理机和向量流水处理机

标量流水处理机（Scalar Pipelining Processor）：

处理机仅对标量数据进行流水处理。

向量流水处理机（Vector Pipelining Processor）：

处理机具有向量数据表示，并通过向量指令对向量的各元素进行处理。

5.线性流水线和非线性流水线

线性流水线（Linear Pipelines）：

流水线的各段串行连接，没有反馈回路。

非线性流水线（Nonlinear Pipelines）：

流水线中除有串行连接的通路外，还有反馈回路。

2. MIPS的基本流水线

2.1 MIPS的一种简单实现

1.取指周期

$IR\leftarrow Mem[PC]$

$NPC \leftarrow PC+4$

2.指令译码/读寄存器周期

$A \leftarrow Reg[IR_{6..10}]$

$B \leftarrow Reg[IR_{11..15}]$

$Imm \leftarrow ((IR_{16})^{16}\#\#IR_{16..31})$ // 符号扩展

3.执行/有效地址计算周期

（1）存储器访问

求有效地址

$ALUOutput \leftarrow A + Imm$

（2）寄存器-寄存器 ALU 操作

求运算结果

$ALUOutput \leftarrow A \space op \space B$

（3）寄存器-立即数 ALU 操作

求运算结果

$ALUOutput \leftarrow A \space op \space Imm$

（4）分支操作

获得分支目标地址

$ALUOutput \leftarrow NPC + Imm$

$Cond \leftarrow (A \space op \space 0)$ // 判断是否分支跳转

4.存储器访问/分支完成周期

（1）存储器访问操作

$LMD \leftarrow Mem[ALUOutput]$ // lw

$Mem[ALUOutput] \leftarrow B$ // sw

（2）分支操作

$if (Cond) \space PC \leftarrow ALUOutput \space else \space PC \leftarrow NPC$

5.写回周期

（1）寄存器-寄存器型 ALU 指令

$Regs[IR_{16..20}] \leftarrow ALUOutput$ // rd

（2）寄存器-立即数 ALU 指令

$Regs[IR_{11..15}] \leftarrow ALUOutput$ // rt

（3）Load 指令

$Regs[IR_{11..15}] \leftarrow LMD$

2.2 基本的MIPS流水线

2.3 流水线性能分析

1.吞吐率

吞吐率（Throughput Rate）：单位时间内流水线所完成的任务数或输出结果的数量。

（1）最大吞吐率 $TP_{max}$

$TP_{max} = \frac{1}{max\{\Delta t_i\}}$

（2）实际吞吐率

完成 n 个任务所需要的时间

$T_{流水} = m\Delta t_0 + (n - 1) \Delta t_0$

$TP = \frac{n}{T_{流水}} = \frac{n}{m\Delta t_0 + (n-1)\Delta t_0} = \frac{1}{(1+\frac{m-1}{n})\Delta t_0} = \frac{TP_{max}}{1+\frac{m-1}{n}}$

如果各段时间不相等，完成 n 个任务的实际吞吐率为

$TP = \frac{n}{\sum_{i=1}^m\Delta t_i + (n-1)\Delta t_j}$

$\Delta t_j$ 是最慢一段所需要的时间

2.加速比

流水线的加速比（Speedup Ratio）： 指 m 段流水线的速度与等功能的非流水线的速度之比。

等效的非流水线上所需的时间为 $T_0 = nm\Delta t_0$

加速度比为

$S=\frac{T_0}{T_{max}}=\frac{nm\Delta t_0}{m\Delta t_0+(n-1)\Delta t_0} = \frac{nm}{m+n-1}=\frac{m}{1+\frac{m-1}{n}}$

如果各段时间不相等

$S=\frac{n\sum_{i=1}^m\Delta t_i}{\sum_{i=1}^m{\Delta t_i}+(n-1)\Delta t_j}$

3.效率

效率（efficiency）： 指流水线的设备利用率。

由于流水线有通过时间（第一个任务输入后到其完成所有的时间）和排空时间（最后一个任务输入后到完成的时间），所以，在连续完成 n 个任务的时间内，每段都不是在满负荷地工作。

• 当各段流水线的时间相等，则整个流水线的效率等同于一条流水线的效率

$E = \frac{e_1+e_2+...+e_m}{m} = \frac{me_0}{m} = \frac{mn\Delta t_0}{mT_{流水}}$

从时空图上来看，效率就是 n 个任务占用的时空区和 m 个段占用的时空区之比，即效率含有时间和空间两个方面的因素

$E = \frac{n\Delta t_0}{T_{流水}}= \frac{n}{m+(n-1)} = \frac{1}{1+\frac{m-1}{n}}$

效率是实际加速比（S）和最大加速比（m）之比

$E = \frac{S}{m}$

如果流水线各段时间不等，此时各段的效率不等

$E = \frac{n 个任务占用的时空区}{m 个段总的时空区} = \frac{n\sum_{i=1}^m\Delta t_i}{m(\sum_{i=1}^m\Delta t_i + (n-1)\Delta t_j)}$

3. 流水线中的相关

一般来说，流水线中的相关主要分为以下三类

（1）结构相关： 当指令在同步重叠执行过程中，硬件资源满足不了指令重叠执行的要求，发生资源冲突时将产生“结构相关”。

（2）数据相关： 当一条指令需要用到前面指令的执行结果，而这些指令均在流水线中重叠执行时，就可能引起“数据相关”。

（3）控制相关： 当流水线遇到分支指令和其他能够改变 PC 值的指令时就会发生“控制相关”。

3.1 结构相关

许多流水线机器都是将数据和指令保存在同一存储器中。如果某个时钟周期内，流水线既要完成对数据存储器的访问，又要完成取指操作，将发生存储器访问冲突。

解决方法通常有：

1. 插入气泡： 在流水线中插入一个暂停周期
2. 流水化功能单元： 如果完全流水化带来的硬件开销将很大
3. 资源重复： 在流水线机器中设置相互独立的指令存储器和数据存储器，也可将 Cache 分割成指令 Cache 和数据 Cache

3.2 数据相关

3.2.1 通过定向技术减少数据相关带来的暂停

定向，也称为旁路或短路：

（1）EX/MEM 段间寄存器中的 ALU 运算结果总是回送到 ALU 的输入寄存器

（2）当定向硬件检测到前一个 ALU 运算结果的写入寄存器就是当前 ALU 操作的源寄存器，那么控制逻辑将前一个 ALU 运算结果定向到 ALU 的输入端，后一个 ALU 操作就不必从源寄存器中读取操作数。

（3）MIPS 的零检测单元在 EX 周期完成分支条件检测操作，也需要设置到该单元的定向路径。

MIPS 流水线还有一种简单技术可以解决一定的读写冲突：在MIPS流水线中，约定在时钟周期的后半部分进行寄存器文件的读写操作，而在时钟周期的前半部分进行寄存器文件的写操作。

3.2.2 数据相关的分类

考虑流水线中的两条指令 i 和 j ，且 i 在 j 之前进入流水线，由此带来的数据相关可能有：

1. 写后读相关（Read After Write, RAW）

正确： i 先写数据，j 再读取 i 写入的数据

错误： j 在 i 写入数据之前将读出了错误的数据

2. 写后写相关（Write After Write, WAW）

正确： i 先写数据，j 再写入数据，此时寄存器中最终保存的应该是 j 写入的数据

错误： j 在 i 写入数据之前写入了数据，寄存器中最终保留的是操作 i 写入的数据

示例： 假设访问存储器占两个拍

3. 读后写相关（Write After Read, WAR）

正确： i 先读出数据，j 再写入数据

错误： j 在 i 读出数据之前向 i 要读的寄存器写入了数据，导致 i 读出了错误的数据

示例：

4. 读后读相关（Read After Read, RAR）

该情况下不存在数据相关。

3.2.3 需要暂停的数据相关

并不是所有的数据相关带来的暂停都可以通过定向技术消除，如下指令序列

为保证流水线正确执行上述指令序列，可以设置一个称为**“流水线锁”（Pipeline Interlock）**的功能部件。一旦流水线锁检测到上述数据相关，流水线暂停执行 LW 指令之后的所有指令，直到能够通过定向解决该数据相关为之。

流水线锁在流水线中插入了暂停和气泡，指令的执行时间增加了一个时钟周期。暂停的时钟周期数称为“载入延迟”。

3.2.4 对数据相关的编译器调度方法

通过编译器重新组织代码顺序消除暂停的技术为**“流水线调度”（Pipeline Scheduling）或“指令调度”（Instruction Scheduling）**。

3.2.5 对 MIPS 流水线控制的实现

指令发射（Instruction Issue）： 让一条指令从流水线的指令译码段（ID）移动到执行段（EX）的过程。

已发射的指令： 经过了上述过程的指令。

对 MIPS 流水线而言，所有的数据相关均可在流水线的 ID 段检测到。

当硬件检测到一个相关：

• 只需要将 ID/EX 流水线寄存器组中的控制寄存器改为全 0 即可，全 0 表示不进行任何操作。
• 另外还必须暂停向前传送 IF/ID 寄存器组的内容，是流水线能够保持被暂停的指令。

所有定向都是从 ALU 或数据存储器的输出到 ALU、数据存储器或 0 检测单元的输入定向，可以分别将 EX/MEM 和 MEM/WB 段的寄存器 IR 同 ID/EX 和 EX/MEM 段中的寄存器 IR 相比较，决定是否需要定向，从而实现必须的定向控制。

3.3 控制相关

MIPS 流水线上执行分支指令时，PC 值有两种可能的变化情况：

1. 一种是 PC 值发生改变（为分支转移的目标地址）
2. PC 值保持正常（等于当前值加 4）

如果分支转移条件成立，PC 变为分支转移的目标地址，称为分支转移“成功”。否则分支转移“失败”。

在暂停周期中，可以同过设置 IF/ID 寄存器文件的 IR 域为 0 （noop操作）来实现暂停。

减少流水线处理分支指令时的暂停时钟周期数有以下两种途径：

1. 在流水线中尽早判断出分支转移是否成功。

   在 MIPS 流水线中，分支指令（BEQZ 和 BNEZ）需要测试分支条件寄存器的值是否为 0 ，所以，可以把测试分支条件寄存器的操作移到 ID 段完成，从而在 ID 周期末就完成分支转移成功与否的检测。

2. 尽早计算出分支转移成功时的 PC 值（即分支的目标地址）。

   将计算分支目标地址的操作移到 ID 段完成。

为优化处理分支指令，在流水线中应该同时采用上述两条途径，缺一不可。

3.3.1 降低流水线损失的方法

从编译技术的角度来说，以下方法对分支转移成功与否进行的预测都是 静态的 ，并在整个程序的执行过程中保持这种预测结论，即要么认为分支转移成功，要么失败。

1. “冻结”或“排空”流水线

   在流水线中停住或删除分支后的指令，直到知道转移目标地址。

   优点：简单

2. 预测分支失败

   流水线继续照常流动，如果分支转移成功，将分支指令后的指令转换为空操作，并从分支目标处开始取指令执行；否则照常执行。

3. 预测分支成功

   始终假设分支成功，直接从分支目标处取指令执行。

   对MIPS流水线没有任何好处！由于 MIPS 流水线中，修改后也只有在 ID 段才能知道分支目标地址，无法直接执行分支目标处的指令。

4. 延迟分支

   分支开销为n的分支指令后紧跟有n个延迟槽，流水线遇到分支指令时，按正常方式处理，顺带执行延迟槽中的指令，从而减少分支开销。

   

   调度分支延迟指令的三种常用方法：

   

   为了提高编译器填充分支延迟槽的能力，许多流水线机器引入了“取消”或“作废”分支。对取消的分支而言，分支指令包括了预测的分支方向，当实际分支方向和事先所预测的一样，执行分支延迟槽中的指令，流水线正常工作。反之，就将延迟槽中的指令转化成一个空操作。

   

3.3.2 各种处理分支方法的性能

假设理想 CPI 为 1 ，则加速比为

$S=\frac{D}{1+C}=\frac{D}{1+f*P_{分支}}$

$D$ 为流水线深度。

$C$ 为由于处理分支指令而给程序中每条指令带来的平均暂停的时钟周期数。

$f$ 为程序中分支指令的出现频率。

$P_{分支}$ 为分支开销。

4. 计算机实例分析（MIPS R4000）

5. 向量处理机（Vector Processor）

具有向量数据表示和相应向量指令的流水线处理机称为向量流水线处理机，也称向量处理机。
与之对应的是标量处理机，不支持向量数据表示，没有提供向量指令。

循环的每个迭代(iteration)中有1次数据相关，1次控制相关，需要2次功能切换。

5.1 水平横向处理方式

5.2 垂直（纵向）处理方式

没有分支；仅有1次数据相关；仅需要1次功能切换。

5.3 分组（纵横）处理方式

这种技术称为 向量循环 或 分段开采 。

需要m次迭代；每次迭代执行两条向量指令，有1次数据相关，需要2次功能切换。

5.4 向量处理机的速度评价方法

1. 由于一条指令最多得到一个结果，标量处理机通常用每秒执行多少条指令(MIPS)来衡量机器的运算速度。

   向量处理机用每秒取得多少浮点运算结果来衡量机器速度，以 MFLOPS 作为测量单位。

   采用 MFLOPS 可以忽视 Load、Store、分支、测试等类型指令的影响。

   一般认为，在标量计算机中执行一次浮点运算，平均需3条指令。因此，如果要把这两种速度指标放在一起比较，就应该把MFLOPS乘以一个系数，以得到相应的MIPS。

2. 比较法：选择一台速度指标得到公认的机器作为标准机，给定一些典型的基准程序，分别在标准机和被测机上求解。

5.5 向量处理机实例：Cray-I

向量处理机存在的冒险：

• 功能部件冒险： 同一功能部件被一条以上的并行工作向量指令所使用。
• **Vi冒险： **并行工作的各向量指令具有相同的源向量或结果向量。

CRAY-I体系结构特点：

• 向量寄存器与功能单元的连接通路

  每个Vi块都有单独总线可连到6个向量功能部件，而每个向量功能部件也各自都有把运算结果送回向量寄存器组的总线。

• 向量链接技术

  一个向量功能部件得到的结果 直接送入 另一个向量功能部件的 操作数寄存器 时所发生的连接过程称为 链接（Chaining） 。

  

  当两条指令出现“先写后读（RAW）”相关时，若它们不存在功能部件冒险和向量寄存器(源或目的) 冒险，就有可能把它们所用的功能部件头尾相接，形成一个链接流水线，进行 流水处理 。
  链接 特性实质上是把流水线“定向”的思想引入到向量执行过程的结果。

  

• 向量链接技术应考虑的问题：

  • 设定合适的向量功能部件和操作数寄存器
  • 链接时机问题
    • 只有在前一条向量指令的第一个结果元素送入结果向量寄存器的那一个时钟周期才可以进行链接
    • 当一条向量指令的两个源操作数分别是两条先行指令的结果寄存器时，要求先行的两条指令产生运算结果的时间必须相等，即要求有关功能部件的通过时间相等。
    • 所有可以链接执行的向量指令的向量长度应相等

6. 题目