4 MIPS流水线及指令级并行技术

2022-12-01
33 分钟前

第4章 MIPS流水线及指令级并行技术

  1. 流水线的概念、分类
  2. 流水线的时空图及性能指标计算
  3. add, sub, addi, subi, lw, sw, beq每条指令在5级流水线的执行过程
  4. 结构冒险、数据冒险和控制冒险的判断，以及需要暂停的时钟周期数的判断（控制冒险的解决性能依赖于分支地址计算阶段和分支条件判断阶段）
  5. 结构冒险、数据冒险和控制冒险的解决办法
  6. 流水线中处理中断和异常的方法
  7. 记分牌/Tomasulo动态调度算法

4.1 流水线概述

4.1.1 流水线的概念

流水线定义

流水线是利用执行指令操作之间的并行性，实现多条指令重叠执行的技术（在前一条指令执行完毕之前开始执行本条指令）。当今，流水线是实现更快CPU的基本和关键技术。不仅是实现CPU，12级流水线用于几何变换的GPU中。

流水线术语

  • 机器周期（流水线周期）：指令沿流水线移动一个流水段的时间。长度取决于最慢的流水段，一般是一个时钟周期（有时是两个时钟周期）。每个流水线周期从指令流水线流出一条指令。
  • 吞吐量：单位时间从流水线流出的指令数。
  • 流水段（级）：完成一条指令的一部分操作

流水线结构

一个流水线有多个段（级），段间有流水线寄存器。

每个流水段执行指令或操作的不同部分。

流水段之间采用同步时钟控制。

一条指令或操作从流水线一端进入，经过各段，从另一端流出。

流水线是开发串行指令流中并行性的一种实现技术。

image-20221130154723367

重叠方式需要解决的问题

问题1：为了实现取指、分析指令、执行指令同时进行，需要有对应的独立部件。需暂存中间结果。

问题2：尽量缩短各个功能部件的运行速度，使得大致相等，避免在重叠中相互等待。

问题3：主存访问冲突。例如，取指令k+1时需访存，分析指令k时可能也需要取操作数访存。

解决访存冲突，主要有3种解决办法：

  • 将主存分为两个独立编址的存储器：指令存储器和数据存储器，CPU可分别独立访问。
  • 低位交叉存取方式：可并行访问不在同一个存储体中的指令或数据。
  • 指令预取：在重叠操作中，当前一条指令在执行过程中就需要提前取出后面的指令进行相应处理，这种提前取出后继指令进行相应处理，称为先行（预取）。

4.1.2 流水线的分类

流水线可按不同的观点进行分类，一般来说流水线可以分为以下几个类型。

1.按各过程段用时是否相等分类

流水线按各过程段用时是否相等可分为均匀流水线和非均匀流水线两种。

1）均匀流水线指的是各过程段用时全相等的流水线

2）非均匀流水线指的是各过程段用时不全相等的流水线

2.按处理的数据类型

按处理的数据类型可分为标量流水处理机和向量流水处理机两种。

1）标量流水线：用于对标量数据进行流水处理。如：IBM 360/91，AmDahl 470V/6

2）向量流水线：用于对向量数据进行流水处理。（向量很适合流水处理），如：STAR-100，CYBER-205，CRAY-1.

3.按流水线的规模

按流水线的规模可分为操作流水线、指令流水线和宏流水线。

1）操作流水线是把处理机的算术逻辑部件分段，使得各种数据类型的操作能够进行流水，规模最小。

2）指令流水线则是把执行指令的过程按照流水方式处理。

3）宏流水线它是指由两个以上的处理机串行地对同一数据流进行处理，每个处理机完成一项任务。

4.按功能分类

按流水线完成的功能是否单一，流水线可分为单功能流水线与多功能流水线两种。

1）单功能流水线：只能完成一种固定功能的流水线。例如，浮点加法器流水线专门完成浮点加法运算，浮点乘法器流水线专门完成浮点乘法运算。

2）多功能流水线：流水线的各段可以进行不同的连接，以实现不同的功能。
例： ASC的多功能流水线

image-20221130155323616

5.按工作方式分类

流水线按工作方式可分为静态流水线和动态流水线两种。

1）静态流水线：在同一时间内，多功能流水线中的各段只能按同一种功能的连接方式工作。
对于静态流水线来说，只有当输入的是一串相同的运算任务时，流水的效率才能得到充分的发挥。

2）动态流水线：在同一时间内，多功能流水线中的各段可以按照不同的方式连接，同时执行多种功能。
优点：灵活，能够提高流水线各段的使用率，从而提高处理速度。
缺点：控制复杂。

image-20221130155337394

6.按连接方式分类

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

1）线性流水线：流水线的各段串行连接，没有反馈回路。数据通过流水线中的各段时，每一个段最多只流过一次。

2）非线性流水线：流水线中除了有串行的连接外，还有反馈回路。

image-20221130155415879

7.其他分类

除上述几种外，流水线分类还有下述几种。

1）根据控制方式分成顺序流水线和乱序流水线。

2）在线性流水线中，根据控制方式还可以分成同步流水线和异步流水线。

4.1.3 流水线的特点

  1. 流水线处理的最好是连续任务，只有连续不断的任务才能充分发挥流水线的效率。
  2. 流水线依靠多个功能部件并行工作宋缩短程序的执行时间，实际上是把一个大的功能部件分解为多个子过程，如前述将浮点数加法器分解为4个子过程。
  3. 流水线中的每一功能部件后面都要有一个缓冲寄存器，即所谓的锁存器，以便平滑各个功能段延时时间的不一致。
  4. 流水线中各段时间应尽量相等，避免段延时过长引起的相互等待。
  5. 流水线需要有“装入时间”和“排空时间”。

4.2 流水线的时空图及性能分析

4.2.1 时空图

时空图从时间和空间两个方面描述了流水线的工作过程。

时空图中，横坐标代表时间，纵坐标代表流水线的各个段。

4段指令流水线的时空图：

image-20221130155534791

4.2.2 吞吐率

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

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

nn：任务数

TkT_k：处理完成 nn 个任务所用的时间

各段时间均相等的流水线

各段时间均相等的流水线时空图（假设一条 kk 段线性流水线）：

image-20221130213817248

流水线完成 n 个连续任务所需要的总时间为

Tk=kΔt+(n−1)Δt=(k+n−1)ΔtT_k=k\Delta t+(n-1)\Delta t=(k+n-1)\Delta t

流水线的实际吞吐率

TP=n(k+n−1)ΔtTP = \frac{n}{(k+n-1)\Delta t}

最大吞吐率

TPmax⁡=lim⁡n→∞n(k+n−1)Δt=1ΔtTP_{\max} = \lim_{n\to\infty} \frac{n}{(k+n-1)\Delta t} = \frac{1}{\Delta t}

最大吞吐率与实际吞吐率的关系

TP=nk+n−1TPmax⁡TP = \frac{n}{k+n-1}TP_{\max}

流水线的实际吞吐率小于最大吞吐率，它除了与每个段的时间有关外，还与流水线的段数k以及输入到流水线中的任务数 nn 有关。

只有当 n≫kn\gg k 时，才有 TP≈TPmax⁡TP \approx TP_{\max}。

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

一个各段时间不等的流水线：

  • 一条4段的流水线
  • S1，S3，S4各段的时间：Δt0\Delta t_0
  • S2的时间：3Δt03 \Delta t_0 （瓶颈段）
image-20221130214157295

时空图：

image-20221130214201126

流水线中这种时间最长的段称为流水线的瓶颈段。

各段时间不等的流水线的实际吞吐率（ Δti\Delta t_i 为第 ii 段的时间，共有 kk 个段 ）：

TP=n∑i=1kΔti+(n−1)max⁡(Δt1,Δt2,⋯ ,Δtk)TP = \frac{n} {\sum^k_{i=1} \Delta t_i + (n-1) \max(\Delta t_1,\Delta t_2, \cdots, \Delta t_k) }

流水线的最大吞吐率为

TPmax⁡=1max⁡(Δt1,Δt2,⋯ ,Δtk)TP_{\max} = \frac {1} { \max(\Delta t_1,\Delta t_2, \cdots, \Delta t_k) }

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

1.细分瓶颈段

例如：对前面的4段流水线，把瓶颈段S3细分为3个子流水线段：S3a，S3b，S3c

image-20221130214240755

改进后的流水线的吞吐率：TPmax⁡=1ΔtTP_{\max} = \frac{1}{\Delta t}

2.重复设置瓶颈段

缺点：控制逻辑比较复杂，所需的硬件增加了。

例如：对前面的4段流水线，重复设置瓶颈段S3：S3a，S3b，S3c

image-20221130214324111

重复设置瓶颈段后的时空图

image-20221130214339809

4.2.3 加速比

流水线的加速比

流水线的加速比（Speedup）是完成某个任务顺序执行所用时间与流水线执行所用时间之比。

假设：不使用流水线（即顺序执行）所用的时间为 TsT_s，使用流水线后所用的时间为 TkT_k ，则该流水线的加速比为

S=TsTkS=\frac{T_s}{T_k}

【例题】考虑一个非流水线机器。假设时钟周期是 1ns，ALU操作和转移操作需要4个时钟周期，存储器需要5个时钟周期。以上操作的比例相应为40%，20%和40%。若改为流水化，时钟周期需增加0.2ns，那么该流水线的加速比为多少？

