第四章指令集并行

国防科大计算机体系结构课程第四章笔记

4.1 指令集并行的概念

当指令之间不存在相关时，它们在流水线中是可以重叠起来并行执行的。这种指令序列中存在的潜在并行性称为指令级并行
- Instruction-Level Parallelism
- 简记为 ILP
如何知道指令之间可以并行？硬、软件如何支持指令级并行？如何研究这些问题？
- 硬件技术或者软件技术都可以提高指令级并行性
- 必须要硬件技术和软件技术互相配合，才能够最大限度地挖掘出程序中存在的指令级并行
  性能评价：CPI计算
流水线处理器的实际CPI（平均每条指令使用的周期数）等于理想流水线的CPI加上各类停顿引起的周期数的总和
CPI流水线 = CPI理想 + 停顿结构相关 + 停顿先写后读 + 停顿先读后写 + 停顿写后写 + 停顿控制相关
减少其中的任何一种停顿，都可以有效地减少CPI，从而提高流水线的性能

软件和硬件的支持

上述技术中有些技术主要是硬件支持
- 循环展开
- 寄存器换名的动态调度（基本的Tomasulo’s）
- 动态分支指令预测
- 每个周期多发射
- 前瞻技术
所有的技术都必须和软件，特别是编译器合作完成

几个基本概念

基本（程序）块：一段除了入口和出口以外不包含其它分支的线性代码段
- 程序平均每6~7条指令就会有一个分支
- 必须在多个基本块之间开发指令级的并行性
循环级并行：循环体中指令之间的并行性
开发循环级并行的基本技术方法
- 指令调度（scheduling）
- 循环展开（loop unrolling）
- 换名（renaming）

4.1.1 循环展开调度的基本方法

循环展开是展开循环体若干次，将循环级并行转化为指令级并行的技术
这个过程既可以通过编译器静态完成，也可以通过硬件动态进行
- 开发循环级并行性的另外一个重要技术是向量处理技术
- 具有向量处理指令的典型机器是向量计算机，有关向量处理和向量计算机的内容本章不作讨论
本章中的分支指令就是指条件转移指令

本章通用浮点流水线延迟表

编译器在完成这种指令调度时，受限于以下两个特性
- 一是程序固有的指令级并行性
- 二是流水线功能部件的执行延迟
本章中使用的浮点流水线的延迟如下表

流水线其他特性说明

整数流水线采用改进的 MIPS 整数流水线
- 由于数据的取操作的结果可以毫无停顿的通过相关通路机制传送到数据存部件，所以延迟为 0
  - 定向通道或旁路机制
分支指令，由整数流水线执行
- 分支条件检测调整到 ID 段
- 如果分支指令使用上一条指令的结果作为分支条件，将要延迟 1 节拍
- 分支指令有 1 个节拍的延迟槽
浮点运算一般为 64 位
无结构冒险

循环展开实例

对于下面的源代码，在不进行指令调度和进行指令调度两种情况下，分析代码一次循环的执行时间
1
2
for (i = 1; i <= 1000; i++)
x[i] = x[i] + s;

编译过程

每一遍循环之间是不存在相关的
- 多遍循环可以同时执行而不会导致结果的错误
变量分配寄存器
- 整数寄存器 R1 用作循环计数器，初值为向量中最高端地址元素的地址
- 浮点寄存器 F2 用于保存常数 S
- 为简单起见，假定最低端元素的地址为8
  - 否则需要另外的指令来将它和R1做比较

MIPS汇编语言程序

程序转换成MIPS汇编语言程序

Loop:   LD      F0, 0(R1)   ;F0为向量元素
        ADDD    F4, F0, F2  ;加常数F2
        SD      0(R1), F4   ;保存结果
        SUBI    R1, R1, #8  ;修改指针
        BNEZ    R1, Loop    ;循环控制

硬件给编译器更大的空间和支持。编译器用寄存器来进行表达式计算、传递参数、存放变量。

循环无调度执行结果分析
- 每遍循环需要10个时钟节拍
- 只有3个时钟节拍(L.D, ADD.D, S.D)是有效的关键指令
- 有效比率为 30%
- 空转5个时钟节拍 (50%)
- 循环控制2个时钟节拍 (20%)
- 调度代码，减少空转

经过调度后，一次循环仅需 6 个时钟周期便可以完成。

如何进行调度

通过一个好的编译器来调度可以
- 调换 SUBI 和 SD 的位置
- 将 SD 指令移到 BNEZ 的延迟槽内
- 改变 SD 存取指令访问内存地址的偏移量

调度代码结果分析

每遍循环 6 个时钟节拍
和未调度代码比较，加速比 $10/6=1.7$
3个有效时钟节拍 (L.D, ADD.D, S.D)
- 节拍有效比率 50%
- 1拍空转 (占17%)
- 2拍循环控制 (占33%)
如何进一步减少空转和循环控制占用的比率?

循环展开

如果将循环展开3次得到4个循环体(假设向量包含了4的倍数的元素)

