第三章指令级并行

开发ILP的方法

资源重复（堆硬件）
时间重叠（流水线）
基于硬件的动态开发
基于软件的静态开发

基本块

一串连续的代码除了出口和入口外没有分支和转入点，称为基本程序块

为了明显提高性能，必须跨基本块开发ILP

再谈相关&ILP

相关是程序固有的属性，而相关导致的冲突是流水线的属性

保持相关，避免发生冲突
通过代码变换消除相关

第二章提到的静态调度，就是保持相关，避免发生冲突的方法。

但是，并不意味着保持相关就一定要保持程序顺序，只有可能导致错误时，才一定要严格限制程序顺序。

保持程序正确性

数据流

数据流(Data Flow)是指数据值从其产生者指令到其消费者指令的实际流动。分支指令使得数据流具有动态性，因为一条指令有可能数据相关于多条先前的指令。分支指令的执行结果决定了哪条指令真正是所需数据的产生者。
异常行为

保持异常行为(Exception Behavoir)是指：无论怎么改变指令的执行顺序，都不能改变程序中异常的发生情况。即原来程序中是怎么发生的,改变执行顺序后应该还是那样发生。
这个条件经常被弱化为：指令执行顺序的改变不能导致程序中发生新的异常。

有时，不遵守控制相关既不影响异常行为，也不改变数据流。这时就可以大胆地进行指令调度,把失败分支中的指令调度到分支指令前。

指令的动态调度

与静态调度的比较

静态调度在编译时完成，而动态调度在运行时进行
静态调度通过编译器（软件）完成，而动态调度通过硬件完成
动态调度可以解决一些运行时问题（编译时情况不明），简化编译器；还可以将面向特定流水线的代码在其他使用动态调度的机器上高效运行
当然，动态调度的硬件复杂性增加

引入

第二章五段流水线中，关于结构冲突和数据冲突的检测在ID段（译码）进行，配合前面stall后面全部都要stall的规则，会使无关语句也滞后。

为此，将ID段分为以下两段：

流出（issue，IS）

进行指令译码，以及检测结构冲突，无结构冲突就可以流出
读操作数（read Operathd，RO）

检测数据冲突，等待冲突消失后读操作数

这样，就可以让指令顺序流出，乱序执行，这也是指令级并行的特征

也就是说，可能同时有多条指令处于执行阶段。

但是，会引发之前不会发生的WAW、WAR冲突

保持了正确的异常行为，动态调度处理机也可能发生不精确异常

精确异常：发生异常时，处理机的现场跟严格按程序顺序执行时指令i的现场相同

不精确异常：当执行指令之导致发生异常时,处理机的现场(状态)与严格按程序顺序执行时指令i的现场不同