解：

非流水线：指令的平均执行时间=时钟周期*平均CPI
=1ns * ((40%+20%)*4 + 40%*5)
=1ns * 4.4 =4.4 ns

流水线： 时钟周期变慢为1.2ns，流水线CPI=1。1.2*1=1.2ns就是指令的平均执行时间。

流水线加速比 = 非流水线指令的平均执行时间/流水线指令的平均执行时间 = 4.4ns/1.2ns = 3.7

1、流水线各段时间相等时（都是 Δt\Delta t）
一条 kk 段流水线完成 nn 个连续任务所需要的时间：Tk=(k+n−1)ΔtT_k = (k+n-1)\Delta t
顺序执行n个任务所需要的时间： Ts=nkΔtT_s = nk \Delta t
流水线的实际加速比为：S=nkk+n−1S=\frac{nk}{k+n-1}
最大加速比：Smax⁡=lim⁡n→∞nkk+n−1=kS_{\max} = \lim_{n \to \infty} \frac{nk}{k+n-1} = k

2、流水线的各段时间不完全相等时，一条 kk 段流水线完成 nn 个连续任务的实际加速比为：

S=n∑i=1kΔti∑i=1kΔti+(n−1)max⁡(Δt1,Δt2,⋯ ,Δtk)S = \frac {n \sum^k_{i=1} \Delta t_i} {\sum^k_{i=1} \Delta t_i + (n-1) \max(\Delta t_1,\Delta t_2, \cdots, \Delta t_k)}

理想情况的加速比

流水线处理器的理想CPI差不多总是1。 (may less than or greater that)

因此：
流水线CPI
= 理想CPI + 每条指令的平均停顿周期数
= 1 + 每条指令的平均停顿周期数

忽略流水线时钟周期的额外开销。停顿会降低流水线的性能，使其性能比理想的差。

image-20221130220540503

理想情况下，非流水线和流水线的时钟周期可以相等。

image-20221130220649996

流水线没有停顿时，加速比等于流水线段数。

4.2.4 效率

流水线效率（Efficiency，E）是指流水线的设备利用率。

在时空图上，流水线的效率定义为 nn 个任务占用的时空区与 kk 个功能段总的时空区之比，因此流水线的效率包含时间和空间两个方面的因素。

实际上，nn 个任务占用的时空区就是顺序执行 nn 个任务的总的时间 T0T_0；而用一条 kk 段流水线完成 nn 个任务的总的时空区为 k×Tkk \times T_k ，其中 TkT_k 是流水线完成 nn 个任务所使用的总时间，则一条 kk 段流水线的效率为：

E=n个任务占用的时空区k个流水段的总时空区=T0kTkE = \frac{n个任务占用的时空区}{k个流水段的总时空区} = \frac{T_0}{k T_k}

各段时间均相等的流水线时空图：

image-20221130214815205

如果每个流水段时间是 Δt\Delta t，且任务是连续的实际效率：

E=k×n×Δtk×(k+n−1)Δt=nk+n−1E=\frac{k \times n \times \Delta t}{k \times (k+n-1)\Delta t}=\frac{n}{k+n-1}

其中，k=4k=4。

最大效率：

Emax⁡=lim⁡n→∞nk+n−1=1E_{\max}=\lim_{n\to\infty} \frac{n}{k+n-1} = 1

例

假设加法由5个流水线实现，计算：S=a0+a1+a2+a3+a4+a5+a6+a7。

解：

对相关算式要合理分解算式（尽量分解为少相关算式）：

① S0=a0+a1 ② S1=a2+a3 ③ S2=a4+a5 ④ S3=a6+a7
⑤ S4=S0+S1 ⑥S5=S2+S3
⑦ S6=S4+S5

image-20221130214942265

吞吐率：

TP=718ΔtTP=\frac{7}{18\Delta t}

效率：

E=作用区域面积完成运算所需时间矩形面积=75Δt18Δt×5=718\begin{aligned} E&=\frac{作用区域面积}{完成运算所需时间矩形面积}\\ &=\frac{75\Delta t}{18 \Delta t \times 5}\\ &=\frac{7}{18} \end{aligned}

例

由静态多功能流水线实现如下计算：

A∗B=∑i=14ai⋅biA * B = \sum^4_{i=1} a_i \cdot b_i

image-20221130215102790

1—2—3—5 做加法
1—4—5 做乘法

解：分解算式

①S1=a1.b1 ②s2=a2.b2 ③s3=a3.b3 ④s4=a4.b4
⑤s5=s1+s2 ⑥s6=s3+s4
⑦s7=s5+s6

image-20221130215210181

在上例中，将“静态”多功能流水线改为“动态”多功能流水线，又该如何分解？可以同时做加法和乘法

例（第二次课堂练习）

由静态多功能流水线实现如下计算（a1∗b1+a2∗b2+a3∗b3+a4∗b4a_1*b_1+ a_2*b_2+ a_3*b_3+ a_4*b_4），其中乘法使用1-2-3-5级流水线，加法使用1-2-4级流水线，请进行时空图分析题，并计算吞吐率和效率。

image-20230228134102129

4.2.5 其他注意事项

流水线段数不能太多

有些操作不能分为更细的逻辑实现

流水线锁存器不是免费的，要占据面积，且有延迟。
机器周期> 锁存器延迟+ 时钟偏移

太多的段数:

  • 非常复杂

  • 处理正在执行指令之间的控制逻辑很大

平衡每个流水段的时间

流水线设计者：平衡每个流水段的时间，使之等长。
因此，每条指令在流水线的平均执行时间在理想情况下为：非流水线机器1条指令的平均执行时间 / 流水线机器段数

理想情况：流水线的加速比等于流水线机器的段数。
流水线减少了指令执行的平均时间（减少了CPI或时钟周期）
流水线技术（硬件实现）对编程者透明

太多的段数：

  • 非常复杂
  • 处理正在执行指令之间的相关控制逻辑很大
  • 简单指令执行时间过长

4.3 经典5段流水线RISC处理器

4.3.1 RISC指令系统

RISC指令系统特点

RISC系统结构有以下几个关键特点：

  • 所有参加运算的数据来自寄存器，结果也写入寄存器。寄存器为32/64位。
  • 访存只有load和store指令
  • 指令的数量较少，所有指令长度相同。
  • 不同指令执行的时钟周期数差别不大

这种结构可以有效地简化流水线的实现。

MIPS系统是默认的RISC系统结构。

RISC指令的5个周期

image-20221130215740618

IF: Instruction fetch cycle 取指

  • 按照 PC 内容访问指令存储器，取出指令

  • PC+4→NPC，以获取下一条指令地址

ID: Instruction decode / register fetch cycle 译码

  • 指令译码
  • 读寄存器
  • 如果需要，符号扩展指令中的位移量

EX: Execution / effective address cycle 执行

  • Load/Store: 计算数据存储器有效地址
  • R-R / R-I ALU执行运算操作
  • Branch: 做 “=0?” 测试，并置条件，计算目标地址

MEM: Memory access 访存

  • Load: 送有效地址到数据存储器，取数据

  • Store: 写ID读出数据到有效地址单元中

  • Branch: 如果条件满足计算目标地址送PC；否则NPC送PC

WB: Write-back cycle 写回

  • Load or ALU: 写结果到寄存器堆

4.3.2 RISC指令流水线

流水线 (pipeline) 是一种能够使多条指令重叠操作的处理机的实现技术，它已成为现代处理及设计中最为关键的技术。流水线模型机最理想的执行情况是：每个时钟周期开始一条指令、结束一条指令的满负荷运行状态。

单周期处理器的5阶段划分

  1. IF (instruction fetch) 取指令；
  2. ID (instructiondecode) 指令译码并读寄存器操作数；
  3. EXE (execution) 执行；
  4. MEM (memory access) 存储器访问；
  5. WB (write back) 写回。

image-20221130231821523

5 个段构成了一个指令流水线，一条指令经过每个段。

CPI 减少到 1，因为平均每个时钟周期发射或完成一条指令。

在任意时钟周期，在每个流水段正执行一条指令的部分。

理想情况下，性能增加了5倍!

流水线时序图

image-20221130220107550

4.3.3 流水线寄存器的引入

在单周期处理机中，如果一条指令还没有执行完毕，PC的内容不会改变。这就使得在一条指令的整个执行过程中，IM始终输出当前指令。

与单周期处理机不同，流水线处理机每个时钟周期都要取出一条指令。这意味着，当流水线处理机已从存储器取出一条指令并把它送到ID级去译码时，下一条指令也正在从存储器中取出。如果先取出的指令没被保存，则它后面正在被取出的指令会对它造成影响。也就是说，我们必须要使用寄存器来保存从存储器取出的指令。

推而广之，我们必须要在流水线的各级之间安排一组寄存器(中间寄存器、暂存器)，用以保存当前时钟周期运算出的结果，以便为下个周期使用。（我们只能使用触发器寄存器，它把时钟上升沿时数据输入端的信息打人寄存器中；而不能使用锁存器，因为锁存器的输出在时钟高电平时跟随输入的变化而变化。）我们称这些寄存器为流水线寄存器。

由此，我们构想流水线处理机应有如下的结构：

image-20221201004447246

把PC作为一个特殊的流水线寄存器来看待，因为在非流水线处理机中PC也是需要的。由于流水线处理机每个时钟周期都从指令存储器取出一条指令，它的值在每次周期结束时都将被改变。

