首页 计算机专业课程笔记 计算机系统结构

# 第五章：指令集并行及其开发 —— 硬件方法

# 5.1 指令级并行的概念

指令级并行：指指令之间存在的一种并行性，利用它计算机可以并行执行两条或两条以上的指令；它由处理器硬件和编译程序自动识别和利用，不需要程序员对顺序程序做修改
指令集并行设计对象是基本程序块，即一串连续的代码

# 5.2 相关与指令级并行

指令相关有三种类型：数据相关（真相关，RAW），名相关（输出相关 WAW、反相关 WAR、是一种假相关），控制相关（改变 PC）
代码变换与指令调度必须保持两个关键属性：

  • 数据流不变：数据值从其产生者指令到其消费者指令的实际流动不变
  • 异常行为不变：不能导致程序中发生新的异常属性

# 5.3 指令的动态调度

定义：依靠专门硬件对代码进行调度，以减少数据相关导致的停顿

# 5.3.1 动态调度的基本思想

指令的按序发射和按序执行，成为流水线的最大局限。
乱序执行：指令的执行顺序与程序顺序不相同，完成顺序也是乱序的。
将译码阶段分为两个阶段：

  • 发射（Issue，IS）：指令译码，检查是否存在结构冲突；
  • 读操作数（Read Operands，RO）：等待数据冲突（RAW）消失，然后读操作数
    例子：
A: DIVD F0, F2, F4
B: ADDD F10, F0, F8
C: MULTD F12, F8, F14

运行效果，指令 C 先于指令 B 执行：

乱序执行引起新的 WAW 冲突：如果检测到 WAW，则也不发射；
乱序执行引起 WAR：通过写等待，或通过使用寄存器重命名来消除 WAR 冲突
带来的最大问题：异常（中断）处理比较复杂，可能发生不精确异常

# 5.3.2 记分牌动态调度算法

记分牌目标：在没有结构冲突时，尽可能早地执行没有数据冲突的指令，实现每个时钟周期执行一条指令
记分牌实现：硬件维护着用于记录指令的三张表 —— 指令执行状态表，功能部件状态表，寄存器状态表
记分牌算法中将所有指令都划分分为如下的四个阶段：

  • 发射：当前发射指令所需功能部件空闲，且所有其他正在执行的指令的目的寄存器与该指令的不同，记分牌就向功能部件发射该指令并修改状态表；可以解决 WAW 冲突
  • 读操作数：监测源操作数的可用性，如果数据可用，就通知功能部件从寄存器中读出源操作数并开始执行；动态解决了 RAW 冲突
  • 执行：产生出结果后通知记分牌它已经完成执行，可能要占用多个时钟周期
  • 写结果：记分牌一旦知道执行部件完成了执行，就检测是否存在 WAR 冲突；如已经不存在就通知功能部件把结果写入目的寄存器，并释放该指令使用资源；否则等待直到冲突消失（前面的某条指令还没有读取操作数，但与本指令目的操作数相同）
    指令执行状态表：记录正在执行的各条指令已经进入到了哪一段；
    功能部件状态表：九个字段 ——Busy, Op, Fi, Fj, Fk, Qj, Qk, Rj, Rk；注意当寄存器值被取走后，Rj 和 Rk 就会改为 no，从而唤醒后续有 WAR 依赖的指令进入写结果阶段

    结果寄存器状态表：指出哪个功能部件（编号）将把结果写入该寄存器，否则为 "no"；
    具体算法流程及约定，见 PPT P45+。

性能受限于：程序代码中可开发的并行性；记分牌的容量；功能部件的数目和种类；冲突的相关因素等
缺点：阻塞后续相同类型的指令

# 5.3.3 显式动态寄存器重命名

WAW 和 WAR 冲突都可以通过显式动态寄存器重命名消除，但是受限于寄存器数量；
对于循环而言，简单地对单个循环体重命名无法消除，需要对循环进行展开；
对于硬件而言，实际物理寄存器 PR 的数量要多于对软件可见的结构寄存器 AR，硬件微架构可以维护一个映射表，在写寄存器时，为 AR 分配 PR 并建立映射；在读寄存器时，查找映射表中最近一次写入的 PR；重命名后每一个目的寄存器映射到的 PR 都会改变
具体算法流程及约定，见 PPT P96+。
注意事项：对于诸如 DIVD F0, F8, F0 的指令，要将两个 F0 重命名为不同的 PR；保险起见，一般的操作中对所有目的寄存器都会先重命名

缺点：需要确定空闲的物理寄存器，以及高效率访问的映射表，管理空闲寄存器复杂（指针管理）

# 5.3.4 Romasulo 算法

核心思想：通过隐式寄存器重命名来消除 WAR 冲突和 WAW 冲突


保留站：保存一条已经发射并等待到本功能部件执行的指令，对于源操作数替换为具体数值（已经准备好）或者是即将产生它的保留站（功能部件）标识（未准备好）
公共数据总线：所有功能部件的计算结果都是送到 CDB 上广播，对于多发射处理器需要多条 CDB
load/store 缓冲器：存放需要计算出地址的分量（具体数值或标识），保存目标地址和已经完成 load 的结果 / 要 store 的值，等待数据被送到 CDB 上广播 / 送到存储器中

指令发射到保留站后，其操作数寄存器号或者换成了数据本身（如果该数据已经就绪），或者换成了保留站的标识，不再与寄存器有关系，这就是隐式寄存器重命名；计算结果不用经过寄存器，而是从产生它的保留站传送到所有需要它的功能部件
Tomasulo 算法的冲突检测和指令执行控制是分布的

指令执行的步骤：

  • 发射：顺序取指令队列中的指令，该指令的操作所要求的保留站空闲，根据源操作数是否就绪输送数值或标识，一旦被记录的功能部件完成计算，就直接把数据送达，消除了 WAR 冲突；对目标寄存器进行了先后预约，即寄存器上的保留站标识永远是顺序靠后的指令（覆盖前面的标识），消除了 WAW 冲突；如果保留站满，代表发生了结构冲突
  • 执行：当两个操作数都就绪后，保留站就用相应的功能部件开始执行
  • 写结果：功能部件计算完毕后，就将计算结果放到 CDB 上，所有等待该计算结果的寄存器和保留站（包括 store 缓冲器）都同时从 CDB 上获得所需要的数据
    符号约定及例子，见 PPT P37+

优点：冲突检测逻辑是分布的（通过保留站和 CDB 实现），消除了 WAW 和 WAR 冲突导致的停顿
问题：有可能在同一周期有多条指令准备好数据，但是执行单元同时只能执行一条指令，需要从中选择一条指令，简单的解决办法是 FIFO；无法实现精确中断

# 5.3.5 重排序缓存 ROB

希望：按序发射，乱序执行，按序完成
核心思想：记录指令在程序中的顺序，一条指令在执行完毕之后不会立马提交，等待直到前面所有指令都提交完毕

在 Tomasulo 算法结构基础之上，增加了 ROB，并且 CDB 总线不再直通逻辑寄存器堆，而是直通 ROB；ROB 连接指令发射单元获取顺序，所有指令需要从 ROB 读取数据，在发射时入队，在提交时出队
ROB 的结构：Entry（编号），Busy，Instruction，State，Destination，Value（指令可以提交时再提交到目的寄存器）
ROB 编号可以替换上面提到的保留站编号
在执行时 WRITE 阶段存储到 ROB，直到可以提交时进入 COMMIT 状态，写入真正位置
操作流程及例子，见 PPT P110+