之所以会发生不精确异常，是因为当发生异常(设为指令i）时：①流水线可能已经执行完按程序顺序是位于指令i之后的指令；②流水线可能还没完成按程序顺序是指令i之前的指令。

典型的动态调度算法

计分牌

使用集中控制
最早出现于CDC 6600
把ID段分成两个段：流出和读操作数；允许多条指令同时处于执行段。记分牌全面负责和管理这指令的流
出和执行，也包括检测所有的冲突。在没有结构(资源)冲突时，尽可能早地执行没有数据冲突的指令。如果某条指令被暂停，，而后面的指令与流水线中正在执行或被暂停的指令都不相关，，那么这些指令就可以跨越它们，继续流出和执行下去(out oforder).

构成

仅用于浮点部件
2个乘法器（Multi1，Multi2）
1个加法器（Add）
1个除法器（Divide）
一个整数部件（Integer）

步骤

流出

如果当前流出指令所需的功能部件空闲，并且所有其他正在执行的指令的目的寄存器与该指令不同，计分牌就向功能部件流出该指令，并修改记录表。
即：如果存在结构相关或WAW冲突，指令不流出 - 解决了WAW冲突，当然也阻止了后面指令的流出。
读操作数

记分牌监测源操作数的可用性，一旦数据可用，它就通知功能部件从寄存器读出源操作数开始执行，否则等待 - 动态地解决了RAW冲突
数据可用：
如果所有前面已流出且还在执行的指令都不对该寄存器进行写操作，就认为该寄存器可用
执行

取到操作数后就开始执行，产生结果后，通知计分牌已经完成执行
写结果

计分牌一旦知道执行部件完成了执行，就检测是否发生WAR冲突
如果不存在WAR冲突，或者原有的WAR冲突已消失，计分牌就通知功能部件把结果写入目的寄存器，并释放指令使用资源

如果检测到WAR冲突，就不允许该指令将结果写到目的寄存器，计分牌等待直到WAR消失。这发生在以下情况：前面的某条指令（按顺序流出）还没有读取操作数，而且其某个源操作数寄存器与本指令目的寄存器相同

表

记录指令执行状态表
功能部件状态表
寄存器状态

例子

特点

可实现Out of Order
有WRW冲突和结构冲突不能流出
有WAR冲突也只能等待
无Forwarding硬件机制

Tomasulo（CDB公共数据总线法、令牌法）

使用分散控制
核心思想：记录和检测指令相关，操作数一旦就绪就立即执行，把发生RAW冲突的可能性降到最小
通过寄存器换名来消除WAR冲突和WAW冲突（都是后写类型）

结构

注意保留站，能够保存一条已经流出并等待到本功能部件执行的指令

操作码
操作数
用于检测、解决冲突的信息

浮点加法器有三个保留站（ADD1，ADD2，ADD3），浮点乘法器有两个保留站（MULT1，MULT2）

步骤

流出

从指令队列的头部取一条指令。
如果该指令的操作所要求的保留站有空闲的,就把该指令送到该保留站(设为r)。
- 如果其操作数在寄存器中已经就绪,就将这些操作数送入保留站r。
- 如果其操作数还没有就绪,就把将产生该操作数的保留站的标识送入保留站r。
  一旦被记录的保留站完成计算,它将直接把数据送给保留站r。
  
  (寄存器换名和对操作数进行缓冲,消除WAR冲突)
完成对目标寄存器的预约工作

(消除了WAW冲突)

如果没有空闲的保留站,指令就不能流出。

(发生了结构冲突)
执行

当两个操作数都就绪后，本保留站就用相应的功能部件开始执行指令规定的操作。

load和store指令的执行需要两个步骤：
- 计算有效地址（要等到基地址寄存器就绪）
- 把有效地址放入load或store缓冲器
换句话说，需要两个周期执行完load/store指令
写结果

功能部件计算完毕后，就将计算结果放到CDB上，所有等待该计算结果的寄存器和保留站（包括store缓冲器）都同时从CDB上获得所需要的数据。

做题切记：获得后下一个周期才开始执行

表

记录指令执行状态表
保留站表
寄存器状态

特点

可实现Out of Order
消除了计分牌的缺陷——消除了WAW和WAR冲突导致的停顿

使用保留站进行寄存器换名,并且操作数一旦就绪就将之放入保留站。
冲突检测逻辑是分布的，通过保留站和CDB实现，而不像计分牌一样集中实现

如果有多条指令已经获得了一个操作数,并同时在等待同一运算结果,那么这个结果一产生,就可以通过CDB同时播送给所有这些指令,使它们可以同时执行。

动态分支预测

在程序运行时，根据分支指令过去的表现来预测其将来的行为。

与静态固定预测成功/失败不同，动态分支预测是会根据分支行为进行实时的预测调整。

分支预测的有效性取决于：

预测的准确性，预测正确和不正确两种情况下的分支开销

在分支预测失败时，要作废已经预取和分析的指令，恢复现场，并从另一条分支路径重新取指令；显然，需要在执行预测的目标指令前，将现场保存。

决定分支开销的因素

流水线的结构
预测的方法
预测错误时的恢复策略等

目的

采用动态分支预测的目的是：

预测分支是否成功
尽快找到分支目标地址/指令，避免控制相关造成流水线停顿

方法一：采用分支历史表（BHT，branch history table）

最简单的动态分支预测方法，使用BHT记录最近几次的分支执行结果，据此进行预测

可以称这个过程为“两次变换”规则，只有连续两次分支执行情况相同，才会改变分支预测结果

BHT两位预测的操作

分支预测

BHT会在分支指令到达ID译码段时被读出，以进行预测

若预测分支失败，则代码会从判断分支指令后开始运行；若分支实际成功，则需要作废已经预取和分析的指令，恢复现场，并从成功分支路径重新取指令。

若预测分支成功，则代码会从成功分支路径开始运行；若分支实际失败，则需要作废已经预取和分析的指令，恢复现场，并从失败分支路径重新取指令。
状态修改

BHT的生效场景

BHT只对分支是否成功进行预测，而没有预测分支的目标地址

只猜对不对，没有猜在哪里

因此，BHT适用于判定分支是否成功所需时长大于确定目标分支地址时长时才生效

前面提到的五段流水线不适用BHT，因为它在ID段同时进行分支成功判断和计算目标地址的操作。

前面提到五段流水线是在EX段计算条件码和计算目标地址的，而优化版本通过减少分支延迟的处理，将分支计算提到ID段就完成

方法二：采用分支目标缓冲器（BTB，branch target buffer）

对于高性能流水线特别是多流出类处理机，要求能够预测分支，且快速提供足够的指令流

对五段流水线，如果提前一拍在IF译码段就能够得到足够信息，就可以将分支开销降为0

原理：将分支成功的分支指令的地址和它的分支目标地址都放到一个缓冲区中保存起来,缓冲区以分支指令的地址作为标识。

主键是执行过的成功分支指令的地址，第二字段是预测的分支目标地址

这相当于一个cache的缓存机制，记录成功分支指令，下一次指令来到时便会先与BTB进行匹配，如果匹配主键就直接获得成功分支目标地址，因此没有造成停顿；但如果找不到，或者实际情况和预测的相反（猜成功实际失败或猜失败实际成功），就要先花一个周期更新BTB，再花一周期取新的指令，造成两个周期的损耗。

基于硬件的前瞻执行

对分支指令的结果进行猜测,并假设这个猜测是对的
然后按这个猜测结果继续取、流出和执行后续指令
只是执行指令的结果不是写回到寄存器或存储器,而是放到一个称为ROB(ReOrderBuffer)的缓冲器(队列)中。等到相应的指令得到"确认"(Commit)(即确实是应该执行的)之后,才将结果写入寄存器或存储器。

前瞻执行结合了三种思想：

动态分支预测，选择后续执行的指令
控制相关的结果未出之前，前瞻地执行后续指令
用动态调度对基本块的各种组合进行跨基本块的调度

关键思想：允许指令乱序执行，但必须顺序确认

tomasulo算法对前瞻执行的支持

我们知道，tomasulo算法分为三个阶段：取指、执行、写结果。

将写结果段再划分为写结果和确认指令两个段

写结果段
把前瞻执行的结果写到ROB中;
通过CDB在指令之间传送结果,供需要用到这些结果的指令使用。

指令确认段
在分支指令的结果出来后,对相应指令的前瞻执行给予确认。
如果前面所做的猜测是对的,把在ROB中的结果写到寄存器或存储器。
如果发现前面对分支结果的猜测是错误的,那就不予以确认,并从那条分支指令的另一条路径开始重新执行。

于是，tomasulo+前瞻执行的步骤如下：

流出
- 从浮点指令队列的头部取一条指令。
- 如果有空闲的保留站（设为r）且有空闲的ROB项（设为b），就流出该指令，并把相应的信息放入保留站r和ROB项b。
- 如果保留站或ROB全满，便停止流出指令，直到它们都有空闲的项
执行
- 如果有操作数尚未就绪,就等待,并不断地监测CDB。(检测RAW冲突)
- 当两个操作数都已在保留站中就绪后,就可以执行该指令的操作。
写结果
- 当结果产生后,将该结果连同本指令在流出段所分配到的ROB项的编号放到CDB上,经CDB写到ROB以及所有等待该结果的保留站。
- 释放产生该结果的保留站。
- store指令在本阶段完成,其操作为:
  - 如果要写入存储器的数据已经就绪,就把该数据写入分配给该store指令的ROB项。
  - 否则,就监测CDB,直到那个数据在CDB上播送出来,这时才将之写入分配给该store指令的ROB项。
指令确认
- 其他指令（除分支指令和store指令）
  当该指令到达ROB队列的头部而且其结果己经就绪时，就把该结果写入该指令的目标寄存器，并从ROB中删除该指令。
- store指令
  处理与上面类似，只是它把结果写入存储器。
- 分支指令
  当预测错误的分支指令到达ROB队列的头部时，清空ROB，并从分支指令的另一个分支重新开始执行。（错误的前瞻执行)
  当预测正确的分支指令到达ROB队列的头部时，该指令执行完毕

