# 5.7.3 处理器操作的抽象模型

作为分析在现代处理器上执行的机器级程序性能的一个工具，我们会使用程序的数据流（data-flow）表示，这是一种图形化的表示方法，展现了不同操作之间的数据相关是如何限制它们的执行顺序的。这些限制形成了图中的关键路径（critical path），这是执行一组机器指令所需时钟周期数的一个下界。

在继续技术细节之前，检查一下函数 combine4 的 CPE 测量值是很有帮助的，到目前为止 combine4 是最快的代码：

函数/界限	方法	整数 `+`	整数 `*`	浮点数 `+`	浮点数 `*`
`combine4`	累积在临时变量中	1.27	3.01	3.01	5.01
延迟界限		1.00	3.00	3.00	5.00
吞吐量界限		0.50	1.00	1.00	0.50

我们可以看到，除了整数加法的情况，这些测量值与处理器的延迟界限是一样的。这不是巧合——它表明这些函数的性能是由所执行的求和或者乘积计算主宰的。计算 n 个元素的乘积或者和需要大约 L·n+K 个时钟周期，这里 L 是合并运算的延迟，而 K 表示调用函数和初始化以及终止循环的开销。因此，CPE 就等于延迟界限 L。

# 1. 从机器级代码到数据流图

程序的数据流表示是非正式的。我们只是想用它来形象地描述程序中的数据相关是如何主宰程序的性能的。以 combine4（图 5-10）为例来描述数据流表示法。我们将注意力集中在循环执行的计算上，因为对于大向量来说，这是决定性能的主要因素。我们考虑类型为 double 的数据、以乘法作为合并运算的情况，不过其他数据类型和运算的组合也有几乎一样的结构。这个循环编译出的代码由 4 条指令组成，寄存器 %rdx 存放指向数组 data 中第 i 个元素的指针，%rax 存放指向数组末尾的指针，而 %xmm0 存放累积值 acc。

# Inner loop of combine4. data_t = double, OP = *
# acc in %xmm0, data+i in %rdx, data+length in %rax
.L25:                              # loop:
    vmulsd  (%rdx), %xmm0, %xmm0   # Multiply acc by data[i]
    addq    $8, %rdx               # Increment data+i
    cmpq    %rax, %rdx             # Compare to data+length
    jne     .L25                   # If !=, goto loop

如图 5-13 所示，在我们假想的处理器设计中，指令译码器会把这 4 条指令扩展成为一系列的五步操作，最开始的乘法指令被扩展成一个 load 操作，从内存读出源操作数，和一个 mul 操作，执行乘法。

combine4 内循环代码的图形化表示

图 5-13 combine4 的内循环代码的图形化表示。指令动态地被翻译成一个或两个操作，每个操作从其他操作或寄存器接收值，并且为其他操作和寄存器产生值。我们给出最后一条指令的目标为标号 loop。它跳转到给出的第一条指令。

作为生成程序数据流图表示的一步，图 5-13 左手边的方框和线给出了各个指令是如何使用和更新寄存器的，顶部的方框表示循环开始时寄存器的值，而底部的方框表示最后寄存器的值。例如，寄存器 %rax 只被 cmp 操作作为源值，因此这个寄存器在循环结束时有着同循环开始时一样的值。另一方面，在循环中，寄存器 %rdx 既被使用也被修改。它的初始值被 load 和 add 操作使用；它的新值由 add 操作产生，然后被 cmp 操作使用。在循环中，mul 操作首先使用寄存器 %xmm0 的初始值作为源值，然后会修改它的值。

图 5-13 中的某些操作产生的值不对应于任何寄存器。在右边，用操作间的弧线来表示。load 操作从内存读出一个值，然后把它直接传递到 mul 操作。由于这两个操作是通过对一条 vmulsd 指令译码产生的，所以这个在两个操作之间传递的中间值没有与之相关联的寄存器。cmp 操作更新条件码，然后 jne 操作会测试这些条件码。