IF/ID

IF/ID流水线寄存器中必须包括一个指令寄存器IR。

在IF/ID中，我们使用了一个被称为IR(Instruction Register)的指令寄存器。对于字长为32位的处理机来讲，PC一般有30位，它存放的是32位指令的字地址。IR有32位，用来存放一条指令。

image-20221201004538108

ID/EXE

ID/EXE中需保存：

  • 从寄存器堆中读出的两个32位数据必须要保存。
  • 经符号扩展后的32位立即数I也要保存。
  • 继续保存PC+4。

image-20221201004615962

EX/MEM

EX/MEM中需保存：

  • PC+4+偏移量的值。
  • ALU的计算结果。
  • ZERO标志位的值。
  • 要写入存储器中的数据

image-20221201004657434

MEM/WB

MEM/WB中需保存：

  • ALU的计算结果。
  • 从存储器中读出的数据

image-20221201004716296

4.3.4 流水线的数据通路

流水线的数据通路

【例】lw指令在通过5级流水线的数据通路的活动部分：

IF

image-20221201153248735

ID

image-20221201153251988

EXimage-20221201153343242
MEM

image-20221201153259660

WB

image-20221201153319316

流水线寄存器的值

考点：求每级的寄存器的值

看右边执行的指令

每级都需保存rd的值

观察：不同级的d寄存器（rd）的值分别是多少？等于右边的值

image-20221201005102698

流水线的时序图

image-20221201005117282

流水线的控制通路

数据通路、控制信号和单周期类似

image-20221201005208451

控制信号：

信号名 为0 为1
RegDst 写入寄存器的目标号来自rt 写入寄存器的目标号来自rd
RegWrite 无效 寄存器堆的写使能
ALUSrc 第二个ALU操作数来自寄存器堆 第二个ALU操作数来自立即数
PCSrc PC=PC+4 PC被分支地址替代
MemRead 无效 允许存储器读
MemWrite 无效 允许存储器写
M2Reg 选择ALU的结果到寄存器堆 选择储存器的结果到寄存器堆

在ID级创建控制信号，然后逐级传递

image-20221201005410357

image-20221201005417690

4.4 流水线中的冒险问题

4.4.1 流水线冒险概述

什么是流水线冒险

如果要执行算式 S=a/b+c，要通过下列指令来执行。

1：lw  $t1, 0($s1);		a
2：lw  $t2, 0($s2);		b
3：lw  $t3, 0($s3);		c
4：div $t4, $t1, $t2;	a/b
5：add $t4, $t4, $t3;	要等div结果 a/b+c
6：sw  $t4, 0($s4);		存结果

第4条指令需要第1条和第2条指令的结果才能执行；第5条指令需要第3条和第4条指令的结果才能执行。这就出现了指令因等待前面结果，使后面没指令无法继续执行下去的现象，即冒险。

流水线冒险的类型

流水线中的冒险主要分为以下3种类型：

  • 结构冒险
  • 数据冒险
  • 控制冒险

冒险总是可以用停顿解决

解决冒险最简单的方式就是停顿流水线。停顿意味着为某些指令暂停流水线一个或多个时钟周期。

  • 一条指令被停顿后，其后的所有指令被停顿；该指令之前的指令必须继续执行。
  • 一个流水线停顿也称为流水线气泡或气泡。
  • 停顿时，没有任何新的指令被取到流水线。

4.4.2 结构冒险

如果某些指令组合在流水线中重叠执行时产生了资源冲突，那么我们称该流水线有结构冒险。

例如：由于访问同一个存储器而引起的结构冲突：

image-20221130220932072

解决办法 1： 插入暂停周期

即让流水线在完成前一条指令对数据的存储器访问时，暂停取后一条指令（指令存储器）的操作。

image-20221130221105656

解决方法 2：相互独立的存储器

设置相互独立的指令存储器和数据存储器或设置相互独立的指令Cache和数据Cache。

image-20221130221121713

解决方法 3： 预取指令技术

在重叠操作中，当前一条指令在执行过程中就需要提前取出后面的指令进行相应处理，这种提前取出后继指令进行相应处理，称为先行（预取）。

4.4.3 数据冒险

数据冒险的定义

如果下面的条件之一成立，则指令j与指令i数据冒险：

  • （1）指令j使用指令i产生的结果；
  • （2）指令j与指令k数据冒险，指令k与指令i数据冒险，则指令j与指令i数据冒险。

第2个条件指出，如果两条指令之间存在类似上述的传递关系，则它们之间也存在冒险的。这条相关链甚至可以贯穿整个程序。

基本结构：一条指令想要使用还没有“完成”的数据值。

  • “完成” 表示 “数据值已经被计算了” 和“ 值已经被放好，正常情况可以在流水线硬件中找到它”。

数据冒险原因：习惯上总是假定采用纯串行指令执行模型（对于k >= 1 ，指令N在指令N+1之前完成），在相邻指令之间有依赖存在。

结论：数据冒险——指令想要的数据值还没有完成，或者值没有在正确的地方。

例子：

image-20221130221547783

冒险有3个方面的意思：

  • 存在风险的可能性；
  • 结果的正确计算顺序；
  • 多少并行性的上界。

解决数据冒险

解决数据冒险的一般方式：

  1. 保持冒险，但要避免风险；(调度代码技术)
  2. 消除冒险，通过变化(transform)代码。

由于数据可以在寄存器和存储器之间流动。当数据在寄存器中出现时，检测相关很容易，因为寄存器名字在指令中是固定的。对于存储器之间的数据相关的检测会更难，因为多个看起来不同地址可能指的是同一个地址，例如100($s4)和20($s6)可能是相同的地址，而随着指令的执行，前一个20($s4)和后一个20($s6)可能就不同了。

解决数据冒险的一般技术：

  • 暂停流水线；
  • 使用相关专用数据通路；
  • 编译优化调度（静态调度）；
  • 动态调度。

4.4.4 数据冒险的解决

image-20221201005537280

2号寄存器的值是否是正确的值？

只有最后一条指令正确

办法一：WB提前半个周期

最后2条指令正确

image-20221201005610026

办法二：在EX级增加转发/前推通路

后4条指令都正确

image-20221201153909327

检测冒险的条件以及控制信号的选择

（1）EX冒险（上图绿色的线）当前指令的 rs 或 rt 为上一条指令的结果

if (EX/MEM.RegWrite and (EX/MEM.Rd = ID/EX.Rs)) 
    ForwardA = 10;
if (EX/MEM.RegWrite and (EX/MEM.Rd = ID/EX.Rt))
    ForwardB = 10;

（2）MEM冒险（上图蓝色的线）当前指令的 rs 或 rt 为上上条指令的结果

if (MEM/WB.RegWrite and (MEM/WB.Rd = ID/EX.Rs))
    ForwardA = 01;
if (MEM/WB.RegWrite and (MEM/WB.Rd = ID/EX.Rt))
    ForwardB = 01;
转发/前推通路的时序图

image-20221201154001775

对于第二条指令：AND

上一条指令SUB的EX级结束（MEM级开始）就把$2的计算结果给下一条指令的EX，下一条指令AND能够得到正确的$2

image-20221201154036485

对于第三条指令：OR

第二条指令SUB的MEM级结束（WB级开始）把$2的计算结果给第三条指令的EX级，第三条指令OR能够得到正确的$2

image-20221201154303450

办法三：暂停流水线

通过内部前推技术，是否能够解决以下指令序列的流水线暂停?

lw    $1, 200($2);
add   $3, $1, $4;

不能，因为 lw 指令不能在 EX 级给出结果，而是在 MEM 级之后才能的得到结果

只能暂停流水线。

暂停流水线的时序图

image-20221201154949691

暂停流水线的检测

检测lw数据冒险的检测条件：

当前指令的 rs 或 rt 为上一条指令的结果，而且上一条指令是读存储器指令

if (ID/EX.MemRead and 
   ((ID/EX.Rt = IF/ID.Rs) or (ID/EX.Rt = IF/ID.Rt)))
Stall the pipeline;
暂停流水线的方法

考点：画时序图，写出 stall，写出向下箭头

易错：这条指令有 2 个 ID 级（共 6 级），stall 在第一个 ID 级

暂停流水线的方法：

  • 保持 PC 寄存器不变
  • 保持 IF/ID 寄存器不变
  • ID/EX 寄存器清零 或者 关闭 ID 的写使能信号

这样本次 ID 级的指令无效，下一次 ID 级仍然会执行这条指令

image-20221201155033970

增加了暂停流水线的机制（封锁PC寄存器和IF/ID寄存器的更新）：

image-20221201155111617

例（第二次课堂练习）

假设该流水线还采用了写操作提前半个时钟周期技术。考虑下面指令序列，回答后面的问题。

lw   $3, 33($1);
or   $2, $9, $3;
add  $5, $3, $10;    
sub  $6, $5, $4

（1）请画出该指令序列的时序图并标记出前推。

image-20230228134342418

（2）当指令“lw $3, 33($1)”处于WB级时，请写出ALU左边上下两个多路选择器分别选择：00和10；当指令“sub $6, $5, $4”处于EX级， 请写出ALU左边上下两个多路选择器分别选择：10和00。

image-20230228134333702

4.4.5 控制冒险

控制冒险定义

