流水线

流水线的定义：将一重复的处理过程分解为若干子过程，每一个子过程都可有效地在其专用功能段上与其他子过程同时执行，这种技术成为流水线技术。

一、流水线的特点

• 流水过程由多个相关的子过程组成，这些子过程称为流水线的“级”或“段”。段的数目称为流水线的“深度”。
• 每个子过程由专用的功能段实现，各功能段的时间应基本相等，通常为1个时钟周期。
• 流水线需要经过一定的通过时间(CD时间)才能稳定。
• 流水技术适合于大量重复的时序过程，且是并行处理。
• 它不能缩短单个任务的响应时间，但是可以提高吞吐率。

二、流水线类型

1. 按流水线所完成的功能分类

• 单功能流水线：只能完成一种固定功能
• 多功能流水线：各段可以进行不同的连接，有很多的类型，但是选取其中的几个，可以完成不同的功能

2. 按同一时间内流水线的连接方式划分

• 静态流水线：同一时间内，流水线各段只能完成某一种功能
• 动态流水线：同一时间内，流水线各段可以完成不同的功能，比如又做加减、又做乘除

PS：动态流水线使得流水线的控制变得很复杂。

3. 按照流水的级别划分

• 部件级流水线：处理机的算术逻辑部件分段
• 处理机级流水线：解释指令的过程分段，比如分为取指、计算、存放
• 处理机间流水线：不同的处理机对同一数据进行处理

PS：部件级与处理机级比较常见，而处理机间流水线更常用于OS。

4. 按照是否有反馈回路来进行分类

• 线性流水线：各段串行连接，无反馈回路
• 非线性流水线：有反馈回路

流水线调度：什么时候向流水线引入新的输入，从而使新输入的数据和先前操作的反馈数据在流水线中不产生冲突。

5. 按照输出端任务流出顺序与输入端任务流入顺序是否相同划分

• 顺序流动流水线：顺序流入，顺序流出
• 乱序流动流水线：顺序流入、乱序流出

三、流水线的性能分析

主要是三项性能指标：吞吐率、加速比、效率

(1)吞吐率

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

a.最大吞吐率

最大吞吐率$TP_{max}$：流水线到达稳定状态后的吞吐率

1. 流水线各段时间相等，均为$\Delta t_0$：
   $$
   TP_{max}=\frac{1}{\Delta t_0}
   $$

2. 流水线各段时间不等，第$i$段时间为$\Delta t_i$($TP_{max}$取决于流水线中最慢一段所需时间，即瓶颈)：
   $$
   TP_{max}=\frac{1}{max{\Delta t_i}}
   $$

消除瓶颈的方法：

• 细分瓶颈段
• 重复设置瓶颈段

b.实际吞吐率

实际吞吐率$TP$：$m$段流水线完成$n$个任务的吞吐率。

1. 若各段时间相等，均为$\Delta t_0$：
   $$
   T_{流水}=m\Delta t_0+(n-1)\Delta t_0\
   TP=\frac{n}{T_{流水}}=\frac{TP_{max}}{1+\frac{m-1}{n}}
   \n>>m:TP>>TP_{max}
   $$

2. 若各段时间不等，第$i$段时间为$\Delta t_i$：
   $$
   T=\sum^m_{i=1}\Delta t_i+(n-1)\Delta t_j,\Delta t_j=max{\Delta t_i}\
   TP=\frac {n}{T}
   $$

(2)加速比

加速比$S$指的是流水线速度与等功能的非流水线速度之比。

1. 各段时间相等：
   $$
   S=\frac {T_{非流水}}{T_{流水}}=\frac{nm\Delta t_0}{m\Delta t_0+(n-1)\Delta t_0}=\frac{m}{1+\frac{m-1}{n}}
   $$

2. 各段时间不等：
   $$
   S=\frac{n\sum^m_{i=1}\Delta t_i}{\sum^m_{i=1}\Delta t_i+(n-1)\Delta t_{max}}
   $$

(3)效率

效率指流水线的设备利用率。

流水线并不是一直满负荷工作，刚开始有通过时间(CD)，结束时有排空时间。

1. 各段时间相等：
   $$
   E=\frac{n}{m+n-1}
   $$

2. 各段时间不等：
   $$
   E=\frac{n个任务占用的时空区}{m个段总的时间区}
   $$

(4)相关关系

1. 效率是实际加速比$S$与$m$($m$段流水线)之比。
   $$
   E=\frac{m n\Delta t_0}{mT_{流水}}=\frac{S}{m}
   $$

2. 当$\Delta t_0$不变时，流水线的效率与吞吐率成正比。
   $$
   E=TP\Delta t_0
   $$

3. 当$m$和$\Delta t_0$不变时，流水线的加速比与吞吐率呈正比。
   $$
   TP=\frac{S}{m\Delta t_0}
   $$