Loop:   L.D     F0,0(R1)
        ADD.D   F4,F0,F2
        S.D     0(R1),F4
        L.D     F6,-8(R1)
        ADD.D   F8,F6,F2
        S.D     -8(R1), F8
        L.D     F10,-16(R1)
        ADD.D   F12,F10,F2
        S.D     -16(R1), F12
        L.D     F14,-24(R1)
        ADD.D   F16,F14,F2
        S.D     -24(R1), F16
        DADDUI  R1,R1,#-32
        BNE     R1,R2,Loop

执行时间分析

Loop:   L.D     F0,0(R1)        1
        ADD.D   F4,F0,F2        2,3
        S.D     0(R1),F4        4,5,6
        L.D     F6,-8(R1)       7
        ADD.D   F8,F6,F2        8,9
        S.D     -8(R1), F8      10,11,12
        L.D     F10,-16(R1)     13
        ADD.D   F12,F10,F2      14,15
        S.D     -16(R1), F12    16,17,18
        L.D     F14,-24(R1)     19
        ADD.D   F16,F14,F2      20,21
        S.D     -24(R1), F16    22,23,24
        DADDUI	R1,R1,#-32      25
        BNE     R1,R2,Loop      26,27
        stall                   28

结果分析

循环使用 28 个时钟节拍
- 14 个空转节拍
  - 每个 L.D 有 1 个空转节拍 – 共 4 拍
  - 每个 ADD.D 有 2 个空转节拍 - 共 8 拍
  - DADDUI 有 1 个空转节拍 - 共1拍
  - BRANCH 有 1 个空转节拍 - 共1拍
- 有 14 个指令流出节拍
每遍循环 7 个时钟节拍
共计使用 9 个寄存器
代码量增大

循环展开+指令调度

Loop:   L.D     F0, 0(R1)
        L.D     F6, -8(R1)
        L.D     F10, -16(R1)
        L.D     F14, -24(R1)
        ADD.D   F4, F0, F2
        ADD.D   F8, F6, F2
        ADD.D   F12, F10, F2
        ADD.D   F16, F14, F2
        S.D     0(R1), F4
        S.D     -8(R1), F8
        DADDUI	R1,R1, #-32
        S.D     16(R1), F12
        BNE     R1, R2, Loop
        S.D     8(R1), F16

“循环展开+指令调度”结果分析

每遍循环时间下降为14个时钟节拍
- 每个元素平均使用3.5个时钟节拍
比较
- 循环展开，没有指令调度
  - 每个元素7拍
- 没有循环展开，有指令调度
  - 每个元素6拍

循环展开总结

对指令进行移动是有效的
展开是有用的
用不同的寄存器
- 换名
- 更多的寄存器
消除额外的测试开销
在循环展开时分析 LOAD/STORE 指令进行内存地址换名（动态地址具有不确定性，必须完全算出地址才能继续执行下面的代码，无法像静态地址那样可以预测）
保留真相关
不规整？

4.2 指令的动态调度

编译器本质上通过对每个循环迭代中寄存器重命名来展开循环
硬件也可通过寄存器重命名和乱序执行来获得同样的效果
动态调度
- 记分牌
- Tomasulo’s 算法

4.2.1 冒险的检测和调度

如果存在数据相关，硬件检测机制会做如下的事情直到相关消除动态调度
- 暂停指令
- 停止取指令和发射指令
静态调度（开始于60s，流行于80s）消除动态调度
- 软件来负责调度指令减少空转
动态调度
- 硬件对指令的执行重新排序来减少空转

动态调度

动态调度的目的
- 在程序执行的时候，解决WAW,WAR和RAW带来的冒险
优点：
- 处理在编译的时候未知的相关，简化编译器
- 在不同的流水线上都能有效的运行
缺点：
- 很大地增加了硬件的复杂性
两个动态调度技术
- 记分牌
- Tomasulo 算法

4.2.2 记分牌算法

记分牌 1964 被 Cray 用于 CDC 6600
记分牌允许指令乱序执行，前提：
- 充足的资源，无数据相关
- 记分牌动态解决了写后读（RAW）相关
- 指令可以乱序执行
基本原理
- 每条指令均经过记分牌，记录各指令间数据相关的信息
- 如果记分牌判断出一条指令不能立即执行，它就检测硬件的变化从而决定何时能够执行

记分牌处理

流水线 ID 段被分为两级
- 流出——解析指令，检查结构相关
- 读操作数——直到不存在数据相关时，才读取操作数
如果存在 WAR 或者 WAW 相关，记分牌会暂停这条指令的执行，直到相关消除后才继续执行

记分牌执行过程

流出（Issue）
- 本指令所需的功能部件有空闲
- 正在执行指令使用的目的寄存器与本指令不同
  - 保证 WAW 相关
读操作数（Read operands）
- 前面已流出的还在运行的指令不对本指令的源操作数寄存器进行写操作
- 一个正在工作的功能部件已经完成了对这个寄存器的写操作
- 动态解决 RAW 相关
前面两步完成了原来ID段的功能
执行（Execution）
- 开始于取到操作数后
- 当结果产生后，修改记分牌
- FP 流水部件会占用多个周期
写结果（Write result）：检查 WAR 相关
出现以下情况时，不允许指令写结果：
- 前面的某条指令还没有读取操作数
- 其中某个源操作数寄存器与本指令的目的寄存器相同