控制冒险是指因为程序的执行方向可能被改变而引起的相关。可能改变程序执行方向的指令通常有无条件转移、条件转移、子程序调用、中断、异常等。

无条件转移指令在程序中的使用情况一般如下

k    …
k+1: j   L
k+2: add $s1, $s2, $s3 
     …        
     …
L:   sub

有条件转移指令的程序：

		addi $s1, $s1, NUM;
LOOP:	……
        ……
        ……
        addi $s1, $s1, -1;
        slt  $t1, $s1, $zero;
        beq  $t1, $zero, LOOP;    //>=0转移
        sub …

从相关的角度看，转移指令与后续指令之存在着一种冒险，使后续指令不能同时进入流水线执行，故称为控制冒险。

控制冒险会引起MIPS流水线的性能损失比数据冒险大得多。

  • 下一条指令PC要花时间计算
  • 对于条件转移，转移分析要花时间计算

控制冒险时流水线执行情况

image-20221130222046615

解决方法一：转移Stalls

转移指令后插入 Stalls，但会造成大的性能损失。

Problem:
程序中有30%的转移频率，理想CPI为1，假设每条转移指令需插入3个stalls，问插入stalls后的性能是多少？

Answer:
CPI = 1 + 30%*3＝1.9
这种方法得到的性能大约只有理想性能的一半。

解决方法二：分支预测

① 总是预测分支不发生

对于很多计算机来说，这种转移stalls方法代价太大，因此就产生了另外一种消除控制冒险的解决方法：总是预测分支不发生（即假设分支不发生，属于静态预测机制）（成功率在50%左右）

如果假设分支不发生（预测正确），则继续执行顺序的指令流。如果分支发生的话（预测错误），丢弃已经进入流水线的指令，按真实分支执行（流水线会阻塞）。

如果分支不发生的可能性是50%，同时丢弃指令的代价很小的话，那么这种优化方法可以将控制冒险代价减半。

② 改进分支预测技术

思考一：另一种稍好的方法是预测一些分支发生而预测另外一些分支不发生。即可以根据分支的方向来预测分支是否命中，向后转移的分支预测为选中，向前转移的分支预测为不选中。

这种分支预测的方法依赖于始终不变的行为，没有考虑特定分支指令的特点。错误率很难低于30%。

③ 动态分支预测技术

思考二： 动态硬件预测器与前面的方法截然不同，其预测取决于每一条指令的行为，并且在整个程序生命周期内可能改变分支的预测结果。

其实现方法是保存每次分支的历史记录，然后利用这个历史记录来预测。当历史记录的数量和类型足够多时，这种硬件预测分支方式能够达到90%的正确率。

动态分支预测技术：通过硬件技术，在程序执行时根据近期转移是否成功的历史记录来预测下一次转移的方向。提前对分支操作做出反应，减少或消除控制相关导致的流水线停顿。

动态分支预测技术：转移预测缓存（跳不跳转）

转移预测缓存，是一小块由转移指令低位地址索引的存储单元，用来记录转移指令在最近的一次执行中是否被选中。可能有几条转移指令都映射到了同一个预测缓存表项。

1 bit 预测

只记录一次历史转移信息状态转化图。

当每项为一位预测位时，记录该指令最近一次分支是否成功，每一条指令的“转移历史表”只需要一个二进制位，其状态图如下：

image-20221130222508031

每个圆圈表示一种状态，圆圈中的T或N表示最近一次执行这条转移指令时，实际转移成功或不成功的信息，这个信息就是“转移历史表”中所记录的内容。

带有箭头的线表示状态转换的方向，线旁边的T表示指令实际执行结果为转移成功，而N表示指令实际执行结果为转移不成功。

预测成功率一般为77-79%。

当采用只记录最近一次转移是否成功的历史信息时，“转移历史表”的修改方法很简单：

  • 假设表中原来记录的是T，
    • 如果本次转移成功，则表中的内容继续保存T；
    • 如果本次转移不成功，则表中的内容修改为N；
  • 假设表中原来记录的是N，
    • 如果本次转移成功，则表中的内容修改为T；
    • 如果本次转移不成功，则表中的内容继续保存N；

在执行条件转移指令时，

  • 如果表中记录的内容是T，则说明转移预测逻辑预测转移成功，并按照转移成功的方向取指令并分析指令；
  • 如果表中记录的内容是N，则按照转移不成功的方向继续取下一条指令并分析指令。

在转移条件实际形成后，

  • 如果与预测的转移方向相同，则预测正确，流水线没有任何“断流”损失；
  • 如果与预测方向不同，则要作废已经预取和分析的指令，并从另一个方向取指令和分析指令

【例子】设一条转移指令在每次执行过程中的实际转移序列如下：
T, T, T, N, T, T, N, T, N, N, T, N, N
采用1位动态预测时：

事件序列 T T T N T T N T N N T N N
预测器状态 T T T T T N T T N T N N T N
准确性 1 1 1 1 1 1

成功率为：6/13=46% 。

T, T, T, N, T, T, N, T, N, N, T, N, N

为了提高分支预测的准确率，后面采用2位预测位

2 bit 预测

记录两次历史转移信息状态转化图。

通常使用2bit预测法来弥补这个缺陷，在这种预测法中，仅当错误两次时才改变预测方向，图为2bit预测法的有限状态机。

image-20221130223358741

每个圆圈表示一种状态，圆圈中的上面一行表示最近两次执行这条转移指令时，实际成功与否的信息，这个信息就是“转移历史表”中所记录的内容。圆圈中的下面一行，表示在当前这种状态下，本次执行这条转移指令时预测的转移方向。

  • TT：两次转移都成功；
  • NT：最近一次转移成功，再前一次转移不成功；
  • TN：最近一次转移不成功，再前一次转移成功；
  • NN：最近两次转移都不成功；
  • t：本次预测转移成功；
  • n：本次预测转移不成功；
  • T：本次实际转移成功；
  • N：本次实际转移不成功。

一般预测成功率为78-89%

研究发现，2 bit 几乎与 n bit 预测方法的效果相同，因此大多数系统使用 2 bit 方法。

动态分支预测技术：转移目标缓存（跳转到哪）

如果转移指令知道下一条指令的地址，那么就可以将转移代价降为0。

把为转移的后继指令保存预测地址的转移预测Cache称为转移目标缓存或转移目标Cache。

image-20221130223745384

解决方法三：延迟转移

观察：在MIPS，无论转移是否发生，转移后续指令总是被取指。

image-20221130231215861

转移延迟槽 (branch delay slot)：转移指令后续的指令。

编译器将需要静态调整代码到这个 “slot” 中, 如果只放入 NOP 就浪费了。

延迟分支指令，顺序执行下一条指令，在一条指令延迟之后再开始执行分支。MIPS编译器会在延迟分支指令的后面紧跟着放一条不受该分支影响的指令。

只有当分支延迟较短时，延迟分支才有效，所以没有处理器使用超过一个时钟周期的延迟分支。对更长的分支延迟，一般都使用前面的硬件分支预测器（即控制冒险的解决方法二）。

延迟槽可以放入无关的运算指令
例如：在 beq 放一条与跳转无关的 add 指令

image-20221130231453890

对于循环，延迟槽可以放入下一次循环的指令
例如：在 bne 指令后面放一条 lw 指令

image-20221130231437903

延迟槽可以放入 store 指令
例如：在 bne 指令后面放一条 sw 指令

image-20221130231446512

控制冒险总结

控制冒险出现的频率比数据冒险要小得多，而且采用转发就能有效解决数据冒险，但没有有效的方法能够解决控制冒险，而且控制冒险比数据冒险会引起更大的性能损失。

通常，流水线越深，在时钟周期上转移损失越大。

CPI 更高的处理器，会付出更高的转移代价。

解决控制冒险的有效性取决于转移预测的准确性。

4.4.6 控制冒险的解决

缩短分支的延迟：分支决策提前

若分支决策在MEM阶段：

image-20230224193439875

如果转移成功，有3条指令需要清除。可否清除更少的指令？可以

是否转移和转移地址都是在MEM阶段才能确定？否

分支决策提前：将分支指令条件判断提前到ID级（分支预测错误的代价减小到1条指令）：

image-20230223155621788

分支决策提前的条件：

  1. 提前计算分支目标地址
    在ID级中已形成了PC值和地址偏移量，因此将分支地址计算从EX级前移到ID级即可。

  2. 提前判断分支条件
    需要在ID级判断两个寄存器的值是否相等。由于可能存在数据冒险，需要把数据转发至ID级进行相等检测。

提前判断分支条件可能需要暂停流水线。比如：

add $1, $3, $4
beq $1, $2, L1

需暂停1个时钟周期

lw   $1, 100($4)
beq  $1, $2, L1

需暂停2个时钟周期

分支预测错误的实例

BEQ进入ID级：

image-20221201155607063

BEQ进入EX级：

分支预测错误，IF.Flush 冲掉 IF/ID 寄存器。使得当前ID级的指令无效

image-20221201155630689

IF.Flush冲掉IF/ID寄存器的两种实现方式：

  • 指令编码变全0：流水线定义编码为全0的指令为nop指令（语义：什么工作都不做）。
    若IF.Flush有效，则将该指令在打入IF/ID寄存器时变为nop指令。
  • 指令编码不变，将该指令的所有写信号全部关闭。
image-20221201155836602

