计算机组成原理（11）----指令流水线

一.指令流水的定义

二.流水线的表示方式

1.指令执行过程图

2.时空图

三.流水线的性能指标

1.吞吐率

2.加速比

3.效率

四.指令流水线影响因素分类

（1）结构相关（资源冲突）

（2）数据相关（数据冲突）

（3）控制相关（控制冲突）

五.流水线的分类（了解）

1.部件功能级、处理机级和处理机间级流水线

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

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

4.线性流水线和非线性流水线

六.流水线的多发技术

1.超标量技术

2.超流水技术

3.超长指令字

七.五段式指令流水线

（1）运算类指令

（2）LOAD指令

（3）STORE指令

（4）条件转移指令

（5）无条件转移指令

八.例题

一.指令流水的定义

一条指令的执行过程可以分成多个阶段(或过程)根据计算机的不同，具体的分法也不同。最简单的划分方式就是将其划分为3个阶段：取指，分析，执行。每个阶段用到的硬件不一样。

取指：根据PC内容访问主存储器（可能是Cache）,取出一条指令送到IR中。

分析：对指令操作码进行译码，按照给定的寻址方式和地址字段中的内容形成操作数的有效地址EA，并从有效地址EA中取出操作数（可能从寄存器中取出，可能从主存中取出，也可能从Cache中取出）。

执行：根据操作码字段，完成指令规定的功能，即把运算结果写到通用寄存器或主存中。

设取指、分析、执行3个阶段的时间都相等用t表示，按以下几种执行方式分析n条指令的执行时间：

1.顺序执行方式

总耗时T=nx3t=3nt

传统冯·诺依曼机采用顺序执行方式，又称串行执行方式。

优点：硬件代价较小，控制指令的执行流时较简单

缺点：执行指令的速度较慢，在任何时刻，处理机中只有条指令在执行，各功能部件的利用率很低。

2.一次重叠执行方式

总耗时T=3t+(n-1)x2t=(1+2n)t

除了第一条指令的执行需要3t时间，其余指令逻辑上只需要消耗2t时间

优点：程序的执行时间缩短了1/3，各功能部件的利率明显提高。

缺点：需要付出硬件上较大开销的代价，控制过程也比顺序执行复杂了。

3.二次重叠执行方式

总耗时T =3t+(n-1)xt = (2+n)t

从逻辑上看，第一条指令耗时为3t，后面的指令每执行一条耗时为1t

与顺序执行方式相比，指令的执行时间缩短近2/3。这是一种理想的指令执行方式（就是各阶段花费时间相同；每个阶段结束后能立即进入下一阶段。）

在正常情况下，处理机中可能同时有3条指令在执行（三条指令处于不同阶段）。若指令执行被分为4个或5个阶段，若能实现各个阶段使用的硬件部件相互独立，那么同一时刻可能就会有4条或5条指令正在执行。

也可以把每条指令的执行过程分成4个或5个阶段，分成5个阶段是比较常见的做法。

二.流水线的表示方式

1.指令执行过程图

主要用于分析指令执行过程以及影响流水线的因素

2.时空图

横坐标表示时间，纵坐标表示不同的指令执行阶段

主要用于分析流水线的性能

三.流水线的性能指标

1.吞吐率

吞吐率是指在单位时间内流水线所完成的任务数量，或是输出结果的数量。设任务数为n；处理完成n个任务所用的时间为Tk

则计算流水线吞吐率(TP)的最基本的公式为TP=n/Tk

理想情况下，流水线的时空图如下：

每条指令的执行分为k个阶段，每个阶段耗时 $\Delta t$ ，一般取 $\Delta t$ =一个时钟周期

对于第一条指令，k个阶段，则耗时为k $\Delta t$ ，之后每经过一个 $\Delta t$ 就会执行完一条指令。

当连续输入的任务n---> $\infty$ 时，得最大吞吐率为TPmax=1/ $\Delta t$ 。

补充：装入时间与排空时间

装入时间：第一条指令从开始执行到结束所需要的时间

排空时间：最后一条指令从开始执行到结束所需要的时间

