Instruction-Level Parallelism¶
约 4055 个字 12 行代码 23 张图片 预计阅读时间 14 分钟
高僧预测
1. 指令级并行：概念与挑战¶
对于确定一个程序中的并行度以及如何利用并行，判断指令之间的依赖关系至关重要。如果两条指令是并行的，那么只要流水线有足够的资源，就可以在一个任意深度的流水线之中同时执行他们，并且不会导致任何停顿；如果两条指令是相互依赖的，那么其必须按照顺序执行。
值得注意的是，依赖是程序的一种属性。某种给定依赖是否会导致检测到实际冒险，冒险又是否会导致停顿，这都取决于流水线结构的性质。下面假设指令 i 位于指令 j 之前，一般存在下面三种依赖：
- 数据依赖/真数据依赖/Data Dependence：指令 i 生成的结果可能会被指令 j 用到；或者指令 j 数据依赖于指令 k，指令 k 又数据依赖于指令 i。
- 名称依赖/Name Dependence：两条指令使用相同的寄存器或者存储地址（称为名称），但与该名称相关的指令之间并没有数据流动的时候，就会发生名称依赖。
- 控制依赖/Control Dependence：控制依赖决定了指令 i 相对于分支指令的顺序，使指令 i 按照争取的指令顺序执行，并且只在应当执行的时候执行。除了程序中第一个基本块中的指令以外，其他所有指令都和某组分支存在控制依赖，为了保持程序顺序，必须保持这些控制依赖。
名称依赖之下又可以分为反依赖/Antidependence 和输出依赖/Output Dependence：
- 当指令 j 对指令 i 读取的寄存器或者存储地址执行写操作的时候，就会在指令 i 和指令 j 之间产生反依赖，为了能保证指令 i 可以读到正确的值，必须保持指令之间的顺序。
- 当指令 i 和指令 j 都写入相同的寄存器或者存储地址的时候，就会在指令 i 和指令 j 之间产生输出依赖，为了保证最后写入的值和指令 j 相对应，必须保持指令之间的顺序。
由于没有在指令之间传递值，如果改变这些指令之中使用的名称，使这些指令不再冲突，名称依赖中涉及的指令就可以重新排序或者同时执行。这种操作称为寄存器重命名/Register Renaming。
根据指令中读访问和写访问的顺序，可以将数据冒险分为 3 类：
- RAW/Read After Write/写后读：j 试图在 i 写入一个源位置之前读取该源位置，所以 j 会错误地获得旧值，这与真数据依赖相对应。为了确保 j 会收到来自 i 的值，必须保持程序顺序。
- WAW/Write After Write/写后写：j 试图在 i 写一个操作数之前写该操作数。这些写操作将以错误的顺序执行，最后写入目标位置的是由 j 写入的值，而不是由 i 写入的值。这种冒险与输出依赖相对应。只有在允许多个流水级进行写操作的流水线中，或者在前一指令停顿时允许后-指令继续执行的流水线中，才会发生 WAW 冒险。
- WAR/Write After Read/读后写：j 尝试在 i 读取一个目标位置之前写入该位置，所以i会错误地获取新值。这一冒险源于反依赖。对于大多数静态安排流水线（即使是较深的流水线或者浮点流水线），由于所有读操作都比所有写操作要早一些，所以不会发生 WAR。
2. 使用动态调度克服数据冒险¶
我们之前的流水线使用静态调度/Static Scheduling，也就是在获取指令后会发射该指令，除非发现该指令存在数据依赖且无法通过前递/Forwarding 来隐藏该数据依赖，此时冒险检测硬件会从使用该寄过的指令开始，使流水线出于停顿状态，直到依赖清除后再获取新的指令。简而言之，使用静态调度的流水线的关键特征和限制是：使用顺序指令发射和执行，且存在暂停/Stall。
在动态调度/Dynamic Scheduling 中，硬件会重新安排指令的执行顺序以减少停顿，同时保持数据流和异常行为不变（在不改变数据流的同时尽可能避免停顿）。它的优点有：
- 允许针对一种流水线结构编译的代码在不同的流水线上高效执行；
- 可以应对编译的时候依赖关系未知的情况；
- 允许处理器容忍一些意料之外的延时，比如缓存缺失，可以在解决缓存缺失的时候执行其他代码。
在经典的五级流水线之中，可以在指令译码/ID 期间检查结构冒险和数据冒险，当可以无冒险执行的时候，就可以从 ID 发射出去，并且确认所有数据冒险都已经解决。为了可以实现动态调度，我们将发射过程分为两部分：检查所有结构冒险和等待数据冒险的消失，我们仍然使用顺序指令发射，但是我们希望一条指令可以在其数据操作数可用的时候立刻开始执行，因此这样的流水线实际上是乱序执行的/Out-of-Order Execution，这也意味着乱序完成/Out-of-Order Completion。但是这样的性质会让事情变得复杂起来：
- 乱序执行可能导致 WAR 和 WAW 冒险，后面会使用寄存器重命名来解决。
- 乱序完成会使异常处理变得复杂，采用连续完成的动态调度必须保留异常行为，既要使严格按照程序顺序执行时发生的异常仍然实际发生，又要保持不会发生其他异常；并且动态调度的处理器可能造成非精确异常，意味着在发生异常的时候，处理器状态和严格按照程序顺序执行指令时的状态不完全一致，这又有两个子原因：
- 流水线在执行导致异常的指令时，可能已经完成了按照程序顺序排在这一条指令之后的指令；
- 流水线在执行导致异常的指令时，可能还没有完成按照程序顺序排在这一条指令之前的指令。
非精确异常增大了在异常之后重新开始执行的难度，后面我们会讨论这些问题。
我们将五级简单流水线的 ID 流水级分为下面两个阶段：
- 发射/Issue/IS：指令译码，检查结构冒险（顺序发射）；
- 读取操作数/Read Operands/RO：一直等到没有数据冒险之后，读取操作数。
我们区分一个指令开始执行和完成执行的时刻：在这两个时刻之间，指令处于执行过程之中。我们的流水线允许同时执行多条指令，这是利用动态调度优势的前提。但是同时执行多条指令也意味着我们需要有多个功能单元或者流水化功能单元，两者兼有也可以，但是我们一般假设具有多个功能单元。
2.1 Scoreboard 算法¶
我们考虑下面的 RISC-V 代码：
简单来讲，Scoreboard 算法维护三个表，分别记录指令及指令状态，功能单元状态和寄存器状态，当只有第一个 Load 指令结束之后，这三个表应该如下所示：
我们认为第二个 Load 指令只完成了执行，并未完成写回操作，由于 Add 部件只有一个，因此最后一条 Add 指令不能被发射。因为第一条 Mul 指令需要使用 F2 寄存器，而 F2 寄存器被第二个 Load 指令占用，因此第一条 Mul 指令需要等待，无法读取操作数，后面的指令也同理。
这里解释一下功能单元状态表的每一个字段的意思：
Busy：功能单元是否被占用；Op：功能单元正在执行的操作；Fi、Fj、Fk：分别代表目的操作数和两个/一个源操作数；Qj、Qk：表明两个源操作数来自哪个部件，比如第二行的Qj为 Integer 部件，表明 F2 寄存器来自 Integer 部件；Rj、Rk：表明两个源操作数是否已经准备好，这分为三种情况：yes：表明操作数准备好了，但是还没有读；no且Qj为空，表明操作数已经读取好；no且Qj不为空，表明操作数还没有准备好，别的指令有可能修改这个操作数，就更别说读了。
下面的寄存器状态表记录了每一个寄存器将会被哪一个部件修改。
注意这张图右侧的四个阶段实际上并不是在描述流水线，而是指明了指令的执行阶段。
当 FMUL.D 指令准备好写回结果的时候，三个表长这样：
当 FDIV.D 指令准备好写回结果的时候，三个表长这样：
例题
Scoreboard 算法的问题之一在于没有积极的处理反依赖和输出依赖，只是使用停顿来解决这两种依赖，而 Tomasulo 算法会积极使用寄存器重命名进一步处理依赖。
2.2 Tomasulo 算法¶
Tomasulo 算法的基本思想如下：
- 通过跟踪每条指令的操作数何时可用，以消除 RAW 冒险；
- 通过硬件实现寄存器重命名，消除 WAW 和 WAR 冒险；、
算法的核心是两个硬件部件：
- 保留站/Reservation Station：
- 公共数据总线/Common Data Bus/CDB：
Tomasulo 算法分为三步走：
- 发射/Issue：从 FIFO 的指令队列取出下一条指令，尝试分配到空闲的保留站；
- 如果存在着一个空闲的保留站，将这条指令发射到保留站内，如果需要的值都已经就绪，就带着值一起发射，不然就记录操作数对应的功能单元编号；
- 如果没有空的保留站，那么目前存在着一个结构冒险，指令会停顿，进行阻塞等待，知道保留站出现空闲；
- 这一步其实就是在做寄存器重命名，消除 WAR 和 WAW 冒险。
- 执行/Execute：监视总线，操作数可用立刻执行；
- 当所有操作数都就绪后，指令可以被分配到对应的功能单元执行，这一步是乱序的；
- 否则就在等待计算的同时监视 CDB，当一个操作数变得可用的时候，就将它放到任何一个正在等待它的保留站中；
- 在一个时钟周期内，可能在一个保留站内会有多条指令同时变成就绪状态，对于浮点数保留站，可以随便选择一条指令进行执行，但是对于 Load 和 Store 指令，会复杂一些；
- Load 和 Store 其实是一个两步的执行过程，当基址寄存器就绪后，计算出有效地址，再将目标地址放到缓冲区内；
- 对于加载，当内存单元可用时，加载会立马执行；对于存储，会等待要存储的值，然后将其发送到存储器单元；
- 为了保护异常行为，任何一条指令必须等到根据程序顺序排在它之前的所有分支全部完成之后，才能执行。
- 写回/Write Back：
- 当结果准备好后，将其写到 CDB 上，然后通过 CDB 将结果写回到寄存器之中，并且通过寄存器广播到所有需要这个结果的保留站中（包含 Store 的缓冲区）。
- 对于 Store 指令，其结果会缓存在 Store 的缓冲区中，直到所需要被保存的值（可能来自寄存器）和存储地址都准备好了，才会在内存单元空闲时写入内存中。
Tomasulo 算法维护三张表：
- 指令状态表：只分为 Issue、Execute、WriteResult 三部分，并非硬件的一部分；
- 保留站状态表：记录发射出来的每条指令的状态，一共有八个字段：
Busy：表明保留站以及对应的功能单元是否被占据；Op：对源操作数要执行的操作；Qj、Qk：产生对应源操作数的保留站。值为 0 表示源操作数已经在Vj或Vk上可用；Vj、Vk：源操作数的值，对于每一个操作数，Q和V只有一个是有效的，对于加载指令，这个字段用于保存偏移量字段；A：用于保存为加载存储指令计算存储器地址所需的信息，在开始时，指令的立即数字段存储在这里，在计算地址之后，有效地址存储在这里；
- 寄存器状态表（字段
Qi）：如果一个运算的结果应当存储在这个寄存器中，则Qi是包含此运算的保留站的编号，如果Qi的值为空（或 0），则当前没有活动指令正在计算应当存储在这个寄存器中的结果，也就是说这个值就是寄存器的内容。
还是对于原来的指令，考虑下面两种情况：
只有第一条 Load 指令完成，且已经将结果写到 CDB 时的状态：
FMUL.D 指令已经准备好写回结果的状态：
Tomasulo 算法尽管很有效，但是仍然有这一些问题：
- 结构复杂：需要多个保留站和缓冲区，以及一个公共数据总线；
- 性能受限：公共数据总线的带宽限制了性能；
- 加载和存储指令的顺序：加载和存储指令可以乱序执行，但是需要保证它们访问不同的地址，如果一个加载和存储指令访问相同的地址，交换顺序就会产生 WAR 或 WAW 冒险。
3. 基于硬件的推测¶
基于硬件的推责结合了下面三种关键思想：
- 使用动态分支预测选择要执行那些指令；
- 利用推测执行
实现推测背后的关键思想是允许指令乱序执行，但是强制他们顺序提交，并且防止指令在提交之前采取任何不可撤销的动作，比如更新状态或者引发异常，这样就可以保证精确异常。也可以很简单地使用在整数指令上，但是可以见得确实增加了很多的硬件复杂性。
4. 使用多发射和静态调度利用 ILP¶
5. 使用多发射和动态调度利用 ILP¶
由于非推测流水线的执行速率很快就会落后于发射速率，因此在再发射几个迭代之后，非推测流水线就会进入停顿。并且，当存在数据依赖分支的时候，推测方法会带来一些好处，反之就会限制性能，这个好处也依赖于准确的分支预测，错误的预测会带来严重的性能损失。