九、乱序执行

乱序执行的定义：现代cpu可以乱序执行指令或者同时执行多个操作，因为一个cpu上有多个计算核心可以同时计算。

乱序执行可以提高效率，但是当存在依赖关系链时（第三章第六节），cpu无法乱序执行，顺序结构中依赖关系链比如：

1
2
float a, b, c, d, y;
y = a + b + c + d;

这个表达式将会以((a+b)+c)+d形式计算，编译器不会优化，因为交换计算位置可能会导致溢出（可以回顾浮点数相关的知识（第六章第一节）），我们可以手动取消依赖关系链。

1
2
float a, b, c, d, y;
y = (a + b) + (c + d);

这样就可以同时计算(a+b)和(c+d)。

还有一种常见的依赖链是循环依赖链，例如：

1
2
3
4
const int size = 100;
float list[size], sum = 0; int i;
for (i = 0; i < size; i++)
    sum += list[i];

这里每一次循环都必须依赖上一次循环的结果，优化这种循环可以可以采用展开循环将依赖链一分为二

1
2
3
4
5
6
7
8
9
10
// Example 11.2b

const int size = 100;
float list[size], sum1 = 0, sum2 = 0; int i;
for (i = 0; i < size; i += 2)
{
    sum1 += list[i];
    sum2 += list[i+1];
}
sum1 += sum2;

如果微处理器从时间 T 到 T+5 对sum1做加法，那么它可以从时间 T+1 到 T+6 对 sum2 做加法，整个循环只需要 256个时钟周期。当然如果size为奇数，要在循环外把最后一位再加上。

当然上面的栗子并没有消除循环依赖链，自然也无法使用乱序执行，如果可以的话应当尽量避免出现循环依赖链。

如果没有循环依赖链，另一个提高效率的方式是使用寄存器作为中间存储，例如：

1
2
3
4
5
6
7
8
9
// Example 11.3
const int size = 100; int i;
float a[size], b[size], c[size];
float register temp;
for (i = 0; i < size; i++)
{
    temp = a[i] + b[i];
    c[i] = temp * temp;
}

具有无序功能的微处理器非常智能。他们可以检测到上例中循环的一次迭代中的寄存器临时值独立于前一次迭代中的值。这允许它在计算完前一个值之前开始计算一个新的临时值。它通过为 temp 分配一个新的物理寄存器来实现这一点，即使在机器码中出现的逻辑寄存器是相同的。这叫做寄存器重命名。CPU可以保留同一逻辑寄存器的许多重命名实例。使cpu能重叠循环迭代计算的条件为：

  1. 没有循环依赖链。
  2. 所有的中间结果都应该保存在寄存器中，而不是内存中。重命名机制只对寄存器有效，而对内存或缓存中的变量无效。在上例中，即使没有 register 关键字，大多数编译器也会使 temp 成为寄存器变量。（CodeGear编译器不能生成浮点寄存器变量，但会在内存中保存临时变量。这会阻止 CPU 的重叠计算）
  3. 循环分支需要可以被预测。如果重复计数很大或恒定，则不存在此问题。如果循环计数很小且不断变化，那么CPU可能偶尔会预测循环分支已经退出了，而实际上它没有，因此无法开始下一个计算。然而，乱序执行机制允许CPU提前增加循环计数器，这样它就可以在判断错误之前及时发现。因此，你不必太担心这种情况。

乱序执行通常是自动的，开发者只需要保证没有依赖链就行。除此之外，还可以做些别的操作提高乱序执行的效率，比如将浮点加法与浮点乘法混合使用、将简单整数与向量整数操作混合使用、将数学计算与内存访问混合使用也有很大的好处。