记分牌结构

功能部件状态表
- 记录每条指令的功能状态，包括指令类型，使用的功能部件、寄存器，结束时间以及谁将使用该条指令的数据等
用9个域来记录每个功能部件的状态
- Busy：指示功能部件是否工作
- Op：功能部件当前执行的操作
- Fi：目的寄存器编号
- Fj，Fk：源寄存器编号
- Qj，Qk：向Rj，Rk中写结果的功能部件
- Rj，Rk：标示Fj，Fk是否就绪，是否已经被使用

程序实例

指令序列如下：

LD    F6, 34(R2)
LD    F2, 45(R3)
MULTD F0, F2, F4
SUBD  F8, F6, F2
DIVD  F10, F0, F6
ADDD  F6, F8, F2

浮点部件执行时间延迟
- 加（减）法2拍
- 乘法 10 拍
- 除法 40 拍

[Cycle 1]

第一条指令 LD 是访存指令，使用整型功能部件，目的寄存器为 R2，Fk 标记为准备好

[Cycle 2]

第二条指令也是 LD，也是使用整型功能部件，因此无法流出

[Cycle 3]

因为第二条 LD 指令不能流出，因此第三条指令 MULTD 也无法流出

[Cycle 4]

第四个时钟周期后，我们可以得到第一条指令的结果，于是要将第一条指令的整数部件释放掉，将结果写回到 F6 中

[Cycle 5]

第五拍时流出第二条 LD 指令，他使用整数部件，因此 F2 是整数部件作为目标寄存器在使用，查询 R3 有效，并且这条指令占用了目标寄存器 F2。

[Cycle 6]

第六个时钟周期时，乘法功能部件空闲，因此第三条乘法指令 MULTD 可以流出。
然后标记 F2 和 F4 为两个源操作数，但是第一个操作数为立即数，因此标记 F2 为整数功能部件。因为整数功能部件目前正在被使用，因此 F2 的数据没有就绪。

[Cycle 7]

该节拍中，目标地址生成，R3 不再使用，因此把 R3 的标识符设置为空闲（No）。
同时第三条指令 MULTD 的 F2 整数部分还未拿到（整数功能部件还未就绪），因此无法继续执行。
减法使用加法部件（空闲），因此将 Add 标志送给 F8，表示 F8 作为 Add 功能部件的目的寄存器使用，查询 F6，F2 可得，F6 已就绪，F2 使用整数部件，未就绪。

[Cycle 8a（前半拍）]

前半拍时，第二条 LD 指令的结果被读出，即将要写入 F2，但是不能立即就被等待整数功能部件的两个寄存器使用，只有到后半拍的时候才能被供给使用

[Cycle 8b（后半拍）]

前半拍实际上是读 LD 的结果，后半拍将结果写进去
这样第三条和第四条指令的四个源操作数便都就绪了，整数部件使用的目的操作数 F2 也就绪了
第五条除法指令 DIVD 经检查也可以流出：除法部件空闲，目的寄存器为 F10，因此将 F10 打上 Divide 功能部件的标志
使用的两个源操作数 F0被乘法功能部件使用，未就绪，F6 就绪

[Cycle 9]

第三条乘法指令和第四条减法指令的四个操作数都就绪，根据之前的约定，这两条指令可以同时启动
前面约定，乘法指令将使用 10 拍完成，加减法指令使用 2 拍完成，将这两个设置计数器倒计时
第六条加法指令使用加法部件，而加法部件此时正在被减法指令（SUBD）使用

[Cycle 10]

第六条加法指令仍然不能流出，乘法和减法指令执行一拍

[Cycle 11]

在第 11 个时钟周期，乘法和减法指令会被执行两拍，减法指令执行完毕
无其他需要使用 F8 寄存器的指令

[Cycle 12]

减法指令将结果写回 F8 寄存器

[Cycle 13]

流出第六条加法（ADDD）指令，使用 F6 作为目标寄存器，因此将 F6 打上加法（Add）功能部件的标志
F8，F2 都可以就绪

[Cycle 14]

启动加法指令执行，需要两个时钟周期

[Cycle 15]

加法指令还剩一拍，乘法指令计数器还剩 4 拍

[Cycle 16]

求得加法指令结果

[Cycle 17]

这时能否将 F6 写回？需要判断是否有读后写相关
需要扫描所有源寄存器（源记录）阵列，扫描发现在除法指令中 F6 寄存器已就绪，说明还没有被读走，因此该加法指令不能写入 F6，需等待除法指令读取完 F6 后才能写入
该指令存在读后写相关，被阻塞在原地

[Cycle 18]

乘法指令还剩一拍

[Cycle 19]

乘法指令执行完

[Cycle 20]

释放掉 F0，除法指令的源操作数使用的 F0 寄存器就绪
除法指令继续启动

[Cycle 21]

