国防科大计算机体系结构公开课_04指令级并行

国防科大计算机体系结构公开课学习笔记。

第四章:指令级并行。
我爱张春元教授(第三章和第四章的主讲老师)!真正做到了深入浅出、有逻辑、成体系,收获很深~~ 😛

2019/5/3:体…系…结…构…好…难…啊…………之…前…信…誓…旦…旦…说…入…个…门…儿…so…easy…………现…在…心…态…就…崩…了…呢…………崩…了…………崩…了…………

指令级并行

当指令之间不存在相关时,它们在流水线中是可以重叠起来并行执行的。这种指令序列中存在的潜在并行性称为指令级并行。Instruction-level Parallelism (ILP)。

  • 另:任务级并行、线程级并行,这两种并行是一种显式的并行。
    $CPI_{流水线} = CPI{理想} + Pause_{结构相关} + Pause_{先写后读} + Pause_{先读后写} + Pause_{写后写} + Pause_{控制相关}$
    所以,为了提高流水线性能,应减少相关带来的停顿。
技术 主要克服的停顿
基本流水线调度 数据先写后读相关停顿
循环展开 控制相关停顿
寄存器换名 数据写后写和先读后写相关停顿
指令动态调度(记分牌和 Tomasulo 算法) 各种数据相关停顿
动态分支预测 控制相关停顿
前瞻 (Speculation) 所有数据/控制相关停顿
多指令流出(超标量和超长指令字) 提高理想 CPI

循环展开和寄存器换名

基本(程序)块:一段除了入口和出口外不包括其他分支的线性代码段。

  • 在多个基本块之间开发指令级并行。
    循环级并行:循环体中指令之间的并行。
  • 指令调度 (scheduling)
  • 循环展开 (loop unrolling):展开循环体若干次,将循环级并行转化为指令级并行的技术 —> 向量处理技术

以如下代码为例:

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

对应的 MIPS 汇编代码如下所示:

1
2
3
4
5
Loop:   L.D     F0, 0(R1);  F0 为向量元素
ADD.D F4, F0, F2; 加常数 F2
S.D 0(R1), F4; 保存结果
SUBI R1, R1, #8; 修改指针
BNEZ R1, Loop; 循环控制

由于浮点存取和计算后有延迟,所以在未调度状态下存在空转情况,十个时钟节拍中仅有三个时钟节拍是真正在做计算,剩下的要么空转要么在做循环控制 —> 如何充分利用这些空转间隙?

时钟 未调度 调度后
1 L.D F0, 0(R1) L.D F0, 0(R1)
2 Stall DADDUI R1, R1, #-8
3 ADD.D F4, F0, F2 ADD.D F4, F0, F2
4 Stall Stall
5 Stall BNEZ R1, Loop
6 S.D 0(R1), F4 S.D 8(R1), F4
7 DADDUI R1, R1, #-8
8 Stall
9 BNEZ R1, Loop
10 Stall ·

—> 如何进一步减少空转和循环控制占用的比率?循环展开。
如果将循环展开 3 次得到 4 个循环体(假设向量包含了 4 的倍数的元素)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
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

执行时间分析:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
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

循环展开后,寄存器使用量和代码体量都变大了
—> 循环展开+指令调度:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
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 拍完成了 14 条指令执行。
由于循环展开需要消耗更多的寄存器,所以需要分析 LOAD/STORE 指令,进行内存地址换名。
展开时要保留写后读相关。

指令的动态调度

编译器本质上通过对每个循环迭代中寄存器重命名来展开循环。硬件也可通过寄存器重命名和乱序执行来获得同样的效果:记分牌和 Tomasulo 算法。
冒险:是指在计算机CPU的微体系结构中,指令流水线乱序执行中的一些问题可能会导致得到不正确的计算结果。有 3 类典型的冒险:数据、结构、控制。(跟相关对应)
动态调度可以解决以上三类冒险,但是很大地增加了硬件的复杂性。

记分牌 Scoreboard

记分牌允许指令乱序执行,动态解决了先写后读相关。基本原理:

  • 每条指令均经过记分牌,记录各指令间数据相关的信息
  • 如果记分牌判断出一条指令不能立即执行,它就检测硬件的变化从而决定何时能够执行。
    流水线 ID 段被分为两级:
  • 流出——解析指令,检查结构相关。保证 WAW 相关
    • 本指令所需的功能部件有空闲
    • 正在执行的指令使用的目的寄存器与本指令不同
  • 读操作数——直到不存在数据相关时,才读取操作数。动态解决 RAW 相关
    • 前面已流出的还在运行的指令不会对本指令的源操作数寄存器进行写操作
    • 一个正在工作的功能部件已经完成了对这个寄存器的写操作

如果存在 WAR 或者 WAW 相关,记分牌会暂停这条指令的执行,直到相关消除后才继续执行。