存在数据冒险的实例

假定流水线对分支不发生进行了优化，并且分支的执行提前到流水线的ID级。试说明下面的指令序列在分支发生时的执行情况：

（分支指令beq的前1条指令sub与分支指令有关于$1的数据冒险）

   sub $1,  $4, $8
   beq $1,  $3, 72
44 and $12, $2, $5
48 or  $13, $2, $6
52 and $14, $4, $2
56 slt $15, $6, $7
   .....
72 lw  $4,  50($7)

分支指令前一条刚好是ALU指令sub，而这条ALU指令sub的结果$1恰是分支指令beq比较时所需要的$1，那么需要产生阻塞。因为ALU指令sub的EX级（产生结果$1）将在分支指令beq的ID级后发生，即ID级进行分支比较所需的数据$1可能在sub执行EXE后面才能产生正确的$1，因此有可能会发生数据冒险，这样就需要阻塞流水线（可以通过关掉所有写信号来实现）。

阻塞流水线：关掉所有写信号（这些控制信号在每个周期都向前传递，但都不会产生效果）

image-20221201162215383

4.5 流水线中异常事件的处理

4.5.1 异常概述

异常（Exception）事件是指在程序执行过程中，由于操作非法，例如除数为0，结果上溢等，或者用户程序试图执行去处理异特权指令等。这时处理机应该转向特定的程序常事件。

处理的方法一般是先向用户报告哪条指令引起了异常事件以及引起了何种异常事件，然后继续用户程序的执行，或者结束用户程序的执行，返回到操作系统。

异常的原因

  • I/O 外设请求

  • 用户 OS 服务请求

  • 断点

  • 整数算术运算溢出

  • 浮点算术异常

  • 缺页

  • 未对齐的存储器访问

  • 违反了存储器保护权限

  • 硬件错误功能

  • 未定义指令

异常和中断

Exceptions are exceptional events that disrupt the normal flow of a program
本节所指的异常是广义异常，包括了中断和狭义上的异常。

中断例子

  • 用户敲击键盘
  • 网络包到达

异常例子

  • 除0
  • 溢出
  • 缺页

MIPS架构中的异常

异常能在流水线的哪些阶段中产生？

阶段 可能产生的异常类型
IF 取指时发生缺页;
存储器访问边界未对齐;
违反了存储器访问权限;
ID 未定义的或非法操作码;
EX 算术异常;
MEM 存取数据时缺页;
存储器访问边界未对齐;
违反了存储器访问权限;
WB 无

非流水线处理机是在一条指令执行的过程中检测异常事件，当异常事件发生时处理机在该指令结束时转向异常事件处理程序，处理完毕后再返回到用户程序。

当这些事件发生时，处理机应该适当地保存当前处理机的状态，比如当前程序计数器PC的内容，处理机状态寄存器的内容，等等。然后，处理机由硬件向PC写入特殊的值，即异常事件处理程序的入口地址，以实现程序的转移。

在流水线上出现异常的情况

出现异常后，要清除进入流水线的指令，使异常处理程序进入流水线。

image-20221201162622960

4.5.2 异常处理

处理流程：停止和重新开始执行

  1. 强制一个trap指令进入流水线

  2. 关掉出错指令及后面指令的所有写操作，直到trap指令开始执行
    这避免了后续指令改变机器出错时的状态

  3. 当trap指令开始执行，唤醒OS ，OS保存出错指令的PC值

  4. OS试图修复异常，然后重新执行出错指令
    重新取出错指令的地址送给PC
    重新执行出错指令

流水线实现中的异常

本节以 add $1, $2, $1 作为算术溢出类型异常的例子

  • 假设该指令产生了一个算术溢出，则必须清除流水线中该指令后续进入流水线的指令，并开始在新异常地址取指。
  • 可使用之前的重置机制

异常可被视为另一种形式的控制冒险

实现清除流水线中的指令

add $1, $2, $1

IF.Flush冲掉IF/ID指令
ID.Flush冲掉ID/EX指令
EX.Flush冲掉EX/MEM指令

image-20221201163132879

实现异常处理程序进入流水线

PC = 异常处理程序入口地址

实现中断或异常时PC的保存

流水线处理机在每个周期都取来一条指令，假如当处在执行（EXE）级的指令（假设该指令的字地址为n）的操作结果上溢时，PC已经不再是n了。

例如：

在 EX 级的指令地址为 n: add $1, $2, $1（出现了异常）

在 IF 级的指令 PC = n+8

解决方法：

将导致异常的指令地址放入EPC中

把PC逐级地保存下来，即让指令的PC跟着指令一起往前走

哪条指令发生异常就保存哪条指令的PC

4.5.3 精确异常和非精确异常

精确异常 Precise Exceptions

当异常出现时，如果出错指令之前的指令能正常完成，出错指令及其后的指令能够重新正常执行，则称该流水线是精确异常。

精确异常的条件：

  • 出错指令之前的指令正常完成。
  • 出错指令及其后的指令能重新正常执行的条件：出错指令及其后的指令没有改变机器的状态。

在这个模型下，重新执行就很简单了:

  • 简单地重新恢复执行出错指令
  • 如果它不是一个可恢复执行的指令，则执行下一条指令

非精确异常

当不同指令需要不同时钟周期才能完成的时候难以实现精确异常。

在某条指令产生异常之前，后面的指令可能已经执行完毕。（后续指令改变了机器的状态）

例如
Multiply r1, r2, r3 ; 需 10 cycles
Add r10,r11,r12 ; 需 5 cycles

Add在Multiply完成之间执行完毕。如果在Add执行完之后且Multiply完成之前，Multiply发生溢出，此时R10的值已经被更新过了。

异常发生后，要先恢复Multiply执行前的状态然后再重新执行Multiply很困难，此为非精确异常。

精确/非精确异常 两种工作模式

某些处理器实现了两种工作模式：精确异常和非精确异常。

  • 特殊的软件指令保证精确异常。

  • 处理器若工作在精确异常模式下，运行速度更慢。

  • 一般来说，整数操作所产生的异常是精确的，浮点异常一般不是精确的。

4.5.4 一个时钟周期内的多个异常

image-20221201163402370

在Clock Cycle 4, LW指令可能出现数据缺页异常，且ADD指令 可能出现算术异常。CPU应该先响应哪个异常?

应该先响应前一条指令，即LW指令的缺页异常，然后重新开始LW指令的执行。

当LW指令执行完毕后，ADD’s 算术异常会再次发生。

4.5.5 多个异常的乱序产生

（后一条指令先出现异常）

image-20221201163413261

ADD指令在取指阶段导致了一个指令预取异常，LW指令在访存阶段导致了一个异常。

如果我们要实现精确异常，LW 异常必须先被处理。实现精确异常的方式：设置一个按指令顺序推迟异常响应的机制。

具体的实现方式如下：

  • 推迟异常响应，出现异常时不立即响应。

  • 当一条指令即将离开流水线(MEM/WB), 检查是否有挂起未响应的异常。

  • 如果一条指令产生过了多个异常，应先响应最早出现的异常。

  • 可行的办法是：在流水线中的每条指令有一个异常状态向量表：如果一个异常被推迟了，它就被添加到对应的向量表，并禁止所有会影响系统状态的写操作。

4.6 指令级并行技术概述

4.6.1 指令级并行

几乎所有的处理机都利用流水线来使指令重叠并行执行，以达到提高性能的目的。这种指令之间存在的潜在并行性称为指令级并行 (ILP：Instruction-Level Parallelism)。

在流水线模型机中，如果指令间无相关或者相关可以通过专用数据通路消除，则流水线没有停顿，指令级并行得以充分发挥。但是，不能消除的相关必然会导致流水线的停顿，使流水线的利用率下降。例如，涉及load指令的内部前推技术时只能强制暂停流水线的执行。

那是不是对此情况真的就只能暂停流水线的执行呢？答案肯定是NO。

因此如果要避免暂停流水线，一个相关指令的执行必须和被相关的前一条指令的要分开，分开的时钟周期需至少等于被相关的指令的流水线延迟。

例如：

load r1, 100(r2)
add  r3, r1, r4

若顺序执行，则这两条指令之间必须暂停一个时钟周期。也可在这两条指令之间插入一条非数据相关的指令。

本章将分别以硬件和软件实现的方式讨论如何打乱指令之间的顺序，既保证执行结果的正确性，又不牺牲性能。

打乱指令顺序主要有两种方法：

  • 一种是在编译阶段静态的发现指令级并行，再重新排序和优化指令（静态调度）；
  • 一种是在硬件执行指令时动态的发现指令级的并行，再重新排序指令（动态调度）。

如Intel的Pentium系列采用动态调度；Intel的Itanium（用于科学领域和特殊应用）采用静态调度。

在RISC机器中，指令系统支持编译优化，其编译器都会采用静态调度方式，有的也同时采用动态调度。

在个人移动设备上，由于能耗的限制，一般使用软件的方式，如ARM处理器(包括Cortex-A8)。但Cortex-A9使用了硬件方式。

4.6.2 多发射

流水线挖掘了指令间潜在的并行性：

  • 增加流水线的深度以重叠更多的指令
  • 复制处理器内部部件的数量

通过复制处理器内部部件的数量，使得每个流水级可以启动多条指令，这种技术被称为多发射。

