parallel-processing - 阿姆达尔定律示例

Question

阿姆达尔定律指出，计算的部分 S 必须按顺序从 1 个处理器系统到 N 个处理器系统进行时，计算的最大加速比最多为

                 1 / (S + [(1 - S) / N])

有谁知道对代码进行实际分析的书籍或笔记，对于一些非平凡的计算，以确定分数 S 吗？

Answer 1

Microsoft Patterns and Practices book on Parallel Programming with .NET中对 Amdahl 定律进行了很好的讨论。

对代码进行详细分析将非常困难——因为每种情况都是独一无二的。

但是，如果您有确定并发量的机制，它应该是可以轻松近似的。通过更改可用的并发性和分析，您应该能够S通过反向求解方程来进行估计。

Answer 2

以下是一些可能对您有所帮助的链接：

微软研究院 | 多核时代阿姆达尔定律的讨论

Amadahl（和Gustafson）定律的评估和分析

估计速度乘数的摘要 简要讨论阿姆达尔定律

希望他们能帮助你。

Answer 3

所涉及的原则并不是并行化所独有的。如果程序 25% 的时间用于执行某些特定操作，那么除了 25% 之外的所有操作都立即发生（不影响 25%），则程序会占用原始时间的 25%，因此速度是原来的四倍。

在算法具有可并行化或不可并行化的明确阶段的情况下，上述公式的应用将很简单——图 N 路并行化将使可并行化的部分以 N 倍的速度运行，而不能并行化的部分则以 N 倍的速度运行。 t parallelizable 将以正常速度运行。在实践中，我认为大多数算法并不完全由 100% 可并行化或 100% 顺序的部分组成。在大多数有趣的情况下，算法可以在很大程度上并行运行，但有各种排序约束；在某些情况下，精确的排序约束可能取决于数据。因此，“并行化百分比”可能会根据处理器的数量等因素而变化，因此尝试将其插入公式不会很有帮助。