除法指令计数器从 40 开始计数

[Cycle 22]

源寄存器 F6 读完，取消就绪态，加法指令可以写 F6 寄存器

[Cycle 61]

经过 40 个节拍，除法指令执行完毕

[Cycle 62]

将结果写入 F10 寄存器

记分牌最终状态

观察最后的结果，我们发现指令流出是顺序的，读操作数和执行是乱序的，结果写回也是乱序的
指令乱序执行，指令乱序写回

开销和性能提升

CDC6600

|性能提升|编码方式|
|——-|——|
|1.7|FORTRAN|
|2.5|手工汇编|

Condition（CDC6600记分牌）
- 无软件流水调度
- 无主存储器
- 无 Cache
CDC6600 上的记分牌的逻辑电路相当于一个功能部件，器件的耗费是非常低的
但是记分牌需要和每个功能部件进行连线，有了记分牌之后的连线是原来的 4 倍

4.2.3 Tomasulo 算法

IBM 360/91比 CDC6600 晚三年推出
- 商业计算机使用 Cache 技术之前
整个 360 系列仅一个指令系统和一个编译器
- 要求具有很高的浮点性能，但不是通过高端机器的专用的编译器实现
- 只有四个双精度浮点寄存器，编译器调度的有效性受到很大限制
- 访存时间和浮点计算时间都很长
- 可支持循环的多次迭代重叠执行

Tomasulo 算法与记分牌

采用了许多记分牌中的理念
两个较大的差异
- Tomasulo 算法中，冲突检测和执行控制是分布的，利用保留站实现
- Tomasulo 算法不检查 WAR 和 WAW 相关，他们通过算法本身消除掉了

在MIPS上实现算法

360/91 浮点功能单元
- 3个加法单元
- 2个乘法单元
- 6个读单元
- 3个写单元
MIPS和360/91浮点单元的区别
- 360/91: 支持寄存器-存储器指令
- 360/91: 采用流水化功能单元，不采用多个功能单元
每个功能单元都有保留站：缓冲

可以看到，结构中有一个指令队列，指令从队列中流出到各个功能部件，有四个浮点寄存器，三个加法部件，两个乘法部件，三个 store 部件，六个 load 部件
但是只有一个加法器和三个缓冲器，一个乘法器和两个缓冲器，这三个加法缓冲器和两个乘法缓冲器加起来叫保留站（Reservation Station），对于指令队列来说，流出队列并且进入加法器的指令可以有三条，这就相当于有三个加法器，同理，相当于有两个乘法器，三个 store 部件和六个 load 部件
这些缓冲器又称为虚拟功能部件，这样做是为了有更多的部件供请求队列使用

Tomasulo 浮点单元具体执行流程

一条指令流出后，可能是加法或其他类型的指令，该指令将被分配到相应的功能部件，指令开始进入执行阶段
在每一个保留站中，便会记录该指令的操作类型（加法还是减法等）以及两个源操作数，这两个源操作数将从浮点寄存器中读取，如果就绪则成功读取，若没有就绪，则记录谁将产生这个操作数
一旦获得了操作数或者知道了将从哪儿产生这个操作数后，该寄存器对于该部件便没有意义了，相当于将其释放了
操作数从其他部件或从自己部件的保留站中产生，实际上完成了一个指针的调整，记录了一个指针等待这个数据从什么地方过来
当两个操作数都成功得到后，该指令便会被流入到功能部件进行运算，运算完成后将结果送入一条总线上，这个总线叫公共数据总线，该总线是 Tomasulo 算法的枢纽
将数据放入公共数据总线后，所有需要该数据的地方将同时获得该数据，包括保留站和寄存器，供下一条指令使用
获得两个操作数的指令便可以接着执行，相关的检测是在保留站中执行的，没有一个统一的控制电路
数据指针的调整使得寄存器完成了一次换名操作，==由原来的寄存器读数，变成从产生数据的源部件取数==

MIPS五阶段的流水线的改造

ID和EX阶段被以下三个阶段代替
1、流出（Issue）
2、执行（Execute）
3、结果写回（Write result）

流出（Issue）

从浮点指令队列中取出一条指令
如果存在一个空的保留站，就流出这条指令
如果操作数在寄存器中，就送到该指令对应的保留站
存储器取/存指令只要有空闲的缓存就可以流出
如果没有空闲的保留站或者缓存，就存在结构相关，指令暂停，直到有空闲的保留站或者缓存

执行

如果缺少一个或者多个操作数，就监听 CDB
这个阶段实际是检测和自动维护 RAW 相关
如果两个操作数都就绪，这条指令就可以执行

结果写回（Write result）

如果结果已经产生，将其写到 CDB 上
通过 CDB，把这个结果写到目标寄存器和等待这个结果的所有功能单元的保留站

保留站的六个域

Op：对源操作数 S1 和 S2 进行的操作
Qj, Qk：产生本条指令所需要的源操作数的保留站
- 如果值为 0，意味着源操作已经就绪
Vj, Vk：源操作数的值
- V 域和 Q 域不同时有效，表示一旦获得源操作数的值或者获得源操作数的来源，则寄存器便失效
Busy：这个保留站被占用了

