[[计算机体系结构]]

Recap

ILP是指令序列潜在的并行性、软硬件技术相结合
结构冲突、数据冲突、控制冲突对CPI的影响
基本块和循环级并行

循环展开调度的基本方法
浮点流水线、整数流水线的特性
循环无调度执行
循环调度、循环展开
循环展开并结合调度执行

指令的动态调度

动态调度原理

编译器本质上通过对循环中的寄存器重命名开展开循环

硬件也可以通过寄存器重命名和乱序执行的方法（OoO）来获得同样的效果

冲突的检测和调度

存在数据相关：

暂停
停止取指和发射指令

静态调度：

依靠编译器

编译期间的代码调度和优化

相关指令拉开距离来减少可能产生的停顿

动态调度：

依靠专门硬件对代码进行调度

动态调度的原理

指令是按照顺序流出的，是按照顺序执行的

DIVD F4 F0 F2
ADDD F10 F4 F6
SUBD F12 F6 F14

ADDD指令和DIVD指令关于F4相关，导致流水线停顿

SUBD指令虽然无关，但是也会被阻塞

在基本流水线中

检测结构冲突
检测数据冲突

乱序执行

指令的执行顺序和程序的顺序不同
指令的完成也不同

为了支持乱序执行

流出：指令译码，检查是否有数据冲突

读操作数

动态调度算法之一：记分牌

记分牌在1964年被Cray用于CDC 6600

记分牌允许乱序执行，前提是：

充足的资源
指令可以乱序执行

基本原理：

每条指令经过记分牌，记录各个指令之间的数据相关的信息，进行相关的检测，控制指令的流出和执行

如果记分牌判断出一条指令不能立即执行，它就检测硬件的变化从而决定什么时候可以执行

集中控制寄存器和处理单元的数据传送，检测或者消除数据的相关性，加快程序的执行速度

记分牌的执行过程

流出
- 本指令所需要的功能部件有空闲
- 正在执行指令使用的目的寄存器和本指令不同
  :heavy_check_mark: 保证没有写后写相关（WAW）
- 如果存在结构冲突或者WAW相关，这个指令就不会流出，本指令就不会流出，后面的指令也不会流出，直至阻塞消失
读操作数
- 前面已经流出的还在运行的指令不会本指令的源操作数寄存器进行写操作
- 一个正在工作的功能部件已经完成了对这个寄存器的写操作
  :heavy_check_mark: 动态解决RAW相关

前面两步完成了原来ID段的功能

执行

开始于取到操作数之后
结果产生之后，修改记分牌
FP流水部件会占用多个周期

写结果：检查WAR相关

出现以下的情况的时候，不允许指令写结果

前面某条指令（已经按照顺序）还没有读取操作数
而且其中某个源造作书和本指令的目的寄存器相同

记分牌结构

指令状态表

功能部件的状态表

结果寄存器状态表

#### 记分牌实例

In-order Issue

out-of-order execute

out-of-order WR

### 动态调度算法之二：Tomasulo算法

整个360系列仅一个指令系统和一个编译器

要求具有很高的浮点性能，但是不是通过高端机器的专用的编译器实现

只有四个双精度浮点寄存器，编译器调度的有效性受到很大的限制

访存时间和浮点运算的时间都很长

可以支持的循环的多次迭代重叠执行

Tamassulo和记分牌

采用了很多和记分牌中的理念

两个较大的差异

Tomasulo算法中，冲突检测和执行控制是分布的，利用保留站实现
Tomasulo算法不检查WAR和WAW相关通过算法本身消除。计算结果通过专用通道直接从功能部件进入到保留站进行缓冲，而不是写到寄存器。

Tomasulo算法核心思想

记录并检测指令的RAW相关，操作数一旦准备就绪就立即执行，把发生RAW冲突的可能性降到最低。

不检查WAR和WAW相关，通过换名（Remainning）技术来消除WAR和WAW冲突

✔️ 基于Tomasulo算法的MIPS处理器浮点部件的基本结构

MIPS五阶段的流水线的改造

流出（数据就已经在保留栈中）
✨ 所以就不需要进行读出数据了
执行
结果写回

Tomasulo算法的三阶段

Issue：从队列中取出指令，如果存在一个空闲的保留站，就控制发射指令和操作数，消除WAR，WAW相关
Execution：当两个操作数就绪的时候就可以执行；如果没有准备好，就检测Common Data Bus 来获取结果；通过推迟指令执行避免RAW相关
Write result：将结果通过Common Data Bus 传给所有等待该结果的部件

#### 和记分牌的不同

无需任何的操作来检查数据的写后写WAW和先读后写WAR冲突，在指令流出的过程中，操作数寄存器号换成操作数本身（如果已经就绪）或者相应的保留站标识

通过公共数据总线来广播结果，将计算结果直接东产生的保留站传送到所有需要它的功能部件而不需要经过寄存器（动态解决了RAW）

存储器存和取都能作为基本的功能部件

由于保留站技术能够有效的解决先写后读，记分牌中的用于判断RAW的’取操作数‘段被取消。

CA-第十二讲 指令集并行