表

ROB表（代替指令运行状态表）

Value字段记录的是前瞻执行后的结果

保留站表

增加Dest字段，指示哪个ROB项将接收保留站指令的结果

同时，保留站中存放的是ROB的编号而不是保留站号

寄存器状态表

同样的，寄存器状态表中存放的是ROB的编号而不是保留站号

前瞻执行与tomasulo的差别

前瞻执行通过ROB实现了顺序完成，而tomasulo很明显是乱序完成
前瞻执行可以实现精确异常，即正常运行现场和异常现场一致，而tomasulo可能会产生不精确异常

前瞻执行的漏洞问题

熔断(Meltdown)和幽灵(Specter)漏洞
原因:如果处理器猜错了,那么被错误抓取的数据依旧会存储在Cache中…
也称为"旁路分析利用"漏洞利用乱序/前瞻执行技术,破坏了内存隔离机制,使恶意程序可越权访问操作系统内存数据,造成敏感信息泄露
恶意程序从其它程序的内存中窃取信息,包括密码、账户信息、加密密钥和理论上存储在进程中的任何内容

前瞻执行的缺陷

需要支持的硬件太多、太复杂

多指令流出技术

为了使CPI小于1，需要每个时钟周期流出多条指令

多流出处理机

超标量（superscalar）

