【指令执行阶段】

计算机的流水线是把一个重复的过程分解为若干子过程，每个子过程与其他子过程并行执行，采用流水线技术只需要增加少量硬件就能把计算机的运算速度提高几倍

一条指令的执行过程可以分成多个阶段，根据计算机的不同，具体分法也不同，但一条指令的执行过程可以分为如下三个阶段：

取指：根据 PC 内容访问主存储器，取出一条指令送到 IR 中
分析：对指令操作码进行译码，按照给定的寻址方式和地址字段中的内容形成操作数的有效地址 EA，并从有效地址 EA 中取出操作数
执行：根据操作码字段，完成指令规定的功能，即把运算结果写到通用寄存器或主存中

【指令执行方式】

顺序执行方式

指令按顺序执行，前一条指令执行完后，才启动下一条指令

设取指、分析、执行三个阶段的时间都相等，用 $t$ 表示，则顺序执行 $n$ 条指令所用时间 $T$ 为：

$T=3nt$

传统冯·诺依曼机采用顺序执行方式，又称串行执行方式，其优点是控制简单，硬件代价小，但是执行指令的速度较慢，在任何时刻，处理机中只有一条指令在执行，各功能部件的利用率很低

一次重叠执行方式

这种方式把第 $k$ 条指令的执行阶段和第 $k+1$ 条指令的取指阶段同时进行

采用此种方式时，执行 $n$ 条指令所用的时间为：

$T=(1+2n)t$

采用一次重叠执行方式的优点是程序的执行时间缩短了三分之一，各功能部件的利用率明显提高，但为此需要付出硬件上较大开销的代价，控制过程也比顺序执行复杂了

二次重叠执行方式

为了进一步提高指令的执行速度，可以把取 $k+1$ 条指令提前到分析第 $k$ 条指令的期间完成，而将分析第 $k+1$ 条指令与执行第 $k$ 条指令同时进行

采用此种方式时，执行 $n$ 条指令所用的时间为：

$T=(2+n)t$

与顺序执行方式相比，采用二次重叠执行方式能够使指令的执行时间缩短近三分之二，这是一种理想的指令执行方式，在正常情况下，处理机中同时有三条指令在执行

【流水线表示方法】

通常用时空图的表示方法来直观地描述流水线的工作过程

在时空图中，横坐标表示时间，也就是输入到流水线中的各个任务在流水线中所经过的时间，当流水线中各个流水段的执行时间都相等时，横坐标就被分割成相等长度的时间段，纵坐标表示空间，即流水线的每一个流水段（对应各执行部件）

如上图所示，第一条指令 $I_1$ 在时刻 $t_0$ 进入流水线，在时刻 $t_4$ 流出流水线，第二条指令 $I_2$ 在时刻 $t_1$ 进入流水线，在时刻 $t_5$ 流出流水线，依此类推，每经过一个 $\Delta t$ 时间，便有一条指令进入流水线，从时刻 $t_4$ 开始有一条指令流出流水线

从图中可以看出，当 $t_8=8\Delta t$ 时，流水线上便由 $5$ 条指令流出，如果采用串行方式执行指令，当 $t_8=8\Delta t$ 时，只能执行 $2$ 条指令，可见使用流水线方式成倍地提高了计算机的速度

【流水线方式的特点】

与传统的串行执行方式相比，采用流水线方式具有如下特点：

把一个任务（一条指令或一个操作）分解为几个有联系的子任务，每个子任务由一个专门的功能部件来执行，并依靠多个功能部件并行工作来缩短程序的执行时间
流水线每一个功能段部件后面都要有一个缓冲寄存器，或称为锁存器，其作用是保存本流水段的执行结果，提供给下一流水段使用
流水线中各功能段的时间应尽量相等，否则将引起堵塞、断流
只有连续不断地提供同一种任务时才能发挥流水线的效率，所以在流水线中处理的必须是连续任务，在采用流水线方式工作的处理机中，要在软件和硬件设计等多方面尽量为流水线提供连续的任务
流水线需要有装入时间和排空时间，装入时间是指第一个任务进入流水线到输出流水线的时间，排空时间是指最后一个任务进入流水线到输出流水线的时间

【流水线的分类】

按照不同的分类标准，可以把流水线分成多种不同的种类

下面从几个不同的角度介绍流水线的基本分类方法：

根据流水线使用的级别的不同，流水线可分为：

部件功能级流水：将复杂的算术逻辑运算组成流水线工作方式，例如，可将浮点加法操作分成求阶差、对阶、尾数相加以及结果规格化等四个子过程
处理机级流水：把一条指令解释过程分成多个子过程，如取指、译码、执行、访存、写回五个子过程
处理机间流水：是一种宏流水，其中每一个处理机完成某一专门任务，各个处理机所得到的结果需存放在与下一个处理机所共享的存储器中

根据流水线可以完成的功能，流水线可分为：

单功能流水线：只能实现一种固定的专门功能的流水线
多功能流水线：通过各段间的不同连接方式可以同时或不同时地实现多种功能的流水线

根据同一时间内各段之间的连接方式，流水线可分为：

静态流水线：在同一时间内，流水线的各段只能按同一种功能的连接方式工作
动态流水线：在同一时间内，当某些段正在实现某种运算时，另一些段却正在进行另一种运算，这样对提高流水线的效率很有好处，但会使流水线控制变得很复杂

根据流水线的各个功能段之间是否有反馈信号，流水线可分为：

