c - Loop unrolling and its effects on pipelining and CPE(有解法，但不懂)

Question

在线下方是练习测试的问题。该表实际上填写了所有解决方案。但是，我需要澄清为什么这些解决方案是它们的样子。 (阅读水平线下方的问题)。

例如，我真的很想了解 A2 和 A3 的解决方案行。

在我看来，您在 A2 中遇到了以下情况:

1. x * y
2. xy * r
3. xyr * z

现在，让我们看看管道中的情况:

|1|2|3|4|5|6|7|8 |9|10|11|12|13|14|15|16|17|18|19|20|21|
| | | | | | | |  | |  |  |  |  |  |  |  |  |  |  |  |  |
{ x * y } | | |  | |  |  |  |  |  |  |  |  |  |  |  |  |
        { xy * r } |  |  |  |  |  |  |  |  |  |  |  |  |
                 { xyr * z  }  |  |  |  |  |  |  |  |  |
//next iteration, which means different x, y and z's|  |
                   {x2 * y2    }  |  |  |  |  |  |  |  |
                               {x2y2 * r   } // this is dependent on both previous r and x2y2
                                           {x2y2r * z  }

所以我们可以重叠 xyr * z 和 x2 * y2，因为没有依赖冲突。然而，这只是摆脱了 3 个周期，对吗？

所以它仍然是 (12 - 3)/3 = 9/3 = 每个元素 3 个周期(三个元素)。 那么他们如何获得 A2 的 8/3 CPE？

如果能帮助理解这个概念，我们将不胜感激!并不着急，因为测试要到下周。如果您需要任何其他信息，请告诉我!

---

(下面是完整的试题文本，以及填满答案的表格)

考虑以下用于计算 n 个整数数组的乘积的函数。

我们将循环展开了 3 倍。

int prod(int a[], int n) {

int i, x, y, z;
int r = 1;

for(i = 0; i < n-2; i += 3) {
    x = a[i]; y = a[i+1]; z = a[i+2];
    r = r * x * y * z; // Product computation
}
for (; i < n; i++)
    r *= a[i];

return r;
}

对于标记为 Product computation 的行，我们可以使用括号创建五个不同的计算的关联，如下:

r = ((r * x) * y) * z; // A1
r = (r * (x * y)) * z; // A2
r = r * ((x * y) * z); // A3
r = r * (x * (y * z)); // A4
r = (r * x) * (y * z); // A5

我们用每个元素的循环次数来表示函数的性能(持续专业教育)。如书中所述，此度量假设运行时间，以时钟为单位循环，对于长度为 n 的数组是 Cn + K 形式的函数，其中 C 是 CPE。

我们在 Intel Pentium III 上测量了该函数的五个版本。回想一下， native 上的整数乘法运算有 4 个周期的延迟和 1 个周期的发出时间。

下表显示了 CPE 的一些值，以及其他缺失值。测得的CPE 值是实际观察到的值。 “理论 CPE”意味着性能如果唯一的限制因素是延迟和发布时间整数乘数。

填写缺失的条目。对于测量的 CPE 的缺失值，您可以使用来自具有相同计算行为的其他版本的值。对于值(value)观的理论 CPE，您可以确定将需要的周期数只考虑乘法器的延迟和发布时间的迭代，然后除以3。

Answer 1

在不知道 CPU 架构的情况下，我们只能猜测。

我的解释是时序图只显示了管道的一部分，从收集操作数到写入结果，因为这与依赖关系解析相关。

现在，大如果:如果在依赖解析器和执行单元之间有一个缓冲阶段，就可以开始第一组的第三次乘法运算(3) 和第二组的第一个乘法 (4) 都在偏移量 8 处。

因为 3 依赖于 2，所以在这里使用不同的单元没有意义，所以 3 排到单元 1在 2 之后。接下来的指令 4 不依赖于先前的结果，因此它可以排队到单元 2，并并行启动。

理论上，这最早可能在第 6 周期发生，CPE 为 6/3。实际上，这取决于 CPU 设计。