对于形成循环的代码片段，我们可以将访问到的寄存器分为四类：

只读：这些寄存器只用作源值，可以作为数据，也可以用来计算内存地址，但是在循环中它们是不会被修改的。循环 combine4 的只读寄存器是 %rax。
只写：这些寄存器作为数据传送操作的目的。在本循环中没有这样的寄存器。
局部：这些寄存器在循环内部被修改和使用，迭代与迭代之间不相关。在这个循环中，条件码寄存器就是例子：cmp 操作会修改它们，然后 jne 操作会使用它们，不过这种相关是在单次迭代之内的。
循环：对于循环来说，这些寄存器既作为源值，又作为目的，一次迭代中产生的值会在另一次迭代中用到。可以看到，%rdx 和 %xmm0 是 combine4 的循环寄存器，对应于程序值 data+i 和 acc。

正如我们会看到的，循环寄存器之间的操作链决定了限制性能的数据相关。

图 5-14 是对图 5-13 的图形化表示的进一步改进，目标是只给出影响程序执行时间的操作和数据相关。在图 5-14a 中看到，我们重新排列了操作符，更清晰地表明了从顶部源寄存器（只读寄存器和循环寄存器）到底部目的寄存器（只写寄存器和循环寄存器）的数据流。

将 combine4 的操作抽象成数据流图

图 5-14 将 combine4 的操作抽象成数据流图。a）重新排列了图 5-13 的操作符，更清晰地表明了数据相关。b）操作在一次迭代中使用某些值，产生出在下一次迭代中需要的新值。

在图 5-14a 中，如果操作符不属于某个循环寄存器之间的相关链，那么就把它们标识成白色。例如，比较（cmp）和分支（jne）操作不直接影响程序中的数据流。假设指令控制单元预测会选择分支，因此程序会继续循环。比较和分支操作的目的是测试分支条件，如果不选择分支的话，就通知 ICU。我们假设这个检查能够完成得足够快，不会减慢处理器的执行。

在图 5-14b 中，消除了左边标识为白色的操作符，而且只保留了循环寄存器。剩下的是一个抽象的模板，表明的是由于循环的一次迭代在循环寄存器中形成的数据相关。在这个图中可以看到，从一次迭代到下一次迭代有两个数据相关。在一边，我们看到存储在寄存器 %xmm0 中的程序值 acc 的连续的值之间有相关。通过将 acc 的旧值乘以一个数据元素，循环计算出 acc 的新值，这个数据元素是由 load 操作产生的。在另一边，我们看到循环索引 i 的连续的值之间有相关。每次迭代中，i 的旧值用来计算 load 操作的地址，然后 add 操作也会增加它的值，计算出新值。

图 5-15 给出了函数 combine4 内循环的 n 次迭代的数据流表示。可以看出，简单地重复图 5-14 右边的模板 n 次，就能得到这张图。我们可以看到，程序有两条数据相关链，分别对应于操作 mul 和 add 对程序值 acc 和 data+i 的修改。假设浮点乘法延迟为 5 个周期，而整数加法延迟为 1 个周期，可以看到左边的链会成为关键路径，需要 5n 个周期执行。右边的链只需要 n 个周期执行，因此，它不会制约程序的性能。

combine4 内循环 n 次迭代的数据流

图 5-15 combine4 的内循环的 n 次迭代计算的数据流表示。乘法操作的序列形成了限制程序性能的关键路径。

图 5-15 说明在执行单精度浮点乘法时，对于 combine4，为什么我们获得了等于 5 个周期延迟界限的 CPE。当执行这个函数时，浮点乘法器成为了制约资源。循环中需要的其他操作——控制和测试指针值 data+i，以及从内存中读数据——与乘法器并行地进行。每次后继的 acc 的值被计算出来，它就反馈回来计算下一个值，不过只有等到 5 个周期后才能完成。