多发射的CPI<1，例如四路多发射处理器的CPI可达0.25，如果是5级流水线，可有20条指令在流水线中。

多发射的实现的方式：

  • 编译器完成（静态多发射）
  • 硬件完成（动态多发射）

需考虑的问题：

  1. 在每个时钟周期发射多少条什么指令？
  2. 处理数据冒险和控制冒险

4.6.3 静态多发射处理器

静态多发射处理器使用编译器来帮助封装多条指令并处理冒险。在给定时钟周期内发射的多条指令称为发射包(超长指令字)。

不同的静态多发射处理器：

  • 某些设计中，编译器负责避免所有的冒险，通过调度指令和插入nop等方法使代码在执行时完全不需要冒险检测。
  • 某些设计中，由硬件检测数据冒险并在两个发射包间产生阻塞，而编译器只负责避免同一个发射包中两条指令的依赖。

静态双发射处理器的结构

考察一个简单的双发射MIPS处理器：（两条指令组合成对）

  • 前一条指令是ALU操作或分支；
  • 后一条指令是lw或sw；
  • 实在没有配对指令，就用nop指令代替。

对处理器的要求：

  • 每个时钟周期要取回和译码64位指令；
  • 两条指令成对放在64位对齐的内存区域；
  • 寄存器再增加两个读端口，一个写端口；
  • 增加一个ALU；
  • 其他相应通路。

image-20221201163807733

理论上性能变为原来的两倍。

但是，额外的重叠使数据冒险和控制冒险带来的性能损失也增加了。

lw指令的结果不能在下个时钟周期使用，意味着下一个发射包的两条指令都不能使用lw指令的结果。

静态双发射流水线的指令调度

在一个MIPS静态双发射流水线中，下面循环将如何调度？

image-20221201163840664

最佳调度方式（CPI=0.8）：

image-20221201164157082

循环展开

一种重要的从循环中获得更多性能的编译技术叫循环展开。

  • 循环体被复制多份；
  • 重叠不同循环体的指令可以获得更多的ILP；
  • 消除不必要的循环开销指令。

寄存器重命名：$t0 变成 $t0,$t1,$t2,$t3

image-20221201164439202

4.6.4 动态多发射处理器

刚才这种实现的前提是什么？能确定分支跳转成功。

如果处理器采用动态分支预测技术推测分支的结果，那么这些信息在编译阶段无法得到。

要发挥指令乱序执行的特点，需要允许多条指令同时处于执行阶段，这就要求有多个功能部件或功能部件流水化或者两者兼有。如果没有多个功能功能部件，动态调度的最大的优势也就没有了。

动态多发射处理器也称为超标量处理器。指令顺序发射，在每个周期由硬件决定是发射0条，1条还是多条指令。

与静态多发射的异同：

  • 同：动态多发射仍然依赖编译器对指令的调度，错开依赖指令
  • 异：由硬件保证执行的正确性和速度，尽量不产生冒险和阻塞（采用了动态流水线调度技术）

考虑下面的指令序列：

image-20221201164606338

即使sub指令先准备好，但是仍然得等lw和addu先执行。

动态多发射处理器中，即使lw和addu没有执行，也可以优先执行sub指令。

动态流水线调度的结构

动态流水线调度：动态选择下一条要执行的指令，甚至重排避免阻塞。

流水线被划分为3个主要单元：取值与发射单元，多个功能单元，一个提交单元。

image-20221201165020486

动态调度经常与基于硬件的推测机制集合，特别是对分支指令的推测。

通过对分支指令方向推测，动态调度处理器可以在推测方向上进行取值和执行。由于指令是顺序提交的，可以在分支指令及所有推测执行的指令提交前知道推测是否正确。

动态调度处理器的优势

  1. 并不是所有阻塞都是可以事先知道的，尤其是Cache缺失可能导致不可预测的阻塞。动态调度可以调度其他无关指令避免性能损失；
  2. 编译器无法预知的信息，如分支结果，可由动态推测解决；
  3. 流水线延时和发射宽度在不同处理器上实现不同，最佳编译也不固定。如：调度一个互相依赖的指令序列的具体方式和发射宽度密切相关，流水线的结构也影响循环展开的效果。动态调度通过硬件将这些细节对用户透明，代码具有更好的通用性。

两种动态调度算法

  • 记分牌动态调度算法
  • Tomasulo动态调度算法

4.7 指令调度

4.7.1 限制指令顺序的调整的因素

指令i与指令j之间的关系除了数据冒险之外，还可能有以下两种：

（1）读后写：指令i先执行，指令j写的名是指令i读的名。反相关指令间的顺序是必须保证的。

（2）写后写：指令j和指令i写相同的名。输出相关指令的执行顺序是不能颠倒的。

考虑下指令顺序被调整后，可能会出现什么问题？

写后写：

ADD   R4 , R0 , R2
…
ADD   R4 , R5 , R8

读后写：

ADD   R4 , R0 , R2
…
ADD   R0 , R5 , R8

数据冒险：

ADD   R4 , R0 , R2
…
ADD   R1 , R4 , R8

4.7.2 指令调度方法

指令顺序的调整

在编译器实际进行指令调度过程中，通过改变指令在程序中的位置，将相关指令间的距离加大到不小于指令执行延迟的时钟周期数，这样就可以将相关指令转化为无关指令。

编译器在完成指令调度时，受限于两个特性：

  • 一是程序的指令的逻辑顺序性；
  • 二是流水线功能部件的执行延迟。

换名技术

与数据相关比较，名相关的指令间没有数据交换。如果一条指令中的名改变了，并不影响另外一条指令的执行。因此，可以通过改变指令中操作数的名字来消除名相关，这就是换名技术。

对寄存器操作数进行换名称为寄存器换名。这个过程可以用编译器静态完成，也可以用硬件动态完成。

判断数据相关的对象

另一个需要注意的问题是判断数据相关的对象：寄存器和存储器。

当数据相关发生在寄存器之间时，编译器较容易判断，因为寄存器是按统一规则被唯一命名的，不存在二义性。

而对于存储器中的数据相关性判断要困难得多，如10（R1）与20（R2）表示相同地址。又如程序执行时的有效地址会随着执行变化，20（R4）与20（R4）可能是不同的。因此，存储器数据相关性检测会更复杂，通常用硬件判断。

解决控制冒险

再看控制冒险，控制冒险对指令顺序的调整会带来两方面的限制：

  • （1）与控制相关的语句或指令不能移到分支语句或指令之前执行。例如if…then语句中，then后面的语句不能移到if之前执行。
  • （2）与控制无关的语句或指令不能移到该分支语句或指令之后，从而受这个分支控制。例如if…then语句中，if前的语句不能移到then后面部分执行。

例如：

image-20221201184328660

由于三条分支指令的存在，引起控制相关，导致其后的指令不能跨越分支指令进行调度，即不同循环遍次里的指令不能够跨越循环遍次进行调度。

去除这三条指令后，就消除了程序中的控制相关，从而才有可能在不同循环遍次之间进行全局调度，以有效提高程序在流水线上的执行吞吐量。

此外，对于控制冒险来说，还需要保持异常行为。调整指令的顺序不能影响改变之前异常出现的条件。

看下面一个简单的例子：

    ADD    R2，R3，R4
    BEQZ   R2，L1
    LW     R1，0(R2)
L:  …

如果我们忽略这个控制冒险，把load指令移到分支指令之前，这个load指令可能会导致一个存储保护异常。

循环展开技术

循环展开技术是利用多次复制循环体，并相应调整展开后的指令和循环结束条件，增加有效操作时间与控制操作时间的比率。这种技术也给编译器进行指令调度带来了更大的空间。

4.7.3 指令调度实例

下面通过一个例子的介绍说明循环展开的过程。

假设使用的浮点流水线的延迟如下表：

产生结果指令 使用结果指令 延迟时钟周期数
浮点计算 另外的浮点计算 3
浮点计算 浮点数据存操作（SD） 2
浮点数据取操作（LD） 浮点计算 1
浮点数据取操作（LD） 浮点数据存操作（SD） 0
  • 条件转移指令如果使用上一条指令的结果作为判断条件，需要等待一个时钟周期。
  • 条件转移指令同时还有一个时钟周期的分支延迟。

对于下面的源代码，转换成DLX/MIPS汇编语言，在不进行指令调度和进行指令调度两种情况下，分析代码一次循环的执行时间。

for (i=1; i<=1000; i++)
    x[i] = x[i] + s;

解：浮点数长度8个字节。

(1) 变量分配寄存器

整数寄存器R1：循环计数器，初值为向量中最高端地址元素的地址。
浮点寄存器F2：保存常数S。

假定最低端元素的地址为8。

(2) 转换为MIPS汇编语言后的程序

Loop:	LD	   F0,0(R1) 
    	ADD.D  F4,F0,F2
    	SD	   0(R1),F4
    	SUBI   R1,R1,#8
    	BNEZ   R1,Loop

不进行指令调度

(3) 不进行指令调度时，根据前表给出的浮点流水线指令执行的延迟，以上程序执行的情况如下：

image-20221201191359623
  • （1）LD + （3）浮点计算，延迟1个时钟周期
  • （3）浮点计算 + （6）SD，延迟2个时钟周期
  • （3）浮点计算 + （7）浮点计算 ，延迟3个时钟周期
  • （9）条件转移指令使用（7）浮点计算 的结果，延迟1个时钟周期
  • （9）条件转移指令同时还有一个时钟周期的分支延迟（10）