寄存器文件和存缓冲都有 Qi 域

Qi：保留站的编号
- 编号所对应产生结果的保留站
- 如果 Qi 为空，就是当前没有指令的结果要写到这个寄存器或者缓冲
Load 缓冲和 Store 缓冲都有
- busy 位
- 地址域
- Store缓冲还有 V 域

$\sum$

程序实例

用以下指令序列来说明 Tomasulo 算法原理
同记分牌算法的指令系列

LD    F6, 34(R2)
LD    F2, 45(R3)
MULTD F0, F2, F4
SUBD  F8, F6, F2
DIVD  F10, F0, F6
ADDD  F6, F8, F2

假设：

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

数据相关

三个 RAW 相关（真数据相关）
- 第二个 LD 与 MULTD 和 SUBD
- 从 MULTD 到 DIVD
- 从 SUBD 到 ADDD

名相关

DIVD 和 ADDD 之间的 WAR 相关（反相关）
- Tomasulo 中通过硬件遍历搜索当前指令的目的寄存器是否和之前指令的源操作数寄存器相同，从而避免读后写相关
第一条 LD 和 ADDD 之间的 WAW 相关（输出相关）

举例

有三个 Add 保留站，两个 Multi 保留站
三个 Load 缓冲

[Cycle 1]

第一条 LD 指令可以流出，使用一个 Load 功能部件

[Cycle 2]

Load 功能部件还有剩余，并且使用 F2 作为目标寄存器，因此可以流出，并在 F2 上打上 Load2 标志
第一条 LD 指令进行地址相加计算，进行访存（？）

[Cycle 3]

第三条指令 MULTD 使用一个乘法保留站，目的寄存器为 F0，将 F0 打上 Mult1 标志
检查两个源寄存器 F2 和 F4，F2 未就绪，记录 F2 被 Load1 使用
F4 就绪
MULTD 进入等待状态
第一条 LD 指令进入地址计算阶段

[Cycle 4]

第一条 LD 指令结果写回，释放 Load1
第二条 LD 指令也进入地址计算阶段
第四条指令 SUBD 是减法指令，使用加法保留站，有空闲单元，可以流出，目的寄存器为 F8，将 F8 打上 Add1 的标志（先判断是否能流出，在将寄存器打上标志）
在第一个加法保留站中记录操作类型为 SUBD
检查目的操作数 F6 和 F2，发现 F2 正在被 Load2 使用，进行标记
F6 来自 LD 指令写回的值，通过 CDB 进行传送，写到所有等待该数据的保留站中，于是 F6 就绪

[Cycle 5]

第二条 LD 指令写回 F2，通过 CDB 传送给 Mult1 中的 F2，第三条指令 MULTD 的两个操作数就绪，开始执行
第四条 SUBD 指令的 F2 也在等待数据，因此 F2 也要传送给 Add1 保留站，于是该指令两个操作数准备就绪，开始执行
第五条指令 DIVD 使用乘法功能部件，Multi2 空闲，可以流出，目的寄存器 F10 空闲，打上 Mult2 标志
检查源操作数 F0 和 F6，检查 F0，记录正在被 Mult1 使用
F6 准备就绪
对于加法和乘法指令，需要使用局部计数器完成对整个运算的计数，Add1 设置计数器为 2，Mult1 设置计数器为 10

[Cycle 6]

Add1 和 Mult1 分别完成一拍的计算，还剩 1 和 9
第六条指令 ADDD 是加法指令，加法保留站有空闲，可以流出
ADDD 目标操作数是 F6，F6 空闲，将 F6 打上 Add2 标签
检查源操作数 F8 和 F2，检查发现 F8 由 Add1 产生结果，未就绪，F2 已就绪

[Cycle 7]

加法保留站 Add1 的计数器为0，表示第四条指令 SUBD 已经完成运算

[Cycle 8]

第八拍时，SUBD 将结果写回 F8，同时写到 CDB 上
检查到 Add2 的一个目的寄存器使用 Add1 输出的结果，因此 Add1 同时将数据通过 CDB 输出到 Add2，ADDD 两个源操作数准备就绪，开始执行，设置计数器为 2

[Cycle 9]

Add2 计数器还剩 1，Mult1 计数器还剩 6

[Cycle 10]

Add2 计数器为 0，计算完成

[Cycle 11]

ADDD 的结果写回 F6，同时送入公共数据总线，除了 Add2，没有其他保留站等待该数据
Mult1 还剩四拍计算完成

[Cycle 12-14]
图略，等待 MULTD 计算完成

[Cycle 15]

MULTD 计算完成

[Cycle 16]

使用第一个乘法器（Mult1）结果的有两个地方：一个是第二个乘法部件 Mult2，第二个是 F0 寄存器
Mult2 获得 F0 结果后，DIVD 两个寄存器都准备就绪
DIVD 指令开始计算，设置计数器为 40

[Cycle 55]

除法还剩一个节拍

[Cycle 56]

除法执行完成

[Cycle 57]