因为各个执行阶段，处理的硬件部件是相互独立的，所以装入时间就是各个硬件部件陆续投入使用的时间，而排空时间就是，各个硬件部件陆续结束工作的时间。

2.加速比

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

设T0表示不使用流水线时的执行时间，即顺序执行所用的时间；Tk表示使用流水线时的执行时间。

则计算流水线加速比(S)的基本公式为S=T0/Tk

理想情况下，流水线的时空图如下：

一条指令的执行分为k个阶段，每个阶段耗时 $\Delta t$ ，一般取 $\Delta t$ =一个时钟周期

单独完成一个任务耗时为k $\Delta t$ ，则顺序完成n个任务耗时T0=nk $\Delta t$ ，而Tk=(k+n-1) $\Delta t$

当连续输入的任务n---> $\infty$ 时，最大加速比为Smax=k

3.效率

流水线的设备利用率称为流水线的效率。

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

理想情况下，流水线的时空图如下:

一条指令的执行分为k个阶段，每个阶段耗时 $\Delta t$ ，一般取 $\Delta t$ =一个时钟周期。如下图所示，每个执行阶段使用的设备相互独立，4个执行阶段，则有4组设备。

流水线效率（E）的一般公式为：

当连续输入的任务n→ $\infty$ 时，最高效率Emax=1。

四.指令流水线影响因素分类

上面建立的指令流水线的工作模型都是理想的指令执行方式，就是各阶段花费时间相同；每个阶段结束后能立即进入下一阶段。但是事实上会有以下因素影响流水线的工作：

我们设置机器周期如下所示：

这是五段式指令流水线是MIPS架构提出的，即MIPS架构下，一条指令会被分为5个阶段，而MIPS是第一个精简指令集系统（RISC）。

虽然有的指令在实际执行时不需要执行某些阶段，但是为了方便指令流水线的设计：

1.所有指令都会被安排为5个机器周期（有的机器周期可以不执行任何指令）。

取指令--->指令译码--->指令的执行--->访存--->将运算结果写回通用寄存器组

2.同时，需要将指令每个阶段的耗时取成一样，以最长耗时为准。即此处应将机器周期设置为100ns。

在第二个阶段耗时为80ns，即180ns就可以完成译码，如何将其设置为在200ns时完成指令译码呢？这就需要在每一个功能段部件后面设置一个缓冲寄存器，或称为锁存器。其作用是保存本流水段的执行结果，提供给下流水段使用。

对于第一阶段：取指令

我们之前说的取指令一般都是到主存中取指令，但是当前使用的指令或数据会在Cache中保留一个副本，并且基于局部性原理，Cache的命中概率是很高的，所以大部分情况下，都能从Cache中找到想要的指令，而不需要访存。

对于第四个阶段：访存

原理与第一阶段类似，大部分情况下，都能从Cache中找到想要的数据，由于第四个阶段我们访问的不是指令，而是指令要操作的某些数据，所以这里访问的是Data Cache。

Cache会被分为两块，一块专门用来存储指令，另一块专门用来存储变量。把指令和数据分开存放在Cache的两个独立模块中，则对这两个模块的访问是能够并行进行的。

若在Cache中找不到相应数据，则会出现流水线断流的情况。因为Cache不命中，就需要访问主存。

对于第二阶段：译码

除了指令译码外，还会将操作数从通用寄存器取出放到锁存器中，或者直接从指令当中取出立即数，放入Imm（专门存放立即数的锁存器），即进行取数操作。

对于第三阶段：执行指令

用ALU算术逻辑单元处理取出的操作数

对于第四阶段，第五阶段：访存，将运算结果写回通用寄存器组

就是将运算的结果写回主存或者通过锁存器将运算结果写回某个通用寄存器中

（1）结构相关（资源冲突）

由于多条指令在同一时刻争用同一资源而形成的冲突称为结构相关（与操作系统的互斥是相同的原理）。如下图所示，对于Load和Instr3，若两条指令在同一时刻使用Mem（主存或Cache）或Reg（同一通用寄存器），则会产生资源冲突。

