# 流水线技术

## 流水线的基本概念

流水线技术是指把一个重复的过程分解为若干个子过程，每个子过程由专门的功能部件来实现。把多个处理过程在时间上错开，依次通过各功能段，这样，每个子过程就可以与其它的子过程并行进行。

### 什么是流水线

指令基本执行过程

* 取指令 因为指令首先存放在存储器中，只有读存储器才知道指令要计算机干什么。
* 分析指令 控制器取到了指令就要分析指令的要求。
* 取数据 数据还在存储器，还要将数据读到运算器，才能完成计算任务。
* 执行指令 最后由运算器完成计算，并将结果存入存储器。
* （存数据）

可以把指令执行分解为5个时钟周期

* 取指令周期（IF）
* 指令译码/读寄存器周期（ID） 指令译码和读寄存器是并行进行的。之所以能做到这一点，是因为在DLX指令格式中，操作码在固定位置。这种技术也称为固定字段译码。
* 执行/有效地址计算周期（EX）
* 存储器访问/分支完成周期（MEM）
* 写回周期（WB）

流水线技术

* 把一个重复的过程分解为若干个子过程，每个子过程由专门的功能部件来实现。
* 把多个处理过程在时间上错开，依次通过各功能段，这样，每个子过程就可以与其它的子过程并行进行。

流水线中的每个子过程及其功能部件称为流水线的**级**或**段**，段与段相互连接形成流水线。流水线的段数称为流水线的**深度**。

指令流水线

