深入理解计算机系统第五章，关于每元素周期数（CPE）的计算问题

Question

练习题5.5 题目如下：
对多项式求值a0+a1x+a2x^2+...+an*x^n。
代码如下：

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

该题第二问说到，在参考机Core i7上，测量这个函数的CPE等于5.00。
参考答案是这样解释的：限制性能的计算是反复地计算表达式xpwr = x * xpwr。这需要一个双精度浮点数乘法（5个时钟周期），并且直到前一次迭代完成，下一次迭代的计算才能开始。两次连续的迭代之间，对result的更新只需要一个浮点加法（3个时钟周期）。
那我的问题就是，a[i] * xpwr这个代码不应算入对result的更新的时钟周期么？也就是说实际的CPE不应该是5+3么？

Answer 1

我有完全一样的问题，后来找到了网上的一篇文章解释的挺清楚的（https://is.daryl.moe/posts/cs...），下面我用自己的话复述一下，希望能帮到大家。
之前的答案没有解释很让人迷惑的一点，就是result += a[i] * xpwr这句话不仅有需要3个周期的加法，里面还有个乘法不能忽略啊，光执行这句话就要8个周期，那一个循环需要的周期数瓶颈难道不是这句话吗？
事实上这8个周期是“虚”的，这句话在循环中执行的吞吐量只相当于5个周期，能做到这一点的关键在于，计算这一次的加法可以和计算下一次的乘法同时进行。接下来我把我理解的整个循环过程发生了什么叙述一遍。
第一步，计算a[i]*xpwr和xpwr*x。由于处理器有两个浮点乘单元所以这两个运算被并行处理，5个周期。
第二步，计算result+(上一步算出的a[i]*xpwr)。这个需要3个周期。等等，这不就8个周期了嘛？但是我们发现，这个第二步的结果不会影响下一轮迭代的第一步的计算，因此我们可以同时计算这一轮的第二步和下一轮的第一步。

Answer 2

两次连续的迭代之间，对result的更新只需要一个浮点加法（3个时钟周期）。

答案已经说的很明白，你理解有误。

对result的更新确实只需要执行语句result += a[i] * xpwr，而这个浮点数加法只需要3个时钟周期。

两个连续迭代之间有：两次加法，一次乘法，一次比较。所以两次迭代之间的CPE >　8。

PS：贴代码，请格式化。

Answer 3

CPE是每个元素周期数，不是每次循环，这个函数主宰性能的是双精度浮点数的延迟界限，就是5个时钟周期，而且练习题5.6的C也讲了原因

Answer 4

你好！我也是遇到这个疑问才来查查。可是就在我看到你的问题的瞬间我想通了。这就是流水线处理处理器的特点。5.5题的程序，因为result和后边的两个数据没有关联，所以加法指令可以在译码阶段直接取得执行阶段的浮点运算的成果。因此在循环迭代过程中，加法不会影响循环的每元素周期数。但是对于5.6题就不同了，表达式更新result值与自身关联，必须先提取result原来的值，在没有进行浮点乘法的情况下不能进行浮点加法，浮点加法没有结束也不能更新result因为他在关键路径上。说的不是很明白。望大家纠正。
我觉得理解这个问题的关键是循环是一个周而复始的过程，流水线结构上的指令也是连续不断的，只割裂执行的一个环节很难想通这个问题。5.5也可以这么思考，两个浮点乘法运算相互关联，一前一后执行，第一条浮点运算的结果被保存（参看5.7.1关于转发的论述），浮点加法每次取更新后的值进行运算。把这个循环拉开，浮点加法就好像站在流水线旁边扫条码的工人，不影响生产进度。因为流水线生产的速度，比他扫描的速度慢。

补充一下还有一种策略就是生成两段程序的汇编代码，按照书上讲解的数据流程图的画法画出数据流程图。一操作你就明白了！把循环前和循环后相关寄存器状态之间的数据流程图画出来。

Answer 5

因为当CPE为5时的那个方法是可以依靠多核进行并行的 result的计算你可以看到实际上和xpwr的更新没什么特别大的关系 两个绝对可以并行运行 你也可以看看练习题5.6 那道题的result就是每一步都相互依赖 即使我cpu有再多的核心 也无法并行

Answer 6

不知道还有没有人看了。。。
浮点乘法在参考机上有两个运算单元，因此在一次迭代（记为迭代1）中两个乘法操作可以并行。trick的地方在于，加法操作会被延迟到下一次迭代（记为迭代2）中。加法操作的一个操作数由迭代1的两个乘法中其中一个乘法的结果传送而来（不算延迟代价），这个加法和迭代2的两个乘法并行计算。由于加法延迟小于乘法，乘法才是数据流图的关键路径。只看数据流图，可以算出总延迟是5n+3，加3是因为迭代n+1只有加法，乘法操作在迭代1至迭代n执行完毕。