每完成一次循环需要10个时钟周期，其中5个是空转周期。

调整指令顺序

(4) 对指令进行执行顺序上的调度：

  • SD指令放在条件转移指令之后
  • 对存储器地址指针计算指令进行调整

image-20221201191434471

通过指令调度后，一个元素的操作时间从10个时钟周期减少到6个，其中5个周期是有指令执行的，1个空转周期。那还能不能再优化一些？

再仔细分析以上指令发现，其中的有效指令LD、ADDD和SD占用了3个时钟周期，而其余指令是为了控制循环和解决数据相关。因此，要减少或消除循环控制开销的一种有效方法就是运用循环展开技术。

循环展开技术

第一步：考虑将上面的循环展开，展开后的每次循环包括4次原有循环。得到以下由17条指令构成的指令序列:

image-20221201191959917

第二步：编译器可以通过对相关链上存储器访问偏移量的直接调整，将前3条SUBI指令消除掉，从而得到下面一个14条指令构成的指令序列，如下所示：

image-20221201192025745

第三步：通过寄存器换名，消除读后写和写后写。

F0、F4：用于展开后的第1个循环体；
F2：保存常数；
F6和F8：用于展开后的第2个循环体；
F10和F12：用于展开后的第3个循环体；
F14和F16：用于展开后的第4个循环体。

image-20221201192041224

第四步：对刚才的指令序列进行优化调度

image-20221201192251579

结果分析：

  • 没有数据相关引起的空转等待
  • 整个循环仅仅使用了14个时钟周期
  • 平均每个元素的操作使用14/4=3.5个时钟周期
  • 循环展开和指令调度可以有效地提高循环级并行性。
  • 这种循环级并行性的提高实际是通过实现指令级并行来达到的。

4.7.4 指令调度小结

循环展开所需的条件

  • 需要对原有指令作必要处理；
  • 需要多余的寄存器的支持。
  • 所得到的效果依赖于所展开循环的次数。
  • 需要相关判断等其他指令调度技术的支持

循环展开和指令调度时要注意的问题

  • (1) 保证正确性
  • (2) 注意有效性
  • (3) 采用寄存器换名
  • (4) 尽可能减少循环控制中的测试指令和分支指令
  • (5) 注意对存储器数据的相关性分析
  • (6) 注意不引入新的冒险性。

4.8 记分牌动态调度算法

问题：我们知道，要提高处理器的性能，希望CPI能够尽量小，最好能够小于1。对于前面介绍的流水线模型机和循环展开技术，CPI可能小于1吗？

到目前为止，我们已经看到了动态调度机制、多发射机制和推测机制各自是如何工作的。要提高处理器的性能，希望CPI能够尽量小，最好能够小于1。如果指令流水线每个时钟周期只能流出一条指令，则CPI就不可能小于1。只有处理器能够在一个时钟周期流出多条指令时，才有可能使CPI小于1。

在这一节中，我们要将三者结合到一起，这将是一个与现代微处理器十分相似的微系统结构。

记分牌技术的目标：在资源充足时，尽可能早地执行没有数据阻塞的指令，争取达到每个时钟周期流出尽量多的指令。

设指令预取到指令队列中，为了允许乱序执行，将基本流水线的译码阶段再分为两个阶段：

  • (1)流出（Issue，IS）：指令顺序发射，检查是否存在结构阻塞。
  • (2)读操作数（Read Operands，RO）：当没有数据相关引发的阻塞时就读操作数(可以乱序)。

执行阶段紧跟在读操作数之后，工作过程类似于基本流水线。

假设：处理器采用多个功能部件。

如，CDC 6600具有16个功能部件（采用记分牌）：4个浮点部件，5个存储器访问部件，7个整数操作部件。

下面，在DLX中，记分牌技术主要用于浮点部件（其延迟大，乱序执行可有效提高性能）。假设有2个浮点乘法器、1个浮点加法器、1个浮点除法部件和1个整数部件。

采用记分牌技术的DLX处理器的基本结构：

image-20221201195315114

记分牌电路负责记录资源的使用，并负责冒险检测，控制指令的流出和执行。

记分牌的四个阶段

每条指令在流水线中在指令预取之后的过程分为四个阶段：

(1) 流出（Issue，记为IS）

如果本指令所需的功能部件有空闲，并且本指令的目的寄存器与其它正在执行的指令使用的目的寄存器不同，记分牌就向下一阶段流出本指令，并修改记分牌内部的数据记录。

进入这个阶段判断指令间存在的结构冒险、写后写。

进入流出阶段的指令就没有结构冒险与写后写问题。

(2) 读操作数（Read Operand，记为RO）

记分牌需要监测源操作数寄存器中数据的有效性，如果本指令的源操作数寄存器与前面指令不存在数据冒险，或者一个正在工作的功能部件已经完成了对源寄存器的写操作，那么此操作数有效。当操作数有效后，记分牌将启动本指令的功能部件读操作数并开始执行。（换句话说，只有源操作数都就绪时，才进入RO）

指令在IS段按序流出，从RO段开始乱序执行。

解决了数据的数据冒险。

通过以上二个步骤，记分牌动态检测到结构冒险、写后写、数据冒险，则暂时阻塞相关指令，用延迟解决相关问题。

(3) 执行（Execution，记为EX）

取到操作数后就可以由功能部件执行指令，允许多条指令同时且乱序执行，不同功能部件需要的时钟周期不同。

(4) 写结果（Write Result，记为WR）

检测读后写（WAR）：
同时出现以下的情况时，就不允许指令写结果：前面的某条指令还没有读取操作数，且其某个源操作数寄存器与本指令的目的寄存器相同。

如果没有读后写，目标寄存器空闲，就将结果写入到目标寄存器中，然后释放本指令使用的所有资源。

需要记录的信息

记分牌需要记录的信息分为三部分：

(1) 指令状态表

记录正在执行的各条指令已经进入记分牌DLX流水线四段中的哪些段。

(2) 功能部件状态表

纪录各个功能部件的状态。每个功能部件在状态表中都由以下九个域来纪录：

  • Busy： 指示功能部件是否在工作
  • Op： 功能部件当前执行的操作
  • Fi： 目的寄存器编号
  • Fj，Fk：源寄存器编号
  • Qj，Qk：向Fj，Fk中写结果的功能部件
  • Rj，Rk：表示Fj，Fk是否就绪（IS段） ，是否已经被使用（RO、EXE、WR段）

题目中RO、EXE、WR段中Rj，Rk全写为no

(3) 结果寄存器状态表

每个寄存器在表中有一个域，用于记录当前已经进入流水线的指令所需写入该寄存器的功能部件（编号）。如果当前正在运行的功能部件不需要写入该寄存器的，则相应域置为空。

例

给出一段代码如下所示：

image-20221201200202996

加法需2个时钟周期
乘法需10个时钟周期
除法需40个时钟周期

采用记分牌技术的DLX处理器的基本结构（2个浮点乘法、1个浮点除法、1个浮点加法、1个整数部件）

image-20221201195315114

解：

DLX记分牌信息组成和记录的信息

image-20221201200336764

功能部件状态表

image-20221201200410793

结果寄存器状态表

image-20221201200425136

例

假设代码段和记分牌信息的起始点状态跟上例一样。分别给出MULT.D和DIV.D准备写结果之前的记分牌状态。

image-20221201200901382

解： 在分析记分牌状态之前，首先需要分析指令之间存在的相关性，因为相关性会影响指令进入记分牌DLX流水线的相应段。

(1) 第二条LD指令到MULD和SUBD、MULTD到DIVD之间以及SUBD到ADDD之间存在着先写后读；
(2) DIVD和ADDD之间存在着先读后写；
(3) ADDD和SUBD指令关于浮点加法部件还存在着结构冒险。

执行到MULT.D将要写结果时记分牌的状态 (指令状态表) (功能部件状态表) (结果寄存器状态表)

image-20221201201021668 image-20221201201329446 image-20221201201336764

执行到DIV.D将要写结果时记分牌的状态 (指令状态表) (功能部件状态表) (结果寄存器状态表)

image-20221201201447826 image-20221201201428890 image-20221201201459455

例（第二次课堂练习）

设采用记分牌算法的MIPS结构如下图（2个浮点乘法、1个浮点除法、1个浮点加法、1个整数部件）。

image-20221201195315114

假设该结构流水线执行的延迟如下：整数计算的EX级需1个时钟周期，浮点加法的EX级需5个时钟周期；浮点乘法的EX级需10个时钟周期；浮点除法的EX级需40个时钟周期。

请根据当前的指令状态表第一条指令的状态，完成当指令“ADD.D F8，F6，F10”执行到WR阶段前的指令状态表、功能部件状态表、寄存器状态表的内容。

image-20230228134152447

image-20230228134157169

image-20230228134159738

分析记分牌是如何控制指令执行的（略）

记分牌的性能

记分牌的性能受限于以下几个方面：

(1) 程序指令中可开发的并行性，即是否存在可以并行执行的不相关的指令。

(2) 记分牌容量。记分牌的容量决定了流水线能在多大范围内寻找不相关指令。流水线中可以同时容纳的指令数量又称为指令窗口。

(3) 功能部件的数目和种类。功能部件的总数决定了结构冲突的严重程度。

