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

1.流水线的概念、分类

概念：流水线是利用执行指令操作之间的并行性，实现多条指令重叠执行的技术。
- 特点：
  - 段数（Stage）：流水线分为多个阶段，每阶段完成指令的部分操作。
  - 吞吐量：单位时间内流水线输出的指令数量。
  - 瓶颈段：流水线中耗时最长的段，决定了整体性能。
分类：
1. 按时间是否均匀：
  - 均匀流水线：每段时间相等。
  - 非均匀流水线：段时间不等。
2. 按数据类型：
  - 标量流水线：处理标量数据。
  - 向量流水线：处理向量数据。
3. 按功能：
  - 单功能流水线：实现单一功能（如浮点运算）。
  - 多功能流水线：各段可进行不同操作。
4. 按工作方式：
  - 静态流水线：每段连接固定。
  - 动态流水线：各段连接可变，控制更复杂。
5. 按规模：
  - 操作流水线
  - 指令流水线
  - 宏流水线
6. 连接方式
  - 线性流水线
  - 非线性流水线
  解决访存冲突的办法：
  
  1)将主存分为两个独立编址的存储器：指令存储器和数据存储器，CPU可分别独立访问。
  
  2)低位交叉存取方式：可并行访问不在同一个存储体中的指令或数据。
  
  3)指令预取：在重叠操作中，当前一条指令在执行过程中就需要提前取出后面的指令进行相应处理，这种提前取出后继指令进行相应处理，称为先行（预取）。

2.流水线的时空图及性能指标计算

指令级并行(Instruction-Level Parallelism, ILP)

1.采用依靠硬件来发现和实现ILP(动态)，

2.依赖软件编译器来发现和实现ILP(静态)。

3.add, sub, addi, or, ori, lw, sw, beq每条指令在5级流水线的执行过程

4.结构冒险、数据冒险和控制冒险的判断，以及需要暂停的时钟周期数的判断（控制冒险的解决性能依赖于分支地址计算阶段和分支条件判断阶段）

5.结构冒险、数据冒险和控制冒险的解决办法

结构冒险：

(1)：插入暂停周期，即让流水线在完成前一条指令对数据的存储器访问时，暂停取后一条指令（指令存储器）的操作

(2)：设置相互独立的指令存储器和数据存储器或设置相互独立的指令Cache和数据Cache

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

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

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

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

•暂停流水线；

•使用相关专用数据通路；

•编译优化调度（静态调度）；

•动态调度。

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

控制冒险性能影响及解决方法

控制冒险会引入流水线停顿，导致吞吐率下降。为了降低控制冒险对性能的影响，通常会采取以下解决方案：

(1) 停顿（Stalls）

最直接的方法是暂停流水线，等待分支条件判断完成。缺点是会严重影响性能，尤其是分支频率高的程序。

(2) 静态分支预测

假设分支不会发生，继续执行顺序指令。如果预测正确，则无需停顿；如果预测错误，则需要清空错误指令并重新加载目标指令。

优点：实现简单，能减半控制冒险的影响。
缺点：预测正确率一般较低（50%左右）。

(3) 动态分支预测

基于硬件的预测机制，通过记录分支历史信息预测分支是否会发生。动态分支预测的准确率可以达到90%左右，大幅降低控制冒险的性能损失。

常用方法：
1. 1位预测：只记录最近一次分支的结果。
2. 2位预测：只有连续两次错误预测时才改变预测方向，效果更稳定。
3. 转移目标缓存（BTB）：提前记录分支目标地址，减少分支地址计算的开销。

(4) 延迟分支（Delayed Branching）

延迟分支技术允许编译器在分支指令后插入一条不会受分支影响的指令，从而减少分支延迟带来的性能损失。

限制：延迟槽中插入的指令有限，编译器需要额外优化代码。

6.流水线中处理中断和异常的方法

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

处理的方法一般是:

先向用户报告哪条指令引起了异常事件以及引起了何种异常事件，

然后继续用户程序的执行，或者结束用户程序的执行，返回到操作系统。

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

在流水线上出现异常:

7.记分牌/Tomasulo动态调度算法

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

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

一种是在硬件执行指令时动态的发现指令级的并行，再重新排序指令（动态调度）。

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

* 一是程序的指令的逻辑顺序性；

* 二是流水线功能部件的执行延迟。

以下是总结记分牌算法所需记录信息的表格：

类别	字段/内容	作用
指令状态表	当前指令的流水线阶段	记录每条指令在流水线四个阶段中的状态：`Issue`（发射）、`Read Operand`（读取操作数）、`Execute`（执行）、`Write Result`（写回）。
功能部件状态表	Busy	表示功能部件是否被占用。
	Op	当前功能部件正在执行的操作类型（如加法、减法、乘法等）。
	Fi	目标寄存器编号（指令结果需要写入的寄存器）。
	Fj 和 Fk	源寄存器编号（指令的两个操作数）。
	Qj 和 Qk	源寄存器 `Fj` 和 `Fk` 是否依赖其他功能单元的结果，以及依赖的功能单元编号。
	Rj 和 Rk	标记源寄存器 `Fj` 和 `Fk` 的操作数是否已准备好（1 表示已准备，0 表示未准备）。
寄存器状态表	每个寄存器的状态	记录寄存器当前的状态，指示哪个功能单元负责生成该寄存器的值。

记分牌记录信息概述

指令状态表：跟踪每条指令的流水线执行阶段，确保按正确阶段推进。
功能部件状态表：动态管理功能单元的使用状态，处理指令的数据依赖问题。
寄存器状态表：管理寄存器的状态和依赖，避免数据冒险。

这一表格清晰概括了记分牌的三部分信息及其作用，帮助实现指令的乱序执行和动态调度。

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

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

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

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

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

记分牌技术允许在资源充足时乱序执行。对于数据相关、名相关，通过检测后延迟相关指令的执行解决相关。由于乱序执行引起的名相关会增多，因此写后写与先读后写导致的阻塞也会更严重。

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

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

(1)具有分布的阻塞检测机制；

(2)寄存器换名消除了数据的写后写和先读后写相关导致的阻塞。

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