4. 流水线冒险的检测与处理
第 3 版 · OCR 辅助 · 原书检索 · 文字用于定位，公式与图表请回原页核验 · 本次导入快照
## 4. 流水线冒险的检测与处理
指令流水线中，可能会遇到一些情况使得流水线无法正确执行后续指令，而引起流水线阻塞(停顿)。这种现象称为流水线冒险。根据导致冒险的原因的不同，流水线冒险分为结构冒险、数据冒险和控制冒险三种。
结构冒险又称资源冲突，由多条指令同时竞用同一个功能部件引起。所用的解决策略包括：①规定每个功能部件在一条指令中只能被用一次；②规定每个功能部件只能在某个特定的阶段被用；③将指令存储器（如 Code Cache）和数据存储器（如 Data Cache）分开。
数据冒险又称数据相关。当前面指令的执行结果是后面指令的操作数时，可能会发生数据冒险。所用解决策略有软件和硬件两种方式。
<!-- page: 163 -->
（1）软件方式：编译器在发生数据相关的指令之间插入足够的 nop 指令，这种方式下，CPU 执行程序时便不会发生数据冒险现象，软件方式简化了硬件实现，但是，软件方式会同时增加程序的空间开销和时间开销。
（2）硬件方式：有两种硬件解决方式，一种是单纯采用“阻塞”技术，另一种是采用“转发+阻塞”技术。在图 6.1 中加上转发检测及处理、load-use 冒险检测及处理机制后，就可以解决数据冒险问题。采用“转发+阻塞”技术的部分流水线数据通路如图 6.4 所示。
图 6.4 带转发和 load-use 冒险处理的部分流水线数据通路
CPU 在执行程序过程中，动态检测是否存在数据相关，在存在数据相关的情况下，通过转发（旁路）技术将前面指令执行过程中得到的结果直接传送到后面指令执行时需要操作数的地方，对于像 load-use 这样不能通过转发解决的数据冒险，则在指令的特定流水段插入“气泡”以“阻塞”指令继续执行，直到后面指令能够取得所需数据为止。单纯采用硬件“阻塞”的方式，使得程序的空间开销比软件方式好，但时间开销并没有减少，而采用“转发+阻塞”的方式可同时减少空间开销和时间开销。
控制冒险又称控制相关。当返回指令、分支指令、跳转指令等有可能改变顺序增量的 PC 值时，由于获取转移目标地址的时间较长，使得在目标地址产生前已经有指令被取到流水线中，如果已经取出执行的指令不是应该执行的指令，则发生了控制冒险。所用解决策略也分为软件方式和硬件方式。
（1）软件方式：有两种软件方式，一种是编译器简单地在分支指令、跳转指令等引起控制相关的指令后面插入足够的 nop 指令；另一种是分支延迟调度技术，编译器将前面若干与分支指令等无关的指令调到后面填充到延迟槽中，不够填满延迟槽时，用 nop 指令补足。不同指令的延迟槽（即延迟损失时间片）不同，它与该指令能在几个周期内得到正确的 PC
<!-- page: 164 -->
值有关。在软件进行了这些处理后，流水线执行时就不会发生控制冒险现象。
（2）硬件方式：在分支指令、跳转指令等引起控制相关的指令后面插入“气泡”，使流水线停顿若干时钟，直到得到正确的PC值为止。
对于分支指令引起的控制冒险，若用硬件方式处理，则通常在上述硬件处理的基础上，还会采用“分支预测”技术。有静态预测和动态预测两种技术，静态预测与分支指令执行的历史情况无关，可以预测总是条件满足(taken)而转移，也可以预测总是条件不满足(not taken)而顺序执行；动态预测利用分支指令执行的历史情况来进行预测，并根据实际执行情况动态调整。可采用一位预测、两位预测甚至三位预测技术，动态预测能达到 90% 的成功率。不管采用哪种分支预测技术，只要预测失败，都必须将错误执行的指令从流水线中冲刷掉。
除了上述几种流水线冒险之外，异常和中断的发生、cache缺失、TLB缺失等也都会引起流水线阻塞。对于异常和中断引起的冒险，其处理方式与分支预测错误时的处理类似。对于cache缺失引起的冒险，则无需冲刷指令，只要冻结机器状态若干时钟周期即可。对于TLB缺失，则可以像缺页一样作为一种内部异常来处理，也可以像cache缺失一样完全由硬件处理。关于cache缺失和TLB缺失等内容将在第7章介绍。
## 5. 高级流水线技术
高级流水线技术充分利用指令级并行来提高流水线执行的性能。有两种增加指令级并行的策略：一种是超流水线技术，它通过增加流水线的级数（将流水线划分成更多的流水段）来使更多的指令同时在流水线中重叠执行；另一种是多发射流水线技术，通过同时启动多条指令独立运行来提高指令并行性。
采用多发射技术的处理器称为超标量处理器。要实现多发射流水线必须完成对指令进行打包和冒险处理两个任务，指令打包是指将能并行处理的多条指令同时发射到发射槽中。根据指令打包任务是由编译器静态完成还是由处理器动态完成的，可将多发射技术分为静态多发射和动态多发射两类。
（1）静态多发射处理器通过编译器静态推测来完成指令打包和冒险处理任务，指令打包的结果可看成将同时发射的多条指令合并到一个长指令中，因此，也称之为超长指令字（VLIW）。
（2）动态多发射处理器在指令执行时由处理器硬件进行动态流水线调度来完成指令打包和冒险处理任务，即处理器可以动态地将后面的一些无关指令调到前面先执行。动态流水线调度可以实现“按序发射、按序完成”“无序发射、按序完成”“按序发射、无序完成”“无序发射、无序完成”4种指令执行模式。
## 6.3 基本术语解释
### 指令流水线 (instruction pipelining)
指令流水线是多条指令重叠执行的一种指令执行方式。流水线方式下，一条指令的执行过程被分成若干操作子过程（又称“流水段”），每个子过程由一个独立的功能部件来完成。在同一条流水线中，每条指令所包含的操作子过程个数必须一样，每个子过程所花的时间也要设计成相同。因此，一般按最复杂的指令来设计流水段个数，以最复杂的子过程来设计流
<!-- page: 165 -->
水段的宽度。这样，所有功能部件可以同时执行不同指令的不同子过程中的操作，即第 $i+1$ 条指令的第 $k$ 段和第 $i$ 条指令的第 $k+1$ 段同时执行。理想情况下，经过若干周期后，流水线能在每个周期内执行完一条指令。
现代计算机一般把复杂度相近的指令用同一条流水线完成，而把复杂度相差很大的指令安排在不同的流水线中。
## 流水线深度（pipeline depth）
流水段的个数称为流水线深度或流水线级数。
## 指令吞吐量 (instruction throughput)
指令吞吐量是指单位时间内处理器执行指令的条数。采用流水线指令执行方式能提高指令的吞吐率，但不能缩短每条指令的执行时间。
## 流水段寄存器（pipeline register）
每两个相邻的流水段之间需要设置一个流水段寄存器，用来存放前一个流水段中产生的并需传输到其后所有流水段的信息，包括各种数据（PC、指令、立即数、运算结果、寄存器编号等）和控制信号两大类信息。每个流水段的功能不一样，所需传递的信息也不同，因此，各流水段寄存器的长度也不同。
## 流水线冒险（hazard）
当若干指令都已进入流水线开始执行后，如果其中某些后续指令的某些流水段任务不能按时开始执行（若执行就会发生错误），则说明流水线被破坏，这种现象称为流水线冒险。流水线冒险有结构冒险、控制冒险、数据冒险三种。
## 结构冒险（structural hazard）
在指令流水线中，同一个部件同时被不同指令所使用的现象称为结构冒险，也称为资源冲突（resource conflicts）。
## 控制冒险（control hazard）
在指令流水线中，转移指令或异常等情况改变了程序执行的流程，而使得在目标地址产生前已被取到流水线中的指令无效的现象称为控制冒险，也称为分支冒险（branch hazard）或控制相关（control dependency）或顺序相关（sequential dependency）。
## 数据冒险（data hazard）
在指令流水线中，后面指令用到前面指令的结果时，前面指令的结果还没产生的现象称为数据冒险，也称为数据相关（data dependency）。
## 流水线阻塞（pipeline stall）/气泡（bubble）
流水线中下一条指令不能执行时，就在硬件上加入额外的电路来使得下一条指令延迟若干周期再执行，这种方式称为流水线阻塞或流水线停顿。有时也会形象地称这种做法为在流水线中插入气泡（bubble）。
## 空操作（nop）
空操作就是不做任何动作，而只是在时间上延迟一段时间。有两种情况：①为了规整流水线，在某些指令的执行过程中加入空流水段，这种空流水段中的操作称为空操作；②为了避免流水线冒险，在相关指令的前后加入 nop 指令，使得流水线停顿若干时钟，等到需要的信息得到后再继续执行后面的指令。
<!-- page: 166 -->
# 转发（forwarding）
当后面指令要用到前面指令的结果数据时，前面流水段部件中得到的数据直接通过连线传送到后面流水段的部件中，而不等待前面指令的结束，这种方式称为转发或旁路，它能解决部分数据冒险。
# 旁路(bypassing)
旁路是数据转发技术的别称。
# 分支条件满足（branch taken）/分支条件不满足（branch not taken）
对于条件跳转指令（即分支指令 branch），其执行结果总有两种可能性：一种是条件满足（称为 branch taken），此时转到跳转目的地址处继续执行；另一种是条件不满足（称为 branch not taken），此时则继续取下条指令执行。
# 分支预测（branch predict）
在流水线执行过程中，对每条分支指令进行预测，可以简单地预测 branch taken 或 branch not taken，也可以根据历史情况动态预测。这样，只要预测成功，流水线就不会发生阻塞。如果预测不成功，则流水线要退回到正确的分支地址处重新启动流水线执行，原先不该取出执行的指令要排除出流水线，这称为清洗或冲刷(flush)流水线。
# 分支延迟（delayed branch）
分支延迟调度方法采用编译优化方法调整指令执行顺序，将分支指令前面与分支指令无关的指令放到分支指令后面执行以填充延迟损失时间片（分支延迟槽），不够时再用 nop 操作填充，这样，使得分支指令能在足够的时间内得到跳转地址计算结果，从而避免流水线的阻塞。
# 分支延迟损失时间片（penalty for branch delay）
由于分支指令引起流水线阻塞而带来的延迟执行时钟周期数称为分支延迟时间片。
# 分支延迟槽（branch delay slot）
分支延迟调度方法中，分支指令后面被填的指令位置称为分支延迟槽。需要填入的指令条数（即分支延迟槽数）等于分支延迟损失时间片。
# 指令级并行（Instruction Level Parallelism, ILP）
指令级并行是指在 CPU 执行程序时，通过多条指令之间的并行执行来提高处理器性能的一种技术。
# IPC（Instruction per Clock）
IPC 是每个时钟周期内可以执行完成的指令条数，是 CPI 的倒数。
# 超流水线（superpipelining）
超流水线是指具有更多级流水段的一种流水线。理想情况下，流水线阶段越多，则指令的吞吐率越高，所以一些处理器采用 8 个或更多流水阶段，称为超流水线。
# 超长指令字（Very Long Instruction Word, VLIW）
通过编译器静态推测来辅助完成指令打包和冒险处理时，通常将一个周期内发射的多个指令预先组织为一条具有多个操作的长指令，这种将多条指令打包生成的指令称为超长指令字，执行这种超长指令字的处理器称为 VLIW 处理器。
# 超标量流水线（superscalar）
超标量流水线是指若干条指令（如整数运算、浮点运算、装入/存储等指令）同时启动并
<!-- page: 167 -->
独立进入流水线执行。即每个时钟周期发射多条指令，有多套取指部件和指令译码部件，并且同时有多条指令执行，所以应有多个执行部件。例如，定点处理部件、浮点处理部件、乘/除部件、取数/存数部件。超标量流水线是一种多指令发射（Multiple-instruction issue）方式。
## 动态流水线（dynamic pipelining）
动态流水线通过指令相关性检测和动态分支预测等手段，投机性地不按指令顺序执行，当发生流水线阻塞时，可以到后面找指令来执行。动态流水线的通用模型由以下主要单元组成：指令预取和分发单元、执行单元、提交单元。这种调整指令执行顺序的方式称为动态流水线调度（dynamic pipeline scheduling）。
## 指令预取（instruction prefetch）
指令预取是指在指令执行前，预先把指令取到CPU的指令缓冲器中。这样，在指令执行时，不需要再去取指令，可以很快地直接执行指令。流水线指令执行方式中通常采用指令预取方式。
## 指令分发（instruction dispatch）
指令分发是指对指令队列中的指令进行译码，根据译码结果将指令分派到相应的执行单元。用来进行指令译码和分发的部件称为分发单元。
## 静态多发射（static multiple issue）
静态多发射通过编译器静态推测来辅助完成指令打包和冒险处理。通常将一个周期内发射的多个指令预先组织为一条多个操作的长指令，称为一个“发射包”。静态多发射处理器主要考虑处理数据冒险和控制冒险。
## 动态多发射（dynamic multiple issue）
动态多发射通过在指令执行过程中由处理器硬件动态完成流水线调度来完成指令打包和冒险处理。目前的超标量处理器大多采用动态多发射流水线。
## 按序发射（in-order issue）
按序发射指按照程序中原来的指令顺序进行指令发射。
## 无序发射（out-of-order issue）
无序发射指不按程序中原来的顺序发射指令，把可能发生冒险的指令推后发射，而把后面无冒险的指令提前发射。
## 指令执行单元（instruction execute unit）
指令执行单元是用来对指令进行执行的功能部件。在动态流水线中，不同的指令被分派到不同的指令执行单元中。例如，整数运算单元、浮点运算单元、存数单元、取数单元等。
## 存储站（reservation station）
在动态调度流水线中，每个执行单元都有自己的缓存，用来保存当前执行的指令、操作数和结果等，这个缓存称为存储站。
## 乱序执行（out-of-order execution）
在不同的指令执行单元中有很多指令同时被执行，而且每种指令所用的执行时间也不一样，所以，无法按照程序中原来的顺序执行指令，因此，动态流水线中的指令一定是乱序执行的。
<!-- page: 168 -->
重排序缓冲(reorder buffer)
因为指令执行是无序的，所以，需要对执行后的指令重新排序，在指令最后提交前先要将其存放在重排序缓冲中。
指令提交单元(instruction commit unit)
指令提交单元将指令执行的结果写到结果寄存器或存储单元中以完成指令最后一步操作。指令提交单元在重排序缓冲中保存所有挂起的指令，根据分支功能单元执行的结果确定预测是否成功，从而确定哪些指令需从重排序缓冲中清除，哪些指令可以写结果以提交。
按序完成(in-order completion)
按序完成是指按照程序中原来的指令顺序完成指令的执行。
无序完成(out-of-order completion)
无序完成是指不按照程序中原来的指令顺序完成指令的执行。
按序发射、按序完成
按序发射、按序完成是指按照程序中原来的指令顺序预取、译码和分发，也按原来的指令顺序完成指令的执行。
按序发射、无序完成
按序发射、无序完成是指按照程序中原来的指令顺序预取、译码和分发，但不按原来的指令顺序完成指令的执行。
无序发射、按序完成
无序发射、按序完成是指不按照程序中原来的指令顺序预取、译码和分发，但按原来的指令顺序完成指令的执行。
无序发射、无序完成
无序发射、无序完成是指不按照程序中原来的指令顺序预取、译码和分发，也不按原来的指令顺序完成指令的执行。
写后读(RAW)相关
若前一条指令对某寄存器单元写入，后一条指令需要从同一个寄存器读出，则称这两条指令是写后读相关的。
写后写(WAW)相关
若前一条指令和后一条指令都需要对同一个寄存器进行写入，则称这两条指令是写后写相关的。这种相关性，在无序发射或乱序执行时可能会发生数据冒险；而在按序发射和完成时，不会发生数据冒险。
6.4 常见问题解答
1. 什么样的指令格式更适合流水线方式？
答：定长指令字和定长操作码使得每条指令的预取及译码操作时间完全一致，便于流水线控制；指令类型少、操作数地址规整，便于规划取操作数步骤，并使得对指令进行译码的同时，可以读取寄存器操作数；采用 Load/Store 型指令格式，便于利用执行运算步骤来进行地址计算。上述这些都是 RISC 指令系统的特点，由此可知，RISC 指令设计风格更适合流水线方式。
<!-- page: 169 -->
2. 采用流水线方式能使一条指令的执行时间更短吗？
答：不能。采用流水线方式使得指令吞吐率提高了，即在给定的时间内完成指令执行的条数增加了，但每条指令的执行过程没有减少，因此不会缩短一条指令的执行时间，相反，流水线方式还会延长一条指令的执行时间。
3. 为什么流水线方式会延长一条指令的执行时间？
答：因为在确定一条流水线的流水段个数时，是以最复杂指令执行过程所需的流水段个数为标准设计的；在确定每个流水段的宽度时，也以最复杂流水段所需的宽度来设计。因而，所有指令都需要花费最慢指令所需的执行时间才能完成执行。此外，每个流水段之间要有信息的缓存和传递等，这也增加了额外的执行时间开销。
4. 二阶段流水线能成倍提高指令执行效率吗？
答：不能。二阶段流水线把一个指令周期分成取指令和执行指令两个阶段，是最简单的流水线，它不能成倍提高指令执行效率。有很多原因，主要原因：①因为每条指令的执行阶段所花时间不同，流水线要求以最慢指令为标准来设计，所以，执行阶段时间可能会很长；②虽然每条指令的取指令过程可能一样，但是流水线中要求每个流水段的时间相同，所以，取指令阶段时间也要和最慢指令的执行时间一样；③流水段寄存器的读写会增加一定的延迟；④各种流水线冒险会破坏流水线，造成流水线的停顿、影响指令的执行效率。
5. 加倍流水线的阶段数能成倍提高指令执行效率吗？
答：不能。一般来说，加倍流水线的阶段数会提高指令的执行效率，但是不能按比例成倍提高。其主要原因是因为增加流水段，使得流水段之间的流水线寄存器的开销增加了。例如，假定一个三阶段流水线的每一级流水段中组合逻辑延时为 100ps，流水段寄存器延时为 20ps，则时钟周期至少为 $100 + 20 = 120\mathrm{ps}$，吞吐率为 $1 / 120\mathrm{ps}\approx 8.33\mathrm{GOPS}$（每秒千兆次操作），指令延时至少为 $3\times 120 = 360\mathrm{ps}$；如果流水段数成倍增加到6段，则每个流水段的组合逻辑延时变为 50ps，故时钟周期变为 $50 + 20 = 70\mathrm{ps}$，吞吐率为 $1 / 70\mathrm{ps}\approx 14.29\mathrm{GOPS}$，指令延时为 $6\times 70 = 420\mathrm{ps}$。所以，性能只提高到大约 $14.29 / 8.33\approx 1.71$ 倍，而不是两倍，指令延时增加了 $420 - 360 = 60\mathrm{ps}$，这主要是流水段寄存器增加的延时。
6. 流水线深度越深，时钟频率就越高，对吗？
答：一般来说，在指令执行时间一定的情况下，流水线深度越深，时钟频率就越高。增加流水段个数，使得每个流水段内的操作变得非常简单，因而，每个阶段的延时就很小，也就缩短了时钟周期，提高了时钟频率。但是，流水线深度不能无限制提高，随着流水段个数的增加，流水段之间的流水段寄存器增多，加大了流水段之间缓冲的额外开销，当额外开销的比例达到 $50\%$ 时，再增加流水线的深度就没有意义了。此外，用于流水线优化和存储器（或寄存器）冲突处理的控制逻辑将随流水线深度的加深而大量增多，可能导致用于流水段之间控制的逻辑比流水段本身的控制逻辑更复杂。
7. 流水线方式下，如何确定流水段的个数？
答：流水线方式下，一条指令的执行过程被分成了若干操作子过程。由于每条指令所完成的功能不同，所包含的操作过程就不同。有的指令要求完成寄存器之间内容的传送；有的指令就是简单的加/减运算；还有的指令是复杂的乘/除运算。这些操作所花的时间相差很大，因此，这些指令如果都在同一个流水线中执行，就必须按最复杂的指令来设计流水线的流水段个数。现代计算机一般把复杂度相近的指令用同一条流水线完成，而把复杂度相
<!-- page: 170 -->
差很大的指令安排在不同的流水线中。
8. 流水线方式执行指令时，总能在一个时钟周期内完成一条指令的执行吗？
答：不能。理想情况下，经过若干周期后，能在每个时钟周期内执行完一条指令，即 $\mathrm{CPI} = 1$ 。但是，当程序中出现以下情况时，流水线被破坏，因而不能达到 $\mathrm{CPI} = 1$ 。①当有多条指令的不同阶段都要用到同一个功能部件时，发生资源冲突，后面指令要延时执行；②当程序的执行流程发生改变时，发生控制相关，原来按顺序取出的指令无效；③当后面指令的操作数是前面指令的运行结果时，发生数据相关，后面指令要延时执行。此外，还有 cache 缺失、TLB 缺失、异常和中断等的发生都会阻塞流水线的执行。
9. 如何解决结构冒险？
答：通过以下两种规整流水线结构的方式可以解决部分结构冒险：①规定每个功能部件在每条指令执行过程中只能被使用一次，例如每条指令只能用一次“寄存器写口”；②每个功能部件只能在一个特定的流水段内被使用，例如“寄存器写口”只能在第五个流水阶段被使用。
另外，指令和数据分别存放在不同的存储器中，使得同时访问指令和数据不会引起存储器资源的结构冒险。这在大多数处理器中都是这样的，因为在L1 cache的data cache和code cache是分开的。
10. 什么是控制冒险？哪些情况下会发生控制冒险？
答：正常情况下，PC的值按顺序增量；但在执行跳转类指令或发生异常和中断时，PC的值由指令或异常/中断处理部件给出。流水线方式下，如果在取下一条指令时，正确的下条指令地址还没有送到PC中，那么所取的下条指令就不是正确的，因而发生控制冒险。可以看出，如果确定下条指令地址所用时间较长，就会因为来不及在一个时钟周期内得到正确的PC值而发生控制冒险。通常，跳转类指令会发生控制冒险。例如，分支指令（条件跳转指令）要根据条件测试结果来确定PC的值，因而会发生控制冒险；返回指令需要从存储器中读取返回地址送PC，因而也会发生控制冒险。
11. 无条件跳转（如跳转指令、调用指令等）是否可以避免发生控制冒险？
答：可能会发生控制冒险。如果不是把取指令操作和译码操作合成一个阶段，那么就会引起控制冒险。因为要等到译码阶段才知道是跳转指令，而此时流水线中正在取下一条顺序执行的指令，即使译码阶段能够得到跳转目标地址，已经有一条不该执行的指令在流水线中，即流水线被阻塞了一个时钟周期。在下一个时钟到达时，应把已经取出的下一条指令清0，并把跳转目标地址送PC，重新从跳转目标地址处取指令执行。
12. 流水线中如何控制在同一时钟内各流水段中执行不同的指令？
答：对于每条指令来说，流水线中前面的取指令流水段和指令译码流水段，都是一样的。所以这两个流水段中的操作没有必要和哪个指令对应。但是，指令译码以后，每个流水段中执行的动作一定要和特定的指令对应。也就是说，特定指令对应的控制信号一定要送到对应的流水段中，以控制该流水段中的执行部件完成正确的动作。这样也就可以控制在同一时钟内各流水段执行不同的指令。要做到特定指令对应的控制信号送到对应的流水段中，只要将译码阶段得到的控制信号也以流水线的方式传送，每来一个时钟，控制信号就往后面一个流水段传送一次，这样使得控制信号和所控制的操作同步。
<!-- page: 171 -->
13. 指令译码前控制信号还没有产生，那么如何控制译码前指令的动作呢？
答：任何指令总是先要取指令，然后对指令译码，根据指令的不同产生不同的控制信号控制数据通路完成不同的指令功能。也就是说，在指令译码前控制信号还没有产生，所以，不可能有控制信号来控制译码前指令的动作。
对所有指令来说，取指令和指令译码两个阶段的动作都是一致的，只要让这两个阶段的功能部件完成特定的功能就行了，而无须区分是哪条指令对应的功能，因而也就不需要控制信号对其进行控制。