其他数据类型和运算组合的数据流与图 5-15 所示的内容一样，只是在左边的形成数据相关链的数据操作不同。对于所有情况，如果运算的延迟 L 大于 1，那么可以看到测量出来的 CPE 就是 L，表明这个链是制约性能的关键路径。

# 2. 其他性能因素

另一方面，对于整数加法的情况，我们对 combine4 的测试表明 CPE 为 1.27，而根据沿着图 5-15 中左边和右边形成的相关链预测的 CPE 为 1.00，测试值比预测值要慢。这说明了一个原则，那就是数据流表示中的关键路径提供的只是程序需要周期数的下界。还有其他一些因素会限制性能，包括可用的功能单元的数量和任何一步中功能单元之间能够传递数据值的数量。对于合并运算为整数加法的情况，数据操作足够快，使得其他操作供应数据的速度不够快。要准确地确定为什么程序中每个元素需要 1.27 个周期，需要比公开可以获得的更详细的硬件设计知识。

总结一下 combine4 的性能分析：我们对程序操作的抽象数据流表示说明，combine4 的关键路径长 L·n 是由对程序值 acc 的连续更新造成的，这条路径将 CPE 限制为最多 L。除了整数加法之外，对于所有的其他情况，测量出的 CPE 确实等于 L，对于整数加法，测量出的 CPE 为 1.27 而不是根据关键路径的长度所期望的 1.00。

看上去，延迟界限是基本的限制，决定了我们的合并运算能执行多快。接下来的任务是重新调整操作的结构，增强指令级并行性。我们想对程序做变换，使得唯一的限制变成吞吐量界限，得到接近于 1.00 的 CPE。

练习题 5.5

假设写一个对多项式求值的函数，这里，多项式的次数为 n，系数为 a₀, a₁, …, a_n。对于值 x，我们对多项式求值，计算

a₀ + a₁x + a₂x² + … + a_nxⁿ　　（5.2）

这个求值可以用下面的函数来实现，参数包括一个系数数组 a、值 x 和多项式的次数 degree（等式（5.2）中的值 n）。在这个函数的一个循环中，我们计算连续的等式的项，以及连续的 x 的幂：
double poly(double a[], double x, long degree)
{
    long i;
    double result = a[0];
    double xpwr = x;  /* Equals x^i at start of loop */
    for (i = 1; i <= degree; i++) {
        result += a[i] * xpwr;
        xpwr = x * xpwr;
    }
    return result;
}
A. 对于次数 n，这段代码执行多少次加法和多少次乘法运算？

B. 在我们的参考机上，算术运算的延迟如图 5-12 所示，我们测量了这个函数的 CPE 等于 5.00。根据由于实现函数第 7～8 行的操作迭代之间形成的数据相关，解释为什么会得到这样的 CPE。

练习题 5.6

我们继续探索练习题 5.5 中描述的多项式求值的方法。通过采用 Horner 法（以英国数学家 William G. Horner（1786—1837）命名）对多项式求值，我们可以减少乘法的数量。其思想是反复提出 x 的幂，得到下面的求值：

a₀ + x（a₁ + x（a₂ + … + x（a_n-1 + xa_n）…））　　（5.3）

使用 Horner 法，我们可以用下面的代码实现多项式求值：
/* Apply Horner's method */
double polyh(double a[], double x, long degree)
{
    long i;
    double result = a[degree];
    for (i = degree-1; i >= 0; i--)
        result = a[i] + x * result;
    return result;
}
A. 对于次数 n，这段代码执行多少次加法和多少次乘法运算？

B. 在我们的参考机上，算术运算的延迟如图 5-12 所示，测量这个函数的 CPE 等于 8.00。根据由于实现函数第 7 行的操作迭代之间形成的数据相关，解释为什么会得到这样的 CPE。

C. 请解释虽然练习题 5.5 中所示的函数需要更多的操作，但是它是如何运行得更快的。

← 5.7.2 功能单元的性能 5.8 循环展开 →