将结果写回 F10

算法分析

指令流出是顺序的，但是执行结束的顺序是乱序的，写结果的顺序也是乱序的
Tomasulo 算法特点：有序流出，乱序执行，乱序结束
可以将优先获得资源并且可以执行的指令优先结束

Tomasulo算法的优点

分布式硬件冲突检测
利用保留站和缓冲完成寄存器换名，彻底消除 WAW 和 WAR 这两种名相关
如果多个保留站等待同一个操作数，当操作数在 CDB 上广播时，他们可以同时所需的数据

动态调度方法评价

动态方法能够达到很高的性能
主要缺陷
- 高复杂性：需要大量硬件
- 存在瓶颈：单个公共数据总线（CDB）引发竞争
  - 额外的 CDB：在每个保留站上需要为每条 CDB 设置重复的硬件接口
  - 现代计算机一般有 3 条 CDB，1 条全局，2 条局部（单独连浮点寄存器和保留站）

4.3 控制相关的动态解决技术

动态分支预测的两个理由
- n流出的处理器加速上限为n倍
- Amdahl定律提示：在较低CPI机器上，控制相关导致的空转对机器性能影响大
前面解决控制相关的静态策略
- 需要编译器将一条或多条指令移动到流水线产生的分支延迟槽中
关于分支预测策略的两部分工作
- 预测的分支是否成功
- 执行分支目标指令

4.3.1 分支预测缓冲

预测的准确率
分支的开销
- 预测正确的开销
- 预测错误的开销

分支预测缓冲(BPB)

最简单的分支预测策略
分支预测缓冲是一个小的存储器阵列
- 每个单元只有 1 位，记录最近一次分支是否成功的信息
- 预测位为1则预测分支成功，并从目标位置开始取指令
- 单元由分支指令地址的低位索引进行寻址
- BPB 的预测位会被具有相同低位地址的分支设置
BPB也被称为 BHP（branch history buffer 分支历史缓冲）

1 位 BPB

1 位 BPB 状态图

这种单位预测策略有大约 80% 左右的准确率
- 当分支不成功时，单位预测会连续失败两次
- 2 位预测策略能够改善这种情况

2 位 BPB

2 位 BPB 状态图

在 2 位预测策略中，一个预测必须错误两次才会改变
对于一个 4096 条记录的 BPB，利用 2 位预测策略，用 SPEC89 测试，命中率为 82% 到 99%
- 准确率最高的测试程序一般包含大量循环
- 线性代码一般准确率最差

另一种转换图：

4096 单元 2 位 BPB 的预测准确率

测试程序为 SPEC89
整数测试程序: 平均 11%
- gcc, espresso, eqntott, li
浮点测试程序: 平均 4%
- nasa7, matrix300, tomcatv
为什么?
- 因为整数程序线性代码较多
- 浮点主要用于计算，循环程序更多

n 位 BPB

1 位或 2 位 BPB 是 n 位 BPB 的特殊情况
n 位策略使用计数器，表示 0~2^n^-1 的值
与 2 位策略类似，对于 n 位 BPB，每次分支成功，计数器 +1，反之则 -1
如果计数器值大于其最大值的一半，则做成功预测，反之则做失败预测
4K 个单元的 BPB 和无穷单元的 BPB 最后结果相差无几

BPB 实现

BPB的实现方案
- 实现一个小而特殊的“cache”，利用指令地址进行索引，在 IF 流水段访问。
- 或者，为指令 cache 中每一块增加附加位，与指令一起取出
若一个指令在 ID 段被译码为分支指令，且对应的BPB标志位预测其成功，则
- 一旦 PC 已知，立刻从分支目标位置开始取指
- 或者，继续顺序取指

4.3.2 分支目标缓冲(BTB)

另一个动态分支预测方法：分支目标缓冲
- Branch Target Buffer, BTB
- 为了减小或消除流水线的分支开销，我们需要在 IF 段结束前知道从哪个地址开始取下一条指令
- 换句话说，我们在 IF 段就需要知道这条未译码的指令是否为分支指令，并且如果它是分支指令，要尽快知道 NPC 值应当为多少
- 这个缓冲机制中保存以前分支成功的分支指令的地址，等到下一次在遇到这条指令的时候，当前指令的地址将会和缓冲中保存的分支指令地址进行比较，若相同，则认为当前指令就是曾经执行过的分支成功的指令，因此预测下一次该指令仍然分支成功

BTB 实现

分支目标缓存 BTB 每个单元应该包括
- 分支指令的地址
- 分支目标的地址
- 分支预测标识
取指阶段，所有指令地址都与 BTB 中保存的分支指令的地址做比较，一旦相同，就认为本指令是分支指令，并且分支成功
它的目标地址就是保存在缓冲区中的分支目标地址
- 取出后直接送入 NPC

执行过程