在每个时钟周期流出的指令条数不固定,依代码的具体情况而定。(有上限)
设这个上限为m,就称该处理机为m流出。
可以通过编译器进行静态调度,也可以基于Tomasulo算法进行动态调度。

基于静态调度的多流出技术

指令按序流出,在流出时硬件进行冲突检测。如果有,只流出该指令之前的指令。
假设一种每个时钟周期流出两条指令的MIPS处理机:1条整数型指令+1条浮点操作指令
同时取两条指令,译码两条指令

需要增加的硬件不多

增加冲突逻辑检测电路
如果浮点load或浮点store指令使用整数部件,会增加对浮点寄存器的访问冲突。

增设一个浮点寄存器的读/写端口
由于流水线中的指令多了一倍,定向路径也要增加
限制超标量流水线的性能发挥的障碍。
- load后续3条指令都不能使用其结果,否则就会引起停顿。
- 分支延迟
  
  如果分支指令是流出包中的第一条指令,则其延迟是3条指今
  否则就是流出包中的第二条指令,其延迟就是两条指令

基于动态调度的多流出技术

扩展Tomasulo算法:支持双流出超标量
每个时钟周期流出两条指令，一条是整数指令,另一条是浮点指令。
采用一种比较简单的方法
指令按顺序流向保留站,否则会破坏程序语义
将整数所用的表结构与浮点用的表结构分离开,分别进行处理,这样就可以同时地流出一条浮点指令和一条整数指令到各自的保留站
有两种不同的方法可以实现多流出。
- 在半个时钟周期里完成流出步骤,这样一个时钟周期就能处理两条指令。
- 设置一次能同时处理两条指令的逻辑电路。
  
  现代的流出4条或4条以上指令的超标量处理机经常是两种方法都采用。

上述双流出动态调度流水线的性能受限于以下3个因素:

整数部件和浮点部件的工作负载不平衡,没有充分发挥出浮点部件的作用。

应该设法减少循环中整数型指令的数量。
每个循环迭代中的控制开销太大。5条指令中有两条指令是辅助指令。

应该设法减少或消除这些指令。
控制相关使得处理机必须等到分支指令的结果出来后才能开始下一条L.D指令的执行。

VLIW 超长指令字（Very long Instrument word）

在每个时钟周期流出的指令条数是固定的，这些指令构成一条长指令或者一个指令包。
指令包中，指令之间的并行性是通过指令显式地表示出来的。
使用多个独立功能单元实现多流出
指令调度是由编译器静态完成的。
是SIMD

示例：

存在问题：

程序代码长度增加了
- 提高并行性而进行的大量的循环展开。
- 指令字中的操作槽并非总能填满。
采用了锁步机制
- 任何一个操作部件出现停顿时，整个处理机都要停
  顿。
机器代码的不兼容性

超标量vsVLIW

超标量处理机与VLIW处理机相比有两个优点

超标量结构对程序员是透明的，因为处理机能自动检测下一条指令能否流出，从而不需要重新排列指令来满足指令的流出
即使是没有经过编译器针对超标量结构进行调度优化的代码或是旧的编译器生成的代码也可以运行。要想达到很好的效果，使用动态超标量调度

多流出处理机的缺陷

主要受以下三个方面的影响：

程序所固有的指令级并行性。
硬件实现上的困难。
超标量和超长指令字处理器固有的技术限制

超流水线处理机（SuperPipelining）

将每个流水段进一步细分，这样在一个时钟周期内能够分时流出多条指令。这种处理机称为超流水线处理机。
对于一台每个时钟周期能流出n条指令的超流水线计算机来说，这n条指令不是同时流出的，而是每隔1/n个时钟周期流出一条指令。

实际上该超流水线计算机的流水线周期为1/n个时钟周期

典型的超流水线机器：MIPS R4000

超标量vs超流水线

超标量采用空间并行性。通过重复设置多份硬件来提高性能：
超流水线采用时间并行性。只需增加少量硬件通过各部分硬件的充分重叠工作来提高性能

m：超标量道数
n：超流水线一个时钟周期流出数