computer-architecture - 阿姆达尔定律示例

Question

有人可以帮我做这个例子，并告诉我如何工作第二部分吗？

问题是 ：

如果天气预报算法的三分之一本质上是串行的，其余是可并行的，那么保证比单核实现提高 150% 所需的最小内核数是多少？

ii. 你的老板将这个数字修改为 200%。你的新答案是什么？

首先十分感谢 ！！

Answer 1

我有点晚了，但这里是答案：

1) 增加 150% -> 如前所述，至少需要 2 个核心dbasnett；

2) 增加 200% -> 根据阿玛尔德定律至少需要 4 个核心：

在这里，执行计算总共需要 90 分钟。P是算法的实际增强部分（可并行化部分），它是 90 的 2/3，N 是核心数，所以当只有一个核心时：

你得到 1，这意味着 100%，这是算法执行标准方式的方式（没有多核加速，因此没有并行化加速）。

现在，我们必须找到 N 个内核，其前面的等式等于 2，其中 2 意味着算法在一半时间内执行（45 分钟而不是没有并行化时的 90 分钟），因此具有 200% 的加速：

自从：

我们看到：

因此，使用 4 个内核并行计算 2/3 的算法，您可以获得 200% 的加速。150% 也是如此，你会得到 2，正如dbasnett已经告诉你的那样。

很简单。

请注意，复杂的算法可能意味着对其可并行部分的进一步划分（理论上，每个可并行部分可以同时拥有不同数量的处理单元）：

您可以进一步查看 Wikipedia（还有一个示例）：

http://en.wikipedia.org/wiki/Amdahl%27s_law#Description

反正原理是一样的：

假设T是算法完成所需执行的时间，A是它的串行部分，B 是它的可并行部分，N 是并行 CPU 的数量，您可以将 B 划分为更小的部分并对每个部分进行计算：

例如，对于 C、D、G，您可以采用 M 个 CPU 而不是 N（如果 M != N，加速当然会有所不同）。

最后，您将到达拥有更多 CPU 不再重要的地步，因为：

并且您的算法加速最多将倾向于总执行时间（T）除以仅串行部分的执行时间（A）。

因此，只有在算法的串行部分执行时间较短时，并行计算才真正派上用场。

Answer 2

猜想：如果算法是 1/3 串行和 2/3 并行...我认为您添加的每个内核都会使您的性能提高 66%...所以要提高 150%，您还需要 3 个核心，如果要增加 200%，你需要 4 个。

这是一个猜测。你的教科书可能更有帮助:)

Answer 3

如果算法在单核上运行并需要 90 分钟，那么串行部分需要 30 分钟，并行部分需要 60 分钟。

添加 CPU：

30是串行部分，30是并行部分（60的一半与串行部分重叠）。

90 / 60 = 增加 150%。