解决办法:
1.后一相关指令暂停一周期
2.资源重复配置：数据存储器+指令存储器，就是将指令和数据分别放到不同的Cache块或存储体中，那么取指令和取数据就能同时执行，不会产生冲突。如下图所示：

（2）数据相关（数据冲突）

数据相关指在一个程序中，存在必须等前一条指令执行完才能执行后一条指令的情况，则这两条指令即为数据相关。（与操作系统的同步是相同的原理）

如下图所示，需要执行完第一条指令，就是将加法运算的结果写回r1后，才能执行第二条指令。这样才不会导致数据冲突。

解决办法：
1.把遇到数据相关的指令及其后续指令都暂停一至几个时钟周期，直到数据相关问
题消失后再继续执行。可分为硬件阻塞(stall)和软件插入“NOP”（空指令）两种方法。

硬件阻塞（stall）：

软件插入“NOP”，每条空指令的执行也会经历完整的5个周期

2.数据旁路技术

如下图所示，也就是将r2和r3相加的结果作为下一条指令的其中一个输入端，而不需要等运算结果写回r1后，再用r1作为下一条指令的输入端。

3.编译优化

通过编译器调整指令顺序来解决数据相关。如下图所示，若后面的指令不与第一条指令的结果相关，则可以把他们插到第一条指令后执行，执行完这些指令，再执行第二条指令则能减少数据冲突的概率。

（3）控制相关（控制冲突）

当流水线遇到转移指令和其他改变PC值的指令而造成断流时，会引起控制相关。

如下图所示，若PC=12的指令直接跳转到了PC=1000的指令，那么中间的指令是不应该执行的。

解决方法：

1.转移指令分支预测

简单预测(永远猜true或false)、动态预测(根据历史情况动态调整)

2.预取转移成功和不成功两个控制流方向上的目标指令

3.加快和提前形成条件码。例如设置加法器时，需要将全加器串联，每个全加器都会依赖于前一个全加器产生的进位，但可以经过电路改造，将进位的信息提前的发送到最后一个全加器，从而提高运算效率，这里同理。

4.提高转移方向的猜准率。

五.流水线的分类（了解）

1.部件功能级、处理机级和处理机间级流水线

根据流水线使用的级别的不同，流水线可分为部件功能级流水线、处理机级流水线和处理机间流水线。

部件功能级流水就是将复杂的算术逻辑运算组成流水线工作方式。例如，可将浮点加法操作分成求阶差、对阶、尾数相加以及结果规格化等4个子过程。

处理机级流水是把一条指令解释过程分成多个子过程，如前面提到的取指、译码、执行、访存及写回5个子过程。

处理机间流水是一种宏流水，其中每一个处理机完成某一专门任务，各个处理机所得到的结果需存放在与下一个处理机所共享的存储器中。

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

按流水线可以完成的功能，流水线可分为单功能流水线和多功能流水线。

单功能流水线指只能实现一种固定的专门功能的流水线；

多功能流水线指通过各段间的不同连接方式可以同时或不同时地实现多种功能的流水线。

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

按同一时间内各段之间的连接方式，流水线可分为静态流水线和动态流水线。

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

动态流水线指在同一时间内，当某些段正在实现某种运算时，另一些段却正在进行另一种运算。这样对提高流水线的效率很有好处，但会使流水线控制变得很复杂。

4.线性流水线和非线性流水线

按流水线的各个功能段之间是否有反馈信号，流水线可分为线性流水线与非线性流水线。

线性流水线中，从输入到输出，每个功能段只允许经过一次，不存在反馈回路。

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

六.流水线的多发技术

注：这里以理想情况进行分析，即每个机器周期(功能段)只消耗一个时钟周期。

1.超标量技术

每个时钟周期内可并发多条独立指令

要配置多个功能部件，只要编译器得到了最终的机器指令序列，就不能调整指令的执行顺序。通过编译优化技术，把可并行执行的指令搭配起来，所以对编译优化技术的要求较高，需要考虑那些指令可以并行执行，哪些指令不可以并行执行。

2.超流水技术

在 一个时钟周期内再分段(3段)，所以在一个时钟周期内一个功能部件可能被使用多次(3次)，这一技术也不能调整指令的执行顺序。同样依靠编译程序解决优化问题。