当前指令的 PC 将和 BTB 中的 PC 值进行遍历比较，如果有相同的项，那么就认为该指令是曾经成功的分支指令，他的分支目标地址放在列==分支目标PC==中
然后将分支目标PC取出直接放入 PC 寄存器，从该地址取出下一条指令执行
- BTB 可以进一步优化，将分支目标指令也存放在缓冲中，加快指令的读取
如果没有命中，则认为他是普通指令，正常执行
若分支预测成功、不是分支指令或者不在 BTB 中且分支不成功，则流水线无延迟

BPB VS. BTB

分支预测技术（BPB）受限于预测精度，以及预测失效后产生的开销，预测精度为 80% 左右
根据不同程序特点以及缓冲区的大小，典型的BTB可以实现 80% 到 95% 的预测精度
降低失效开销技术：在一个时钟周期内同时取出不同分支路径的指令，即把分支成功和失败的指令都取出来
- 会引入其他开销，比如存储系统的端口加倍
- 降低失效开销的唯一方法，比如
  - AS/400 PowerPC 处理器，多分支预测技术

分支预测局限性

预测准确性：80%-90%
预测性能依赖于
- 程序类型
- 缓冲区大小
预测失效开销的优化
- 预取不同分支路径指令
  - 存储端口数目加倍,交叉存取缓冲
- 在目标缓冲中缓冲多个路径的指令

4.4 多指令流出技术

多指令流出处理器
- 实现一个时钟周期内流出多条指令时
- 达到 CPI 小于1
多流出处理器 2 种基本结构
- 超标量（Superscalar）
  - 超标量每个时钟周期流出的指令数不定
  - 可以编译器静态调度，也可以硬件动态调度
- 超长指令字（VLIW，Very long Instruction Word）
  - 每个时钟周期流出的指令数是固定的，只能通过编译静态调度

4.4.1 超标量处理机

超标量处理机的原型来自于 IBM 实验室的 “America”处理器
- RS/6000 第一个采用超标量技术
- 现在，几乎所有高性能处理器都是用该技术
超标量处理机的硬件支持每个时钟周期发出 1-8 条不存在相关的指令
- 如果指令流中的指令相关或不满足限制条件，则只能流出这条指令前面的指令，因此超标量处理器流出的指令数是不定的

超标量处理器

假设有这样一个简单的超标量处理器，每个时钟周期它可以流出两条指令
- 一条指令可以是取指令、存指令、分支指令或整数运算操作
- 另一条指令可以是任意的浮点操作
- 第一条指令排在第二条指令的前面
- 这种配置与 HP 7100 结构类似

超标量处理机的理想执行情况

超标量处理机的技术问题

每个时钟周期流出两条指令意味着取指令和解码部件都是64位
- 假设：指令按要求组合成对，且与 64 位边界对其，整数指令顺序在前
- 需要使得浮点部件流水化或增加相关部件来减少结构相关
另一个限制超标量流水线性能发挥的障碍是取操作和分支操作的延迟
- 分支指令肯定是指令组合的第一条指令，影响配对指令和后续两条指令，分支延迟也变为 3 条指令

超标量处理器举例

为了能有效利用超标量处理器的可获得的并行度，需要采用更有效的编译技术、硬件调度技术和更复杂的指令译码技术
- 循环展开成5个副本

使用先前我们用到的代码作为例子

LOOP  LD    F0, 0(R1)   ;取出一个向量单元.
      ADDD  F4, F0, F2	;与F2寄存器中的标量相加
      SD    0(R1), F4   ;保存相加后的向量单元
      SUBI	R1, R1, #8  ;R1寄存器值减8
      BNEZ 	R1, LOOP    ;如果R1值不为0，则跳转

超标量：例子执行情况

在超标量流水线上对上述代码进行调度，以获取更多地指令机并行度

超标量：例子结果分析

每次循环需 12 个时钟周期
每个迭代为 2.4 个时钟周期
- 前面在普通的流水线上，通过循环展开和调度，可以达到每个迭代为 3.5 个时钟周期
超标量可以获得更好地性能，代价是硬件复杂性大幅度增加

4.4.2 超长指令字技术

一台超标量机器每周期能够流出4-8条指令
- 由于必须要用硬件分析指令间的相关，为其实现带来了困难
另一种选择：长指令字（LIW，Long Instruction Word）或称为超长指令字（VLIW，Very Long Instruction Word）体系结构
- 第一种商用 LIW 机器是 AP-120B，由 Floating Point Systems 开发
- FPS-164 是较新的机器，它的每个指令字含有对应于 10 个不同功能单元的 10 条指令

VLIW基本机构

VLIW 采用多个独立的功能单元，多个不同的操作封装在一条长指令字中，每个功能单元在 VLIW 指令中都有一定的对应区域
- 一般每个功能单元占用 16-24 位
- 例如：2个整数、2个浮点、2个访存、1个分支，则该指令的长度为 112-168位
VLIW 硬件只是简单地将指令字中对应的部分送给各个功能单元，功能单元在哪一个时钟周期执行什么操作由编译器来确定
- 如果某个功能单元在某个周期没有任务，则执行 NOP（空操作）指令

VLIW例子

