0x00 前言

没有看过或者没有看到这里的小伙伴们,看到这个标题一定觉得摸不着头脑。那这里就先来解释一下背景。

double poly(double a[], double x, long degree)
{
    long i;
    double result = a[0];
    double xpwr = x;
    for (i = 1; i <= degree; i++) {
        result += a[i] * xpwr;
        xpwr = x * xpwr;
    }
    return result;
}
double polyh(double a[], double x, long degree)
{
    long i;
    double result = a[degree];
    for (i = degree; i >= 0; i--) {
        result = a[i] + x * result;
    }
    return result;
}

这是 CSAPP 的两道题,每一题是一段代码,这两段代码实现了同一个功能。这两道题有一个共同的问题,比较这两段代码的性能。

0x01 答案

这里的答案是,poly 的性能比 polyh 的性能要高。poly 的 CPE 是 5,而 polyh 的 CPE 是 8。

这就显得很尴尬了,我原以为两个函数的 CPE 都是 8。

0x02 我的猜想

polyh 的 CPE 是 8 我没有疑问,因为这个循环里的操作是无法并行的,也就是下一次迭代会依赖上一次迭代产生的结果。所以,CPE = 5 + 3,5 是浮点数乘法的延迟下届,3 是浮点数加法的延迟下界。

poly 的 CPE 我原本认为也是 8,两个乘法是可以并行的,但是这个加法的是依赖于第一个乘法的值,无法并行,所以 CPE = 5 + 3 = 8。

0x03 指令集并行和流水线

上面的是我的猜想,所以我认为这里的答案是它们的 CPE 是相同的,性能也是相同的。但是如前面所写,答案并不是这样的。于是,我把之前看的东西都翻出来想了一下,真的不是这样的。

现代 CPU 是有一个流水线的概念的。什么是流水线呢,想象一下汽车车间,我们造一辆汽车,是分成了很多道工序的,比如装配发动机、装车门、轮子等等。现代 CPU 也是类似的,我们看到的一条指令,在执行的时候,经历了一长串的流水线,导致了指令真正的执行顺序和我们看到的可能是不一样的,但是由于现代出来的这种机制,可以确保最后的结果是和我们看到的是一样的。

0x04 解释

poly 函数,在执行的时候,由于有两个浮点数乘法单元,所以 a[i] * xpwrxpwr = x * xpwr 可以并行执行。而 a[i] * xpwr 可以通过流水线的数据转移,让这个加法 result + a[i] * xpwr 可以在下一次迭代的时候执行,因为每次迭代的时候,两个乘法都不会依赖 result 这个结果。这样,加法和乘法可以并行执行。浮点乘法的延迟下界是 5,浮点加法的延迟下界是 3,所以浮点乘法是关键路径,CPE 也自然就是 5 了。

再来看看 polyh 函数。这个函数的循环里只有一个浮点乘法运算和一个浮点加法运算。先来看看浮点乘法运算,x * result,很显然,每一次乘法都需要依赖上一次迭代的结果,导致了加法无法和乘法并行执行。于是,CPE 就成了 5 + 3 = 8 了。

0x05 最后

这个例子,我觉得很有趣,因为它涉及到了一个流水线的细节。同时,也说明了,并不是操作少的代码,效率就高。

本文为作者自己读书总结的文章,由于作者的水平限制,难免会有错误,欢迎大家指正,感激不尽。

0x06 参考文献

《深入理解计算机系统(第 3 版)》第 4、5 章