(5)结论

• 流水线并不能减少单条指令的执行时间，但是可以提高吞吐率。
• 流水线深度↑，流水线性能↑
• 流水线深度受限于流水线延迟与额外开销。
• 流水线寄存器使用高速锁存器。
• 指令之间的相关，限制了流水线的性能。

四、流水线中的相关

流水线中的相关是指相邻or相近的两条指令因存在某种关联，后一条指令不能在原先指定的时钟周期开始执行。

basic solution：暂停

暂停流水线中某条指令及其后面所有指令的执行，该指令之前的所有指令继续执行。

全局性相关：转移指令引起的控制相关，对于流水计算机吞吐率、效率的影响比数据相关严重得多。

局部性相关：一般这么称呼数据相关。

(1)结构相关

当指令在重叠执行的过程中，硬件资源满足不了指令重叠执行的要求，发生资源冲突。

比如存储器不能在同一时刻既取指又存数。

导致结构相关的常见原因：

• 功能部件不是全流水
• 重复设置的资源数量不足

解决方法：

• 插入暂停周期（等到可以继续执行的时间）
• 设置相互独立的指令存储器和数据存储器或者是Cache（实际上也是对存储器流水化了，设置了多个段这样，还是增加了硬件资源）

(2)数据相关

因一条指令需要用到前面指令的结果，而无法与产生结果的指令重叠执行。

产生原因：当很多指令在执行的时候，读写操作数的顺序可能会改变，从而导致结果改变。

举个栗子：

//写后读RAW
MOV AX,1000
MOV BL,123
DIV BL//AX=AX/BL
MOV BX,AX//BX=AX

对于第三条DIV指令，由于使除法，所以执行的很慢；但是由于流水线的存在，在DIV执行的时候，MOV指令也开始取指准备执行。但是MOV指令要使用AX，但是此时缓慢的DIV还在执行，没有将结果写入AX······

分类

设有两条指令i和j，都会访问同一寄存器R。

• RAW写后读

若j在i完成写之前从R中读出数据，会得到错误的结果（如上面的栗子）。

• WAW写后写

若j在i之前完成写操作，R中保存错误的结果。

• WAR读后写

若j先将数据写入R，i将读出错误的结果。

RAR不会引起数据相关。

解决方法

向流水线中插入暂停周期。

• 采用直通技术

控制逻辑将前面指令的结果从其产生的地方直接连通到当前指令所处的位置。

就没有存放这一步骤（暂时），因为浪费时间。

• 增加专用硬件

增加流水线互锁硬件(interlock)。互锁硬件先要检测流水线中指令的数据相关性，当互锁硬件发现数据相关是，使流水线工作停顿下来，直到相关消失为止。

• 利用编译器

流水线调度：编译器可以对指令重新排序或插入空操作指令，使得加载任何冲突数据的操作被延迟，但对重新逻辑or输出不受影响。

在编译器这一步就对指令的执行顺序做出调整。

(3)控制相关

当流水线遇到分支指令和其它会改变PC值的指令。

无条件跳转、条件跳转

那么其实无条件跳转相对来说好处理一点，在无条件转移指令之类的指令必须执行；但是对于条件转移，它有一个判断跳转到哪、做决策的过程。

条件分支指令对于流水线性能的影响远比无条件转移指令要大。

所以，其实重点就是，如何对条件转移指令进行处理。

(1)冻结流水线

用于早期CPU，已过时。一旦在指令译码段检测到分支指令，就在转移目标地址确定之前保存or删除所有紧随分支指令之后的指令，当分支指令从执行段流出，确定出新的PC值时，流水线才继续根据新的PC值填充流水线。

这会严重影响流水线的性能。

(2)预取分支目标

在条件分支指令被识别时，除了紧随其后的指令外，分支目标也被预取放在当前流水线，并保存到分支指令被执行。

分支目标 已经进行了取指等操作。

如果分支跳转发生，已预取的目标指令可立刻执行。

(3)多流

在条件分支的两路上同时启动取指令操作，并将指令保存到分支指令被实际执行时。

就是对于预取分支目标的扩展。但是个人感觉开销可能会更大？

(4)循环缓冲器

什么是循环缓冲器？是一个小的、非常高速的存储器。

循环缓冲器中保存着最近获取的n条顺序的指令。若分支发生，硬件先检查分支目标是否在缓冲器中；如果在，下一条指令从缓冲器中获取。

它的好处是：

• 当分支未发生时，顺序获取的指令已在缓冲器中。
• 如果它的容量比较大(可以满足循环中的全部指令)，则循环中的指令只需要从内存中读出一次。
• 假如它的容量比较大(但是也没有那么大，但也不小，指目标地址仅仅是在分支指令之后的几个单元处)，当分支发生时，目标已在缓冲器中。应用：普通的if-then-else语句

分支预测