再次使用先前在解释循环展开及超标量机器时使用过的那段循环代码，来解释VLIW如何工作这一次，我们将循环展开n个副本
VLIW机器每条指令字包含
- 两个访存操作
- 两个浮点操作
- 一个整数或分支操作
得到如下指令序列

5 条结果在 8 个时钟周期中完成计算
- 每条结果花费 1.3 时钟周期，比超标量性能更高
- 有 17/40 的指令槽被放入了有效的操作，利用率很低

当循环展开为 7 次时：

9 拍产生 7 个结果
- 每个结果 1.29 拍
- 比前面的超标量，每个结果 2.4 拍，快接近2倍
9 拍里面执行了 23 个操作
- 2.5 操作/拍
- 指令槽利用率不高，只有 51% (23/45)
使用大量寄存器
7 个循环，共计使用 2×7+1=15 个 64 位浮点寄存器

如果我们想减少循环展开的次数，则至少展开三次才能保证流水线中没有空周期：

8 拍 3 个结果，每个结果 2.66 拍
指令槽利用率: 11/40 = 27.5%
寄存器：3×2+1=7 个 64 位浮点寄存器

如果我们想尽可能充满指令槽，可以展开 10 次：

10 拍 10 个结果，每个结果使用 1 拍
指令槽利用率：36/50 = 72%
寄存器需求：10×2+1=23 个 64 位浮点寄存器
- 当前 MIPS 只有 16 个 64 位浮点寄存器或 32 个 32 位寄存器，已经超过了要求

VLIW的技术难题

第一，从线性代码片段中产生足够的操作需要进行激进的循环展开，这增大了代码大小
第二，无论指令是否被充满，没有被使用的功能单元也在指令字编码过程中占据了相应的位，也就是说将近一半的指令槽是被浪费掉的，这不仅浪费运算资源，还占用了大量存储空间
- 解决方式：在主存中压缩指令，在 cache 中解压缩指令
第三，VLIW 带来了二进制代码兼容性问题
- 若采用 2 个浮点部件和 3 个浮点部件，将带来二进制指令代码不兼容
- 采用模拟的方法解决

4.5 第四章指令级并行总结

4.1 指令级并行的概念
- 循环展开调度的基本方法
  - 解决跨基本块的指令调度
  - 通过寄存器换名技术解决名相关
4.2 指令的动态调度
- 记分牌
  - 通过硬件解决数据相关
- Tomasulo算法
  - 还可以解决控制相关引发的问题
  - 可以很好解决循环展开的问题，由硬件完成寄存器换名，减少空周期
4.3 控制相关的动态解决技术
- 分支预测缓冲
  - 以较小的存储代价和 1 拍的时间延迟进行分支指令的历史预测，提高机器执行效率
- 分支目标缓冲
  - 通过保存分支指令和分支目标的地址，实现没有空转周期的分支预测
- 这两者都是基于历史信息来进行预测的，分支目标缓冲需要更大的存储空间
  - 现在的机器上一般将两者结合使用：使用几十上百个分支目标缓冲和若干 K 个分支预测缓冲
  - 这样可以很好的实现控制相关的动态预测，将失效率降低到 10% 左右
4.4 多指令流出技术
- 超标量技术
  - CPI < 1
  - 指令流出一般在 3-6 条
- 超长指令字技术
  - 依赖编译器的静态多指令流出技术
  - 通用领域技术不够成熟

第四章 指令集并行

4.1 指令集并行的概念

4.1.1 循环展开调度的基本方法

流水线其他特性说明

循环展开实例

MIPS汇编语言程序

循环无调度执行结果分析- 每遍循环需要10个时钟节拍- 只有3个时钟节拍(L.D, ADD.D, S.D)是有效的关键指令 - 有效比率为 30% - 空转5个时钟节拍 (50%) - 循环控制2个时钟节拍 (20%)- 调度代码，减少空转

循环展开

循环展开+指令调度

4.2 指令的动态调度

4.2.1 冒险的检测和调度

4.2.2 记分牌算法

记分牌处理

记分牌执行过程

记分牌结构

程序实例

4.2.3 Tomasulo 算法

Tomasulo 算法与记分牌

在MIPS上实现算法

Tomasulo 浮点单元具体执行流程

MIPS五阶段的流水线的改造

程序实例

举例

算法分析

4.3 控制相关的动态解决技术

4.3.1 分支预测缓冲

分支预测缓冲(BPB)

1 位 BPB

2 位 BPB

n 位 BPB

BPB 实现

4.3.2 分支目标缓冲(BTB)

BTB 实现

4.4 多指令流出技术

4.4.1 超标量处理机

超标量处理器

超标量处理机的技术问题

超标量处理器举例

超标量：例子执行情况

超标量：例子结果分析

4.4.2 超长指令字技术

VLIW基本机构

VLIW例子

4.5 第四章指令级并行总结

第四章指令集并行

循环无调度执行结果分析
- 每遍循环需要10个时钟节拍
- 只有3个时钟节拍(L.D, ADD.D, S.D)是有效的关键指令
- 有效比率为 30%
- 空转5个时钟节拍 (50%)
- 循环控制2个时钟节拍 (20%)
- 调度代码，减少空转