指令重排序

CPU内部结构

图例

CPU由多个功能部件构成
在这个结构中，一条指令执行时，要依次用到多个功能部件，分成多个阶段，虽然每条指令是顺序执行的，但每个部件的工作完成以后，就可以服务于下一条指令，从而达到并行的效果

这种结构叫做流水线(pipeline)结构

流水线(pipeline)结构

比如典型的RISC指令在执行过程会分成前后共5个阶段

• IF: 获取指令
• ID(或RF): 指令解码和获取寄存器的值
• EX: 执行指令
• ME(或MEM): 内存访问(如果指令不涉及内存访问，这个阶段可以省略)
• WB: 写回寄存器

Intel 的 Ice Lake 架构的CPU下的执行单元

• 

• 其他执行单元还有: BM、Vec ALU 、Vec SHIF、Vec Add、Vec Mul、Shuffle

因为CPU内部存在着多个功能单元，所以在同一时刻，不同的功能单元其实可以服务于不同的指令

这样的话，多条指令实质上是并行执行的，从而减少了总的执行时间，这种并行叫做指令级并行

如果没有这种并行结构，或者由于指令之间存在依赖关系，无法并行，那么执行周期就会大大加长

案例

假设load和store指令需要3个时钟周期来读写数据，add指令需要1个时钟周期，mul指令需要2个时钟周期

图中橙色的编号是原来的指令顺序，绿色的数字是每条指令开始的时钟周期，你把每条指令的时钟周期累计一下就能算出来

最后一条指令开始的时钟周期是20，该条指令运行需要3个时钟周期，所以在第22个时钟周期执行完所有指令

右边是重新排序后的指令，一共花了13个时钟周期

• 仔细看一下左边前两条指令，这两条指令的意思是：先加载数据到寄存器，然后再做一个加法
• 但加载需要3个时钟周期，所有add指令无法执行，只能干等着
• 右列的前3条都是load指令，它们之间没有数据依赖关系，可以每个时钟周期启动一个，到了第四个时钟周期，每一条指令的数据已经加载完毕，所以就可以执行加法运算了

• 可以把右边的内容画成上图所示，很多指令在时钟周期上是重叠的，这就是指令级并行的特点
• 当然，不是所有指令都可以并行，最后的3条指令就是顺序执行

导致无法并行的原因

数据依赖约束

如果后一条指令要用到前一条指令的结果，那必须排在它的后面，比如下面两条指令: add 和 mul

对于第2条指令来说，除了获取指令的阶段(IF)可以和第一条指令并行以外，其他阶段需要等第一条指令的结果写入r1,第2条指令才可以使用r1的值继续运行

add r2, r1
mul r3, r1

功能部件约束

如果只有一个乘法计算器，那么一次只能执行一条乘法运算

指令流出约束

指令流出部件一次流出n条指令

寄存器约束

寄存器数量有限，指令并行时使用的寄存器不可以超标

后者可以合并成为一类，称为资源约束

其他无法并行的原因

在数据依赖约束中，如果有因为使用同一存储位置，而导致不能并行，可以用重命名变量方式消除，这类约束被叫做伪约束

而先写后写，以及先读后写的伪约束的两种呈现方式

先写后写：

• 如果指令A写一个寄存器或内存位置，B也写一个同一个位置，就不能改变A和B的执行顺序
• 不过可以修改程序，让A和B写不同的位置

先读后写：

• 如果A必须在B写某个位置之前的读某个位置，那么不能改变A和B的执行顺序
• 除非能够通过重命名让它们使用不同的位置

数据的依赖图(dependence graph)

前提

它的边代表了值的流动，比如a行加载了一个数据到r1，b行利用r1来做计算

所以b行依赖a行，这个图叫优先图(precedence graph)，因为a比b优先，b比d优先

可以给图中的每个节点再加上两个属性，利用这两个属性，就可以对指令进行排序了

• (1) 操作类型，因为这涉及它所需要的功能单元
• (2) 时延属性，也就是每条指令所需的时钟周期

图中的a、c、e、g是叶子，它们没有依赖任何其他节点，所以尽量排在前面

b、d、f、h必须出现在各自所依赖的节点后面，而根节点i，总是要排在最后面

累计时延

根据时延属性，计算出每个节点的累计时延(每个节点的累计时延等于父节点的累计时延加上本节点的时延)

其中 a-b-d-f-h-i路径是关键路径，代码执行的最少时间就是这条路径所花的时钟周期之和

因为a在关键路径上，所以首先考虑把a节点排在第1行

剩下的树中，c-d-f-h-i变成了关键路径，因为c的累计时延最大。c节点可以排在第2行

b和e的累计时延都是最长的，但由于b必须在a执行完毕后，才会开始执行，所以最好等够a的3个时钟周期，否则还是会空等，所以先不考虑b，而是把e放到第3行

继续按照这个方式排，最后可以获得 a-c-e-b-d-g-f-h-i的指令序列

不过这个代码其实还可以继续优化：也就是发现并消除其中的伪约束

消除伪约束

c 和 e都向r2里写了值，而d使用的是c写入的值

如果改变变量名称，比如让e使用r3寄存器，就可以去掉e跟d，以及e与c之间的伪约束，让e就可以排在c和d之前

同理，也可以让g使用r4寄存器，使得g可以排在e和f的前面

当然了，在这个示例中，这种改变并没有减少总的时间消耗，因为关键路径上的依赖没有改变，它们都使用了r1寄存器

但是在别的情况下，就有可能带来更大的优化

其实是采用了一种最常见的算法，List Scheduling 算法

• (1) 把变量重命名消除伪约束
• (2) 创建依赖图
• (3) 为每行代码计算优先值(计算方法可以有很多，比如示例中的基于最长时延的方法就是一种)
• (4) 迭代处理代码并排序

NP-完全是什么意思？

也就是这类问题找不到一个随规模(代码行数)计算量增长比较慢的算法(多项式时间算法)来找到最优解

反之，有可能计算量会随着代码行数呈指数级上升

当然，找最优解太难，可以退而求其次，找一个次优解

就比如我们用地图软件导航的时候，没必要要求导航路径每次都是找到最短的