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-完全是什么意思？
也就是这类问题找不到一个随规模(代码行数)计算量增长比较慢的算法(多项式时间算法)来找到最优解
反之，有可能计算量会随着代码行数呈指数级上升
当然，找最优解太难，可以退而求其次，找一个次优解
就比如我们用地图软件导航的时候，没必要要求导航路径每次都是找到最短的