记分牌执行过程:

  1. 流出
  2. 读操作数
  3. 执行。当结果产生后,修改记分牌。FP 流水部件会占用多个周期;
  4. 写结果:检查 WAR 相关,出现以下情况时不允许指令写结果
  • 前面的某条指令还没有读取操作数
  • 某个源操作数寄存器与本指令的目的寄存器相同

记分牌会使用功能部件状态表,用 9 个域来记录每个功能部件的状态。
读操作数、执行、写结果均为乱序。Issue 是有序的。
记分牌具体执行过程要再自己看一下

Tomasulo 算法

基于记分牌算法的优化。不同点在于:

  • Tomasulo 算法中,冲突检测和执行控制是分布的,利用保留站(缓冲)来实现;
  • Tomasulo 算法不检查 WAR 和 WAW 相关,而是通过算法本身直接消除掉了。

ID和EX阶段被以下三个阶段代替:

  1. 流出(Issue)
  • 从浮点指令队列中取出一条指令
  • 如果存在一个空的保留站,就流出这条指令
  • 如果操作数在寄存器中,就送到该指令对应的保留站
  • 存储器取/存指令只要有空闲的缓存就可以流出
  • 如果没有空闲的保留站或者缓存,就存在结构相关。指令暂停,直到有空闲的保留站或者缓存。
  1. 执行(Execute)
  • 如果缺少一个或者多个操作数,就监听 CBD。这个阶段实际是检测和自动维护 RAW 相关;
  • 如果两个操作数都就绪,这条指令就可以执行。
  1. 结果写回(Write result)
  • 如果结果已经产生,将其写到 CBD 上
  • 通过 CDB,把这个结果写到目标寄存器和等待这个结果的所有功能单元的保留站

有序流出,乱序执行,乱序结束。

<<< 以上两个算法都是计算机使用 Cache 之前推出的。
动态调度方法能够达到很高的性能,但是具有高复杂性,需要大量硬件支持;并且单个公共数据总线(CDB)会引发竞争。若设置额外的 CDB,则需要在每个保留站上为每条 CDB 设置重复的硬件接口。

控制相关的动态解决技术

Amdahl 定律告诉我们,在较低 CPI 的机器上,控制相关导致的空转对机器性能的影响很大。
分支预测有两种:

  • 预测分支是否成功
  • 预测分支目标在什么地方

分支预测缓冲 BPB/BHB (Branch History Buffer)

  1. 1 位分支预测:用 1 位记录最近一次分支是否成功,然后假定下一次分支仍成功。准确率约 80%。

  • 存在的问题:当分支不成功时,单位预测会失败两次。—>改善:2 位预测策略
  1. 2 位分支预测:必须有两次成功/失败,才会发生状态迁移。


推广:N 位。

分支目标缓冲 BTB (Branch Target Buffer)

为了减小或消除流水线的分支开销,需要在 IF 段结束前知道,下一条未译码的指令是否为分支指令,并且如果它是分支指令,要尽快知道 NPC 值应当为多少。
实现:设计缓冲区保留以前分支成功的分支指令的信息。
分支目标缓存 BTB 单元内容包括:

  • 分支指令的地址
  • 分支目标的地址
  • 分支预测标识

取指阶段,所有指令地址都与 BTB 中保存的分支指令的地址做比较,一旦相同,就认为本指令是分支指令,并且分支成功。它的目标地址就是保存在缓冲区中的分支目标地址,取出后直接送入 NPC。

BPB 和 BTB 预测的性能均依赖于程序类型和缓冲区大小。

多指令流出技术

超标量 (Superscalar)

超标量每个时钟周期流出的指令数不定,可以编译器静态调度,也可以硬件动态调度。
现在几乎所有高性能处理器都是采用该技术。

超标量处理机的硬件支持每个时钟周期发出 1-8 条不相关的指令

  • 如果指令流中的指令相关或不满足限制条件,则只能流出这条指令前面的指令,因此超标量处理器流出的指令数是不定的。

举例:

循环展开成 5 个副本。

硬件复杂度大大提升。

超标量必须要用硬件分析指令间的相关,为实现带来了困难。—>解决:所有指令流出时,由软件编译器对其进行指定位置的流出。

超长指令字 (VLIW, Very Long Instruction Word)

每个时钟周期流出的指令数是固定的,只能通过编译静态调度。

VLIW 采用多个独立的功能单元,多个不同的操作封装在一条长指令字中,每个功能单元在 VLIW 指令中都有一定的对应区域。
VLIW 硬件只是简单地将指令字中对应的部分送给各个功能单元,功能单元在哪一个时钟周期执行什么操作由编译器来确定。如果某个功能单元在某个周期没有任务,则执行 NOP 指令。

举例,同样是上面的代码,假设循环开展成 5 个副本:

5 条结果在 8 个时钟周期中完成了计算。

存在的问题:无论指令是否被充满,没有被使用的功能单元也在指令字编码过程中占据了相应的位。将近一半的指令是被浪费掉的

  • 解决:在主存中压缩指令,在 cache 中解压缩指令。