(4) 反相关和输出相关。引起记分牌中先读后写和写后写阻塞。

4.8 Tomasulo动态调度算法

记分牌技术允许在资源充足时乱序执行。对于数据相关、名相关，通过检测后延迟相关指令的执行解决相关。由于乱序执行引起的名相关会增多，因此写后写与先读后写导致的阻塞也会更严重。那有没有更好的算法？或者如果说记分牌技术有不足，那么不足在哪里，应该如何改进？

下面，将讨论的Tomasulo算法，采用寄存器换名技术，使用了大量的缓冲器即保留站作为虚拟寄存器暂时替代指令中的寄存器，以动态消除名相关。

Tomasulo动态调度算法基本思想

Tomasulo算法将记分牌的关键部分和寄存器换名技术结合在一起。通过寄存器换名消除写后写、先读后写相关引起的停顿。

编译器通过寄存器换名可以解决写后写、先读后写相关。

在Tomasulo算法中，寄存器换名通过”保留站和存取缓冲”实现，它保存已经流出(Issue)（特别注意：仍然是顺序流出）的指令所需的操作数。其基本思想是：

  • 只要任何一个操作数有效，就将其取到保留站(存取缓冲)，避免流出指令读操作数时才到寄存器中取数据。
  • 指令的执行结果直接送到等待数据的其它保留站中去。
  • 一条指令流出时，存放操作数的寄存器名被换成为对应于该寄存器保留站的名称（编号）。

实际上，保留站的数目远多于实际的寄存器，保留站就是存放操作数与结果的虚拟寄存器，对系统结构层透明。

指令流水线的分段情况

使用Tomasulo算法的流水线需三段：

(1) 流出（Issue）

从指令队列中取一条指令：

  • 如果是浮点操作且有空的保留站就流出（进入Issue阶段），若其中的操作数在寄存器就绪就将其送入保留站，如果未就绪就在保留站中记录产生该操作数的保留站编号（操作数寄存器名换成了保留站名）。
  • 如果是访存操作且有空的缓冲就流出到缓冲。
  • 如果没有空的保留站和缓冲，即有结构相关，就不流出。

(2) 执行（Execute）

如果保留站的操作数未计算出，就用保留站编号监视CDB（公共数据总线），一旦有结果就取到保留站中，当两个操作数就绪，进入执行阶段，执行指令操作。解决先写后读相关。

(3) 写结果（Write Result）

功能部件完成计算后，将结果连同产生该结果的保留站号一起送到CDB上。根据流出时的记录，所有等待本保留站结果的保留站、存缓冲、目标寄存器将同时从CDB上获得所需数据。

采用Tomasulo算法的DLX浮点部件的基本结构

image-20221201203839836

在DLX模型机中：

保留站

保留站（5个，其中3个是浮点加法器，2个是浮点乘法器）中保存已流出并等待到本功能部件执行的操作（指令）；还保存指令执行所需的控制信息。

  • 如果该操作的源操作数在寄存器中已经就绪，就将该操作数取来，保存到保留站中；

  • 如果操作数还没有计算出来，则保留站中记录这个操作数将由谁计算出来，即指明它由哪个功能部件产生。

存取缓冲

取缓冲（6个）和存缓冲（3个）保存的是读/写存储器的数据和地址。

浮点寄存器通过一对操作数总线连到功能部件的保留站，通过其中一条总线连到公共数据总线，再送到存缓冲。
功能部件的计算结果和从存储器读取的数据送到公用数据总线上，除了取缓冲的输入和存缓冲的输出以外，所有部分均与公用数据总线相连。

两个运算功能部件

  • 浮点乘法器完成乘法和除法操作

  • 浮点加法器完成加法和减法操作

定义有关的术语和数据结构

标志（tags）

指缓冲或产生结果的保留站（功能部件）。

每个保留站有以下6个域：

  • Op：对源操作数S1和S2所进行的操作。
  • Vj，Vk：两个就绪源操作数的值。
  • Qj，Qk：产生源操作数的保留站号。
    等于0表示操作数在Vj和Vk中或不需要操作数。
  • Busy：标示本保留站和相应的功能部件是否空闲。

Vj和Qj只能同时有一个有效， Vk和Qk也只能同时有一个有效。

存缓冲有6个域：

  • Busy：标示缓冲是否空闲。
  • Address ：地址域，用于记录保存的存储器地址。
  • Vj： 保存来自已经就绪的寄存器地址分量。
  • Vk域：保存要存入存储器的数据。
  • Qj：产生有效地址中分量的保留站号。等于0表示地址分量在Vj中或不需要操作数。
  • Qk域：结果要存入存缓冲的保留站号。如果Qk空，表示存入的数据在Vk域或没有指令要将结果写入存缓冲。

取缓冲有4个域：

  • Qj、 Vj、 Busy：标示缓冲是否空闲。
  • Address ：地址域，用于记录取的存储器地址。

每个寄存器有1个Qi域：

结果要存入本寄存器的保留站或取缓冲号。

如果Qi空，表示当前没有指令要将结果写入此寄存器。

当寄存器空闲时，Qi域空。

例

假设浮点流水线中执行的延迟如下：

  • 加法需2个时钟周期
  • 乘法需10个时钟周期
  • 除法需40个时钟周期

对于下列代码，保留站的信息是怎样形成的：

image-20221201203936405

表4-10、4-11、4-12给出的是采用Tomasulo算法时保留站、存缓冲、取缓冲和寄存器的标志等信息。

指令状态表

image-20221201203951815

注意：指令状态表并不是硬件的一部分（列出是为了帮助理解），指令流出后的状态都保留在保留站中。

对比记分牌算法：

image-20221201204013773

保留站与存取缓冲

image-20221201204035328

寄存器的标志

image-20221201204045505

例

在上例的代码中：考察当代码执行到MUL.D准备写回结果时，各状态表中的信息。

解：

指令状态表

如表4-13、4-14、4-15所示，ADDD和DIVD之间的尽管存在F6先读后写相关，由于寄存器换名（DIVD对应保留站Vk域保存了第一个LD的结果）消除了阻塞，ADDD可以早于DIVD先执行完成。

image-20221201204108556

对比记分牌

image-20221201204121862

保留站与存取缓冲

image-20221201204128077

寄存器的标志

image-20221201204135387

一个基于循环的例子

为了更好地理解寄存器重命名在消除WAW和WAR冒险中的作用，我们来考察下面的代码，这段代码将数组中的每个元素与F2中的标量相乘:

Loop: L.D		F0, 0(R1)
	  MUL.D		F4, F0, F2
	  S.D		F4, 0(R1)
	  DADDIU	R1, R1, -8
	  BNE		R1, R2, Loop    ;如果R1≠R2转移

如果预测分支转移成功，那么使用保留站技术可以允许这个循环同时有多个循环体在执行。做到这一点不用改变程序代码，因为在实际效果上，循环已经由硬件动态展开了，其机制就是通过寄存器换名过程从逻辑上扩展了可用寄存器的数量。

假定循环程序已经发射了两个循环体的指令，只是还没有Load、Store或其他操作已经执行完成。系统达到这个状态之后，就可以保持CPI接近于1.0的速率，始终有2个循环体在流水线中运行。

指令状态
指令 循环体 发射 执行 写回结果
L.D F0, 0(R1) 1 √ √
MUL.D F4, F0, F2 1 √
S.D F4, 0(R1) 1 √
L.D F0, 0(R1) 2 √ √
MUL.D F4, F0, F2 2 √
S.D F4, 0(R1) 2 √

Tomasulo算法与记分牌对比

除了寄存器换名， Tomasulo算法与记分牌在结构上有2处明显不同：

  • 相关检测和指令执行控制机制分开。一个功能部件的指令何时开始执行，由其保留站控制，而记分牌是集中控制。
  • 计算结果通过公共数据总线CDB和相关数据通路直接传送到保留站暂存，而不一定是写到寄存器。

Tomasulo算法相对于记分牌技术主要的优点：

  • (1)具有分布的阻塞检测机制；
  • (2)寄存器换名消除了数据的写后写和先读后写相关导致的阻塞。

尽管以上步骤与记分牌基本类似，但有明显不同：

  • 无需检测写后写、先读后写相关，指令流出时的寄存器换名已将其消除；
  • 通过CDB广播结果，送到需要结果的保留站、目标寄存器、存缓冲中。
  • 存储器存、取都作为基本功能部件。
  • 在保留站等待未就绪操作数，即通过延迟解决先写后读相关，因此没有记分牌中的“取操作数”段。

Tomasulo具体算法（略）

4.9 指令级并行小结

总之，动态调度的硬件代价较大，对于浮点运算其执行时间较长，采用动态调度可以有效提高程序执行的效率。但是如果处理器主要是执行简单的短周期指令，则采用静态调度性价比更高。

  1. 指令顺序调整后带来的读后写和写后写问题
  2. 静态调度的循环展开方法，寄存器换名（编译器实现）
  3. 动态调度：记分牌算法
  4. 多发射技术

文章目录

版权

本文遵循署名-非商业性使用-禁止演绎 4.0 国际 (CC BY-NC-ND 4.0) 标准。

部分内容源自互联网、书本和课堂，仅供交流学习，未用于任何商业用途。如果它们侵犯了您的权益，请与我们联系，我们将立即删除它们。

版权所有 © 2020-2026 Kloudy 保留所有权利.