确定数据流中的关键路径[重复]

Question

在《计算机系统：程序员的视角》一书中，练习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，我们需要的操作是浮点加法（对于结果）和浮点乘法（对于xpwr），因此后者控制延迟，导致最终CPE为5。

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

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

所以最长的路径是从xpwr的前一个值到结果的新值，经过执行单元[mul]和[add]。因此最长的时间应该是8个周期。

我想问问

1. 关键路径的确切含义是什么？如何确定它？
2. 哪个答案（我的和书）更合理？

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

Answer 1

A1：根据这本书，关键路径是数据流图中最长的路径，它必须在一条直线上，并且对单个寄存器有影响，而不是将“mul”和“add”相加，其结果只是下一个操作的中间操作数。

关于这个问题，如果继续阅读其余的内容，你就可以完成所有的事情。特别是，比较组合7的数据流图和组合5的数据流图会很有帮助。

A2：如果理解了A1，问题2就清楚了，书中的答案是合理的。

Answer 2

关键路径确实是8个周期，但问题要求CPE，它就像输出循环的一个周期的时间平均时间。

除了第一个周期和最后一个周期之外，处理器还可以同时执行上一次循环迭代的加法和当前乘法，因为操作数彼此不依赖。循环的第一次迭代需要完整的8个周期，但所有迭代之后，循环只需要5个周期来运行，使实际的CPE为5个周期。

P、 我同意这本书描述关键路径的方式令人困惑。他们对关键路径的定义不仅仅是采用最长路径的路径，而且该路径还必须具有操作数依赖于以前的操作的操作，因此必须是有序的。这一定义使得寻找关键路径非常不直观。

Answer 3

我知道我来晚了一点，但这本书绝对正确。正如您可以通过对代码计时来验证的那样，CPE实际上是5，因此第二个答案是错误的。

但第一个也是错误的。它说MUL必须同时执行，这在Nehalem体系结构（我怀疑是大多数现代处理器）中根本不可能实现。请记住，只有一个FP MUL单元和一个不同的FP ADD单元（如2011版及以后版本的书籍所示）

取而代之的是：

（假设负载始终存在，如果在缓存中仅1个周期）

首先，我们在MUL中输入xpwr*=x。紧接着，我们给xpwr*a[i]（记住管道！）

...5个周期后，我们将得到xpwr的新值，6个周期后，我们将得到xpwr*a[i]的结果。那时，xpwr*=x的新计算将在MUL的第1阶段进行。所以如果我们不想受到它们的限制，我们只有4个周期来完成其余的操作。

当然，这很容易，因为我们只需要FP ADD的3个周期即可获得新的结果。

因此，很明显，限制因素是xpwr的计算。这意味着在寻找关键路径（无论是什么）时，我们必须特别关注从旧价值观到新价值观的路径。在这种情况下，结果的路径只包含一个FP ADD！（这也是一开始让我失望的原因）