静态分支预测

可以采用的预测方法：

• 出错检测处理：预测分支不会发生。
• 循环：预测分支总是发生。
• 编译器预测(有先验预测)
• 剖面法：实际运行该程序(模拟器上)，然后将有关信息送给编译器。(作弊，有后验预测)

如果预测错了咋办？

• 对于已经执行的指令，其结果保存在临时寄存器中。

• 对于将要执行的指令，把将要被覆盖的寄存器的原值保存在临时寄存器中。

动态分支预测

分支历史表：也称为分支预测缓存。下面是一个栗子：

延迟分支

流水线遇到分支指令时，按照正常方式处理，同时执行延迟槽中的指令。

分支延迟槽：程序中位于转移指令后面的存储单元的位置。

延迟转移技术

1. 对于放入延迟槽中的指令需满足：
   • 被转移指令在移动过程中与所经过的指令之间没有数据相关。
   • 被移动指令不破坏条件码，至少不影响后面的指令使用条件码。
2. 如果找不到符合上述条件的指令，须在条件转移指令后插入空操作NOP。
3. 若指令的执行过程分为多个流水段，则需插入多条指令。

延迟槽调度：编译器的任务就是在延迟槽中放入有用的指令。有以下三种调度方法：

• 从分支前(before)调入
• 从目标处(target)调入
• 从失败处(fall-through)调入

指令取消技术

如果采用延迟转移技术，经常会找不到可以用来调整的指令。

向后转移(适用于循环程序)：

1. 循环体的第一条指令安放在两个位置，分别在循环体的前面和后面。
2. if转移成功，则执行转移指令(循环体)后面的指令，然后转移到目标地址；
3. else，取消转移指令(循环体)后面的指令。

向前转移：

1. if转移不成功，执行转移指令之后的下条指令；
2. else取消下条指令，转移到目标地址执行。

五、指令级并行

当指令不相关时，它们在流水线中重叠执行，这种指令间潜在的并行性称为指令级并行。

指令流水线的限制：增加指令发射的宽度和指令流水线的深度，要求复杂硬件电路和高频率时钟的支持。导致CPU功耗up。

功耗时限制当代处理器发展的首要因素。

突破限制的途径：

• 流水线深度
• 从更深层次解决流水线中可能存在的各种相关性
• 多核CPU，多指令流水线
• 提高指令级并行的技术
  • 乱序执行
  • 寄存器重命名
  • 推测执行

提高指令性并行的技术

乱序执行&寄存器重命名

乱序执行：跳过相关的指令取执行后面不相关的指令，使得指令的执行顺序不再按原程序的顺序执行。

要求指令调度算法必须保障程序的运行结果和按照顺序执行时的结果相同。

寄存器重命名技术：使用隐秘寄存器对寄存器重命名，可有效地减少WAR和WAW相关。

好处：使用乱序执行&寄存器重命名，可以把运算速度几乎提高到原来的两倍。

坏处：乱序完成使得中断不精确。

推测执行

在不知道是否需要执行之前就执行代码的技术。

• 需要编译器和硬件的支持。
• 需要对体系结果进行扩展。

对于推测执行，分为：

1. 硬件推测：基于动态调度的分支的扩展。
   • 在分支预测的结果时正确的情况下，硬件推测将按照预测的结果取指、发射指令并执行指令。
   • 动态调度仅获得和发射指令。
2. 软件推测：编译器。

多指令发射技术

一个时钟周期内流出多条指令，CPI(Cycles Per Instructions)<1，IPC>1。

对于多指令流出处理器有三种基本结构：

• 超标量(编译器静态调度or动态调度)
• 超流水：将每个功能部件进一步流水化，特別是取指or指令流出被分解为多段。
• 超长指令字：把很多条指令综合成一条超级长的指令，只能使用编译静态调度。

指令级高度并行的超级处理器

主要分为以下三种:

• 超标量：内置多个流水线(不是流水线的段噢，是多个多个多个流水线)
• 超流水线：将流水线的IF,AD,ALU等关键步骤进一步细分为多个阶段。
• 超标量超流水线：多流水线+指令级细分

就是说在没有看到结果之前，可能有一些人(比如我)会觉得：超标量很好，超流水线也很好，那么综合得到的超标量超流水线应当是集二家之长，性能更优才对；为什么得到的结果会是：超标量>超标量超流水线>超流水线呢？

主要是因为，实际上超流水线是很理想的，难以实现。但是超标量结构就比较简单酱。因此将不现实的与简单实际的融合···

以下是正经解释(雾)：

最后，以上关于流水线，主要是工作在单处理器的情况下。于是提出了对于现在常用的多核处理器运用流水线技术：

这实际上是将指令级并行提升至线程级并行。是目前为止可以替代并超越超标量&超长指令字(现在运用最多？反正就是最优的选择)的最佳选择。