* 把指令的解释过程分解为分析和执行两个子过程，并让这两个子过程分别用独立的分析部件和执行部件来实现。 理想情况：速度提高一倍
* 4段指令流水线 ![流水线技术1](http://ofolh8dcq.bkt.clouddn.com/%E6%B5%81%E6%B0%B4%E7%BA%BF%E6%8A%80%E6%9C%AF1.PNG)

浮点加法流水线

* 把流水线技术应用于运算的执行过程，就形成了**运算操作流水线**，也称为**部件级流水线**。
* 把浮点加法的全过程分解为求阶差、对阶、尾数相加、规格化四个子过程。 理想情况：速度提高3倍

时－空图

* 时－空图从时间和空间两个方面描述了流水线的工作过程。时－空图中，横坐标代表时间，纵坐标代表流水线的各个段。
* 例如浮点加法流水线的时空图 ![流水线技术2](http://ofolh8dcq.bkt.clouddn.com/%E6%B5%81%E6%B0%B4%E7%BA%BF%E6%8A%80%E6%9C%AF2.PNG)

流水技术的特点

* 流水线把一个处理过程分解为若干个子过程（段），每个子过程由一个专门的功能部件来实现。
* 流水线中各段的时间应尽可能相等，否则将引起流水线堵塞、断流。 时间最长的段将成为流水线的瓶颈。
* 流水线每一个段的后面都要有一个缓冲寄存器（锁存器），称为流水寄存器。 作用：在相邻的两段之间传送数据，以保证提供后面要用到的信息，并把各段的处理工作相互隔离。
* 流水技术适合于大量重复的时序过程，只有在输入端不断地提供任务，才能充分发挥流水线的效率。
* 流水线需要有通过时间和排空时间。 通过时间：第一个任务从进入流水线到流出结果所需的时间。 排空时间：最后一个任务从进入流水线到流出结果所需的时间。

### 流水线的分类

部件级、处理机级及系统级流水线（按照流水技术用于计算机系统的等级不同）

* 部件级流水线（运算操作流水线）：把处理机中的部件分段，再把这些分段相互连接起来，使得各种类型的运算操作能够按流水方式进行。
* 处理机级流水线（指令流水线）：把指令的执行过程按照流水方式处理。把一条指令的执行过程分解为若干个子过程，每个子过程在独立的功能部件中执行。
* 系统级流水线（宏流水线）：把多台处理机串行连接起来，对同一数据流进行处理，每个处理机完成整个任务中的一部分。

单功能流水线与多功能流水线（按照流水线所完成的功能来分类）

* 单功能流水线：只能完成一种固定功能的流水线。
* 多功能流水线：流水线的各段可以进行不同的连接，以实现不同的功能。

静态流水线与动态流水线（按照同一时间内各段之间的连接方式对多功能流水线作进一步的分类）

* 静态流水线：在同一时间内，多功能流水线中的各段只能按同一种功能的连接方式工作。
  * 对于静态流水线来说，只有当输入的是一串相同的运算任务时，流水的效率才能得到充分的发挥。
* 动态流水线：在同一时间内，多功能流水线中的各段可以按照不同的方式连接，同时执行多种功能。
  * 优点：灵活，能够提高流水线各段的使用率，从而提高处理速度。
  * 缺点：控制复杂。
* 静、动态流水线时空图的对比 ![流水线技术3](http://ofolh8dcq.bkt.clouddn.com/%E6%B5%81%E6%B0%B4%E7%BA%BF%E6%8A%80%E6%9C%AF3.PNG)

线性流水线与非线性流水线（按照流水线中是否有反馈回路来进行分类）

* 线性流水线：流水线的各段串行连接，没有反馈回路。数据通过流水线中的各段时，每一个段最多只流过一次。
* 非线性流水线：流水线中除了有串行的连接外，还有反馈回路。
* 非线性流水线的调度问题 确定什么时候向流水线引进新的任务，才能使该任务不会与先前进入流水线的任务发生冲突——争用流水段。

顺序流水线与乱序流水线（根据任务流入和流出的顺序是否相同来进行分类）

* 顺序流水线：流水线输出端任务流出的顺序与输入端任务流入的顺序完全相同。每一个任务在流水线的各段中是一个跟着一个顺序流动的。
* 乱序流水线：流水线输出端任务流出的顺序与输入端任务流入的顺序可以不同，允许后进入流水线的任务先完成（从输出端流出）。 也称为无序流水线、错序流水线、异步流水线

标量处理机与向量流水处理机

* 把指令执行部件中采用了流水线的处理机称为流水线处理机。
* 标量处理机：处理机不具有向量数据表示和向量指令，仅对标量数据进行流水处理。
* 向量流水处理机：具有向量数据表示和向量指令的处理机。 向量数据表示和流水技术的结合。

## 流水线的性能指标

### 流水线的吞吐率

吞吐率：在单位时间内流水线所完成的任务数量或输出结果的数量。 $$TP=\frac n{T\_k}$$ 其中n为任务数，$T\_k$是处理完成n个任务所用的时间。

1. 各段时间均相等的流水线

* 各段时间均相等的流水线时空图 ![流水线技术4](http://ofolh8dcq.bkt.clouddn.com/%E6%B5%81%E6%B0%B4%E7%BA%BF%E6%8A%80%E6%9C%AF4.PNG)
* 流水线完成n个连续任务所需要的总时间为：（假设一条k段线性流水线） $$T\_k=k\Delta t+(n-1)\Delta t=(k+n-1)\Delta t$$
* 流水线的实际吞吐率： $$TP=\frac n{(k+n-1)\Delta t}$$
* 最大吞吐率： $$TP\_{max}=\lim\_{n\to \infty}\frac n{(k+n-1)\Delta t}=\frac 1{\Delta t}$$
* 最大吞吐率和实际吞吐率的关系： $$TP=\frac n{k+n-1}TP\_{max}$$ 可以看出，流水线的实际吞吐率总是小于最大吞吐率。只有当n>>k时，才有$TP\approx TP\_{max}$。

1. 各时间段不完全相等的流水线

* 各段时间不等的流水线及其时空图 ![流水线技术5](http://ofolh8dcq.bkt.clouddn.com/%E6%B5%81%E6%B0%B4%E7%BA%BF%E6%8A%80%E6%9C%AF5.PNG)
* 各段时间不等的流水线的实际吞吐率为： $$TP=\frac n{\sum\_{i=1}^k \Delta t\_i+(n-1)max(\Delta t\_1,\Delta t\_2,\cdots,\Delta t\_k)}$$
* 流水线的最大吞吐率为： $$TP\_{max}=\frac 1{max(\Delta t\_1,\Delta t\_2,\cdots,\Delta t\_k)}$$

1. 解决流水线瓶颈问题的常用方法

* 细分瓶颈段 例如：对前面的5段流水线把瓶颈段S4细分为3个子流水线段：S4-1，S4-2，S4-3 ![流水线技术6](http://ofolh8dcq.bkt.clouddn.com/%E6%B5%81%E6%B0%B4%E7%BA%BF%E6%8A%80%E6%9C%AF6.PNG) 改进后的流水线吞吐率：$TP\_{max}=\frac 1{\Delta t}$。
* 重复设置瓶颈段 缺点：控制逻辑比较复杂，所需的硬件增加了。

### 流水线设计中的若干问题

1. 瓶颈问题

* 理想情况下，流水线在工作时，其中的任务是同步地每一个时钟周期往前流动一段。
* 当流水线各段不均匀时，机器的时钟周期取决于瓶颈段的延迟时间。
* 在设计流水线时，要尽可能使各段时间相等。

1. 流水线的额外开销（流水寄存器延迟、时钟偏移开销）

* 流水寄存器需要建立时间和传输延迟 建立时间：在触发写操作的时钟信号到达之前，寄存器输入必须保持稳定的时间。 传输延迟：时钟信号到达后到寄存器输出可用的时间。
* 时钟偏移开销 流水线中，时钟到达各流水寄存器的最大差值时间。（时钟到达各流水寄存器的时间不是完全相同）
* 几个问题
  * 流水线并不能减少（而且一般是增加）单条指令的执行时间，但却能提高吞吐率。
  * 增加流水线的深度（段数）可以提高流水线的性能。
  * 流水线的深度受限于流水线的额外开销。
  * 当时钟周期小到与额外开销相同时，流水已没意义。因为这时在每一个时钟周期中已没有时间来做有用的工作。

1. 冲突问题 流水线设计中要解决的重要问题之一。

## 流水线的相关和冲突

### 相关

* 相关：两条指令之间存在某种依赖关系。 如果两条指令相关，则它们就有可能不能在流水线中重叠执行或者只能部分重叠执行。
* 相关有3种类型
  * 数据相关（也称真数据相关）
  * 名相关
  * 控制相关

1. 数据相关

* 对于两条指令i（在前，下同）和j（在后，下同），如果下述条件之一成立，则称指令j与指令i数据相关。
  * 指令j使用指令i产生的结果；
  * 指令j与指令k数据相关，而指令k又与指令i数据相关。
* 数据相关具有传递性。 数据相关反映了数据的流动关系，即如何从其产生者流动到其消费者。
* 当数据的流动是经过寄存器时，相关的检测比较直观和容易。
* 当数据的流动是经过存储器时，检测比较复杂。
  * 相同形式的地址其有效地址未必相同；
  * 形式不同的地址其有效地址却可能相同。

1. 名相关

* 名：指令所访问的寄存器或存储器单元的名称。
* 如果两条指令使用相同的名，但是它们之间并没有数据流动，则称这两条指令存在名相关。
* 指令j与指令i之间的名相关有两种：
  * 反相关：如果指令j写的名与指令i读的名相同，则称指令i和j发生了反相关。 指令j写的名＝指令i读的名
  * 输出相关：如果指令j和指令i写相同的名，则称指令i和j发生了输出相关。 指令j写的名＝指令i写的名
* 名相关的两条指令之间并没有数据的传送。
* 如果一条指令中的名改变了，并不影响另外一条指令的执行。
* 换名技术
  * 换名技术：通过改变指令中操作数的名来消除名相关。
  * 对于寄存器操作数进行换名称为寄存器换名。 既可以用编译器静态实现，也可以用硬件动态完成。

1. 控制相关

* 控制相关是指由分支指令引起的相关。 为了保证程序应有的执行顺序，必须严格按控制相关确定的顺序执行。
* 典型的程序结构是“if-then”结构。
* 控制相关带来了以下两个限制：
  * 与一条分支指令控制相关的指令不能被移到该分支之前。否则这些指令就不受该分支控制了。
  * 如果一条指令与某分支指令不存在控制相关，就不能把该指令移到该分支之后。

### 流水线冲突

流水线冲突是指对于具体的流水线来说，由于相关的存在，使得指令流中的下一条指令不能在指定的时钟周期执行。

流水线冲突有3种类型：

* 结构冲突：因硬件资源满足不了指令重叠执行的要求而发生的冲突。
* 数据冲突：当指令在流水线中重叠执行时，因需要用到前面指令的执行结果而发生的冲突。
* 控制冲突：流水线遇到分支指令和其它会改变PC值的指令所引起的冲突。

带来的几个问题：

* 导致错误的执行结果。
* 流水线可能会出现停顿，从而降低流水线的效率和实际的加速比。
* 我们约定：当一条指令被暂停时，在该暂停指令之后流出的所有指令都要被暂停，而在该暂停指令之前流出的指令则继续进行（否则就永远无法消除冲突）。

1. 结构冲突

* 在流水线处理机中，为了能够使各种组合的指令都能顺利地重叠执行，需要对功能部件进行流水或重复设置资源。
* 如果某种指令组合因为资源冲突而不能正常执行，则称该处理机有结构冲突。
* 常见的导致结构冲突的原因：
  * 功能部件不是完全流水
  * 资源份数不够
* 结构冲突举例：访存冲突 有些流水线处理机只有一个存储器，将数据和指令放在一起，访存指令会导致访存冲突。
  * 解决办法1：插入暂停周期（“流水线气泡”或“气泡”）引入暂停后的时空图
  * 解决办法2：设置相互独立的指令存储器和数据存储器或设置相互独立的指令Cache和数据Cache。
* 有时流水线设计者允许结构冲突的存在 主要原因：减少硬件成本 如果把流水线中的所有功能单元完全流水化，或者重复设置足够份数，那么所花费的成本将相当高。

1. 数据冲突 当相关的指令靠得足够近时，它们在流水线中的重叠执行或者重新排序会改变指令读/写操作数的顺序，使之不同于它们串行执行时的顺序，则发生了数据冲突。

* 根据指令读访问和写访问的顺序，可以将数据冲突分为3种类型。
  * 写后读冲突（RAW） 在i写入之前，j先去读。j读出的内容是错误的。这是最常见的一种数据冲突，它对应于真数据相关。
  * 写后写冲突（WAW） 在 i 写入之前，j 先写。最后写入的结果是 i 的。错误！这种冲突对应于输出相关。 写后写冲突仅发生在这样的流水线中：流水线中不只一个段可以进行写操作；指令被重新排序了。
  * 读后写冲突（WAR） 在 i 读之前，j 先写。i 读出的内容是错误的！由反相关引起。 这种冲突仅发生在这样的情况下：有些指令的写结果操作提前了，而且有些指令的读操作滞后了；指令被重新排序了。
* 通过定向技术减少数据冲突引起的停顿 （定向技术也称为旁路或短路）
  * 关键思想：在计算结果尚未出来之前，后面等待使用该结果的指令并不真正立即需要该计算结果，如果能够将该计算结果从其产生的地方直接送到其它指令需要它的地方，那么就可以避免停顿。
  * 定向的实现 EX段和MEM段之间的流水寄存器中保存的ALU运算结果总是回送到ALU的入口。 当定向硬件检测到前一个ALU运算结果写入的寄存器就是当前ALU操作的源寄存器时，那么控制逻辑就选择定向的数据作为ALU的输入，而不采用从通用寄存器组读出的数据。
  * 结果数据不仅可以从某一功能部件的输出定向到其自身的输入，而且还可以定向到其它功能部件的输入。
* 需要停顿的数据冲突
  * 并不是所有的数据冲突都可以用定向技术来解决。
  * 增加流水线互锁机制，插入“暂停”。 作用：检测发现数据冲突，并使流水线停顿，直至冲突消失。
* 依靠编译器解决数据冲突\
  让编译器重新组织指令顺序来消除冲突，这种技术称为指令调度或流水线调度。

1. 控制冲突

* 执行分支指令的结果有两种
  * 分支成功：PC值改变为分支转移的目标地址。 在条件判定和转移地址计算都完成后，才改变PC值。
  * 不成功或者失败：PC的值保持正常递增，指向顺序的下一条指令。
* 处理分支指令最简单的方法：“冻结”或者“排空”流水线
* 把由分支指令引起的延迟称为分支延迟。
* 分支指令在目标代码中出现的频度 每3～4条指令就有一条是分支指令。
* 可采取两种措施来减少分支延迟。
  * 在流水线中尽早判断出分支转移是否成功；
  * 尽早计算出分支目标地址。
* 3种通过软件（编译器）来减少分支延迟的方法 共同点：对分支的处理方法在程序的执行过程中始终是不变的，是静态的。要么总是预测分支成功，要么总是预测分支失败。
  * 预测分支失败 允许分支指令后的指令继续在流水线中流动，就好象什么都没发生似的； 若确定分支失败，将分支指令看作是一条普通指令，流水线正常流动； 若确定分支成功，流水线就把在分支指令之后取出的所有指令转化为空操作，并按分支目地重新取指令执行。
  * 预测分支成功 假设分支转移成功，并从分支目标地址处取指令执行。 起作用的前题：先知道分支目标地址，后知道分支是否成功。
  * 延迟分支 主要思想：从逻辑上“延长”分支指令的执行时间。把延迟分支看成是由原来的分支指令和若干个延迟槽构成，不管分支是否成功，都要按顺序执行延迟槽中的指令。

> 《计算机系统结构教程（第2版）》张晨曦 王志英 等 著