线性流水线：从输入到输出，每个功能段只允许经过一次，不存在反馈回路
非线性流水线：存在反馈回路，从输入到输出过程中，某些功能段将数次通过流水线，这种流水线适合进行线性递归的运算

【影响流水线的因素】

流水线中存在一些相关的情况，它使下一条指令无法在设计的时钟周期内执行，这些相关将降低流水线性能

结构相关

又称资源冲突，是指多条指令在同一时刻争用同一资源而形成的冲突

有以下两种解决办法：

前一指令访存时，使后一条相关指令（以及其后续指令）暂停一个时钟周期
单独设置数据存储器和指令存储器，使两项操作各自在不同的存储器中进行，这属于资源重复配置

数据相关

又称数据冲突，是指在一个程序中，存在必须等前一条指令执行完才能执行后一条指令的情况

当多条指令重叠处理时就会发生冲突，解决的办法有以下三种：

暂停时钟周期：把遇到数据相关的指令及其后续指令都暂停一至几个时钟周期，直到数据相关问题消失后再继续执行，常用的有硬件阻塞（stall）、软件插入 NOP 指令两种方法
数据旁路技术：设置相关专用通路，即不等前一条指令把计算结果写回寄存器组，下一条指令也不再读寄存器组，而是直接把前一条指令的ALU的计算结果作为自己的输入数据开始计算过程，使本来需要暂停的操作变得可以继续执行
编译优化：通过编译器对数据相关的指令编译优化的方法，调整指令顺序来解决数据相关

控制相关

又称控制冲突，是指当流水线遇到转移指令和其他改变PC值的指令而造成断流

解决的办法有以下四种：

对转移指令进行分支预测，尽早生成转移目标地址
1. 静态预测：总是预测条件不满足，即继续执行分支指令的后续指令
2. 动态预测：根据程序执行的历史情况，进行动态预测调整，有较高的预测准确率
预取转移成功和不成功两个控制流方向上的目标指令
加快和提前形成条件码
提高转移方向的猜准率

【流水线性能指标】

吞吐率

在指令级流水线中，吞吐率是指在单位时间内流水线所完成的任务数量，或是输出结果的数量

计算流水线吞吐率（TP）的最基本的公式为：

$TP=\frac{n}{T_k}$

式中，$n$ 是任务数，$T$ 是处理完成 $n$ 个任务所用的时间

下面以流水线中各段执行时间都相等为例来讨论流水线的吞吐率，如下图所示的各段执行时间均相等的流水线时空图，当输入到流水线中的任务是连续的理想情况下，一条 $k$ 段线性流水线能够在 $k+n-1$ 个时钟周期内完成 $n$ 个任务，其中，$k$ 为流水线的段数，$\Delta$ 为时钟周期

易得出流水线的实际吞吐率为：

$TP=\frac{n}{(k+n-1)\Delta t}$

当连续输入的任务 $n\rightarrow \infty$ 时，可得最大吞吐率为：

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

加速比

完成同样一批任务，不使用流水线所用的时间与使用流水线所用的时间之比称为流水线的加速比

设 $T_0$ 表示不使用流水线时的执行时间，即顺序执行所用的时间，$T_k$ 表示使用流水线时的执行时间，则计算流水线加速比（S）的基本公式为：

$S=\frac{T_0}{T_k}$

如果流水线各段执行时间都相等，则一条 $k$ 段流水线完成 $n$ 个任务所需的时间为：

$T=(k+n-1)\Delta t$

而不使用流水线，即顺序执行 $n$ 个任务时，所需的时间为：

$T_0＝kn\Delta t$

将 $T_0$ 和 $T_k$ 值代入上式，得实际加速比为：

$S=\frac{kn\Delta t}{(k+n-1)\Delta t} = \frac{kn}{k+n-1}$

当连续输入的任务 $n\rightarrow \infty$ 时，最大加速比为：

$S_{max} = k$

效率

流水线的设备利用率称为流水线的效率，在时空图上，流水线的效率定义为完成 $n$ 个任务占用的时空区有效面积与 $n$ 个任务所用的时间与k个流水段所围成的时空区总面积之比

因此，流水线的效率包含了时间和空间两个因素

$n$ 个任务占用的时空区有效面积就是顺序执行 $n$ 个任务所使用的总时间 $T_0$，而 $n$ 个任务所用的时间与 $k$ 个流水段所围成的时空区总面积为 $kT_k$，其中 $T_k$ 是流水线完成 $n$ 个任务所使用的总时间，计算流水线效率（E）的一般公式为：

$E=\frac{T_0}{kT_k}$

如果流水线的各段执行时间相等，上式中的分子部分是 $n$ 个任务实际占用的有效面积，分母部分是完成 $n$ 个任务所用的时间与 $k$ 个流水段所围成的总面积

流水线的各段执行时间均相等，当连续输入的任务 $n\rightarrow \infty$ 时，最高效率为：

$E_{max}=1$

【流水线多发技术】

超标量流水线技术

每个时钟周期内可并发多条独立指令，即以并行操作方式将两条或多条指令编译并执行，为此需配置多个功能部件

超标量计算机不能调整指令的执行顺序，通过编译优化技术，把可并行执行的指令搭配起来，挖掘更多的指令并行性

超流水线技术

在一个时钟周期内再分段，在一个时钟周期内一个功能部件使用多次

不能调整指令的执行顺序，靠编译程序解决优化问题

超长指令字

由编译程序挖掘出指令间潜在的并行性，将多条并行操作的指令组合成一条具有多个操作码字段的超长指令字

超长指令字可达几百位，为此需要采用多个额外的处理部件

Alex_McAvoy

指令流水线