超标量技术，是一种空分复用技术，通过增加多个功能部件，使得同一时间段内能并发执行多条指令。

超流水技术，是一种时分复用技术，将一个时钟周期分为更小的时间段，每个时间段内执行的指令不同。

3.超长指令字

由编译程序挖掘 岀指令间 潜在的并行性，若多条指令在执行阶段需要用到的功能部件完全不同，那么这些指令就可以并行执行。

将多条能 并行操作 的指令组合成 一条。具有 多个操作码字段 的 超长指令字(可达几百位)，想要多个操作字段 同时进行，就需要采用多个处理部件。

七.五段式指令流水线

五段式指令流水线是MIPS架构提出的，即在MIPS架构下，一条指令会被分为5个阶段。而MIPS是第一个精简指令集系统（RISC）。

①IF取指----> ②ID译码&取数 ----> ③EX执行----> ④M访存 ----> ⑤WB写回寄存器

为方便流水线的设计：

1.即使实际上某些指令不需要经历五个阶段，指令也会被安排为5个阶段。某些不需要执行的阶段则被设为空段。

2.将每个阶段的耗时取成一样，以最长耗时为准即此处应将机器周期设置为100ns。
理想情况下，每个机器周期(功能段)只消耗一个时钟周期。

接下来分析一下指令如何根据5个功能段完成工作：

（1）运算类指令

•IF：根据PC从指令Cache取指令至IF段的锁存器

•ID：取出操作数至ID段锁存器

对于ADD Rs,Rd，Rs会存放到A锁存器中，Rd会存放到B锁存器中

对于ADD #996，Rd，#996会存放在Imm（立即数锁存器）中，Rd会存放在A或B锁存器中

对于SHL Rd，Rd会存放在A或B锁存器中

•EX：ALU会根据上一阶段操作数进行运算，将结果存入EX段锁存器

•M：空段

对于精简指令集系统，所有运算类的指令的操作数都来自于寄存器，或者指令中的立即数，并且运算的结果都会存回某一个寄存器，而不是主存，因此第4个阶段（访存），运算类的指令是不需要做任何事的。但是这一段时间是必须消耗的。

•WB：将运算结果写回指定寄存器。具体地，将第三个阶段的运算结果，放到第四个阶段的锁存器中，再将锁存器的运算结果写回到某一个通用寄存器中

（2）LOAD指令

LOAD Rd,996(Rs)：在Rs的基础上加996，以相加的结果作为有效地址，根据这一有效地址在存储体中找到相应数据，再把这一数据放到Rd中

这里使用了基址寻址的方式，也就是用Rs指明这一寄存器的起始地址，相对于起始地址往后偏移996，就是想寻找的数据的有效地址。

IF：根据PC从指令Cache取指令至IF段的锁存器
ID：将基址寄存器的值放到锁存器A，将偏移量的值放到Imm（专门存放立即数的锁存器）

EX：将基址与偏移量相加，得到有效地址。放到EX段的锁存器中

M：根据有效地址，从数据Cache中取数并放入锁存器

WB：将取出的数写回寄存器

注：RISC处理器只有“取数LOAD”和“存数STORE”指令才能访问主存。其他指令想要得到的数据，一定直接来自于某个寄存器，或者指令中的立即数。

（3）STORE指令

STORE Rs，996(Rd)：把Rs所指明的寄存器中的数据存到主存中，存放的位置为(996+(Rd)),996为偏移量，而Rd指的是基地址。

IF：根据PC从指令Cache取指令至IF段的锁存器

ID：将基址寄存器的值(Rd)放到锁存器A，将偏移量的值放到lmm。将要存的数(Rs)放到锁存器B中。

EX：将锁存器A中的基地址与Imm中的偏移量相加，得到有效地址。并将锁存器B的内容放到锁存器 Store。

M：根据有效地址EA，将要存的数据写入数据Cache

之后数据Cache会将数据同步回主存。

WB：空段（写回阶段不需要做任何事）

（4）条件转移指令

