确定数据流中的关键路径

Question

在Computer Systems:A Programmer's Perspective一书中,练习5.5显示了一段代码来计算多项式的值

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;
}

练习假设双精度浮点加法和乘法所需的时钟周期分别为3和5.要求读者解释为什么测量的CPE(每元素周期数)值为5.

按照习题答案,在每次迭代中,我们需要更新变量xpwr和result我们需要的,操作是一个浮点加法(对于result)和浮点乘法(对于xpwr),因此后者占主导地位的延迟,导致最终CPE为5.

但我认为数据流应该是这样的:

xpwr               result
  |                  |
  +-----+ +--[load]  |
  |     | |          |
[mul]  [mul]         |
  |      |           |
  |      +---+ +-----+
  |          | |
  |         [add]
  |           |
  |           +------+
  |                  |
xpwr               result

所以最长的路径是从前一个值xpwr到新值result,通过执行单元[mul]和[add].因此最长时间应为8个周期.

我想问一下

1. 关键路径究竟是什么意思？以及如何确定它？
2. 哪个答案(我的和书)更合理？

任何关于CPU,架构,执行单元,管道,浮点单元的解释都将受到赞赏.

Answer 1

我知道我参加聚会有点晚了,但这本书绝对正确.正如您可以通过计时代码来验证自己,CPE确实是5,所以第二个答案是错误的.

但第一个也是错误的.它说MUL必须同时执行,这在Nehalem架构中是不可能的(我怀疑,大多数现代处理器).请记住,只有一个FP MUL单元和一个不同的FP ADD单元(如本书所述,2011年及以后编辑)

相反的是这样的:

(假设LOAD总是存在,如果在缓存中则只有1个周期)

首先我们喂xpwr *= xMUL.紧接着我们喂食xpwr*a[i](记住管道!)

......经过5个循环后,我们将获得新的值xpwr,经过6个循环,我们将得到结果xpwr*a[i].此时,新的计算xpwr *= x将在MUL的第1阶段进行.因此,如果我们不希望受到它们的限制,我们只有4个周期来执行其余的操作.

当然,这很容易,因为FP ADD只需要3个周期来获得新的result.

因此,很明显,限制因素是计算xpwr.这意味着在寻找关键路径(无论是什么)时,我们必须特别注意从旧值到新值的路径.在这种情况下,路径result仅包含一个FP ADD!(这也是最初让我失望的原因)

Answer 2

关键路径是图中最长的路径，在本例中为八个时钟。这是《龙书》中关于关键路径的说法（10.3.3 优先拓扑顺序）：

在没有资源限制的情况下，最短的调度由关键路径给出，即通过数据依赖图的最长路径。可用作优先级函数的度量是节点的高度，它是图中源自该节点的最长路径的长度。

我想你在书中发现了一个错误。您应该考虑联系作者，以便他们在以后的印刷中纠正它。