9

在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和最终的 CPE 为 5。resultresultxpwr

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

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

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

我想问一下

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

任何关于 CPU、架构、执行单元、流水线、浮点单元的解释都将不胜感激。

4

4 回答 4

6

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

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

相反，会发生这样的事情：

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

首先我们xpwr *= x输入 MUL。之后我们立即喂食xpwr*a[i]（记住管道！）

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

当然，这很容易，因为我们只需要 3 个周期让 FP ADD 获得新的result.

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

于 2014-10-19T04:10:57.720 回答
2

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

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

PS我确实同意这本书呈现关键路径的方式令人困惑。他们对关键路径的定义不仅仅是采用最长路径的路径，而且路径还必须具有操作数依赖于先前操作的操作，因此必须按顺序排列。这个定义使得寻找关键路径变得相当不直观。

于 2014-02-22T09:09:59.507 回答
1

A1：关键路径是书上数据流图中最长的一条，必须在一条直线上，对单个寄存器有影响，而不是'mul'和'add'相加，其结果是仅用于下一个操作的中间操作数。

关于这个问题，如果继续阅读其余部分，您将完成所有工作。尤其是比较 combine7 的数据流图和 combine5 的数据流图会很有帮助。

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

于 2014-11-23T00:01:29.563 回答
0

关键路径是图中最长的路径，在本例中为 8 个时钟。这就是龙书对关键路径（10.3.3 优先拓扑顺序）所说的：

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

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

于 2013-02-10T23:13:26.260 回答