对于转移类指令，无论是有条件转移还是无条件转移，都是采用相对寻址的方式，即相对于PC的偏移量。

若每条指令的字长为4B

beq Rs，Rt，#偏移量：

若Rs寄存器的数据与Rt寄存器的数据相等，则转移的地址为：

当前这条指令的地址+4+(偏移量*4)

也就是从下条指令的地址开始(PC+4)，往前或往后偏移多少条指令(PC)+4+(996*4)。

bne Rs,Rt ,#偏移量：

若Rs寄存器的数据与Rt寄存器的数据不相等，则转移的地址为：

当前这条指令的地址+4+(偏移量*4)

也就是从下条指令的地址开始(PC+4)，往前或往后偏移多少条指令(PC)+4+(996*4)。

IF：根据PC从指令Cache取指令至IF段的锁存器

ID：进行比较的两个数放入锁存器A、B（Rs寄存器与Rt寄存器中的数据）；偏移量放入Imm（专门存放立即数的锁存器）

EX：比较A,B两个锁存器中的数据，并把运算结果放到下一级的锁存器中。

M：不会进行访存，而是将目标PC值写回PC中，因为根据运算结果是否满足条件就能决定PC的值应该是多少。

很多教材把写回PC的功能段称为“WrPc段”，因为这个功能段所需要的硬件部件与五条指令功能段是相互独立的。其耗时比M段更短，可安排在M段时间内完成。

WB：空段。

注：修改PC的值这一操作是在M阶段，而不是WB阶段，WB阶段通常是修改通用寄存器的值。

（5）无条件转移指令

无条件转移指令通常采用相对寻址

jmp #偏移量：首先(PC)+“1”，即PC先自动指向下一条指令，再(PC)+“1”+(偏移量*指令字长)，即相对于下一条指令的地址向前或向后偏移多少指令

IF：根据PC从指令Cache取指令至IF段的锁存器
ID：偏移量放入Imm

EX：将目标PC值写回PC

M：空段
WB：空段

“WrPC段”耗时比EX段更短，可安排在EX段时间内完成。WrPC段越早完成，就越能避免控制冲突（因为指令流水线中是顺序执行指令，但是转移类指令会修改PC的值，接下来顺序执行的指令并不是我们需要执行的指令，所以转移类指令越早执行，就能尽早发现冲突）。当然，也有的地方会在WB段时间内才修改PC的值。

八.例题

11 LOAD R1，[a] 功能：M[a]--->R1，从主存单元（大概率访问的是data cache）中取出a变量，放到R1寄存器中

12 LOAD R1，[b] 功能：M[b]--->R2，从主存单元（大概率访问的是data cache）中取出b变量，放到R2寄存器中

13 ADD R1，R2 功能：(R1)+(R2)--->R2,将R1寄存器以及R2寄存器的内容相加，存入R2寄存器中

14 STORE R2，[x] 功能：(R2)--->M[x]，将R2中的数据存放到x对应的存储单元中

则这4条指令执行过程中I3的ID段和I4的IF段被阻塞的原因各是什么?

（1）13的ID段被阻塞的原因：

11，12都是取数指令，取数指令需要到WB（第五个阶段）才能将数取到对应的寄存器中，如图所示 I1 指令与 I2 指令分别是在 5，6 时间单元才被写回R1寄存器，R2寄存器

而I3这条加法指令的ID段，除了译码之外，还需要从R1和R2中取出两个操作数，所以I3指令的ID段必须安排在前两条指令的WB完成后，才能进行。

总结：I3与I1和I2存在数据相关

（2）I4的IF段被阻塞的原因：

I3指令先执行IF段，就是将I3指令放到锁存器中，但是由于数据相关的存在，所以I3这条指令暂时无法进入ID段，而是暂存在IF段的锁存器中。若此时开始执行I4指令的IF段，这就意味着IF段锁存器原来的I3指令会被I4指令覆盖。

因此必须等待I3指令进入ID段，释放掉IF段锁存器中的I3指令后，才能让I4指令的IF段开始执行。

总结：I4的IF段必须在I3进入ID段后才能开始，否则会覆盖IF段锁存器的内容