multithreading - 如何计算螺纹效率的阿玛达尔定律

Question

它很容易找到和理解 Amadahl 定律的函数定义，但是我能找到的所有工作示例要么太模糊，要么太学术/太大脑，以至于我的小豌豆大脑无法理解。

Amadahl 定律采用以下参数：F，不能通过多线程改进的任务的百分比，以及N，要使用的线程数。

如何F以任何程度的准确度进行计算？

您如何查看一段代码并确定多线程是否会对其进行改进？

Answer 1

说你的代码的哪些部分肯定不会从多线程中受益相对容易：顺序部分。如果您必须按顺序执行一系列小步骤，多线程将无济于事，因为您总是需要等待一个步骤完成才能开始下一步。从这个意义上说，许多常见任务（不一定）不是顺序的：例如，在列表中搜索多个项目。如果要从列表中提取每个红色项目，可以在多个线程之间共享列表的一部分，并将每个部分中的所有红色项目收集到最终结果列表中。并发编程的困难在于为实际问题找到有效的方法。

在较低级别上，您可以谈论数据依赖性：特定指令或块依赖于前一个块，如果它自己使用该块的计算结果。所以（伪代码）：

Block one:
load r1 into r2
add r1 to r3 into r4


Block two:
load r4 into r1
add 3 to r4 into r4

块二依赖于块一：它们必须按顺序执行。这里：

Block one:
load r1 into r2
add r1 to r3 into r4

Block two:
load r1 into r3
add 3 to r1 into r1

事实并非如此。这对并发没有直接的用处，但希望它能更具体地说明这一点。它还说明了处理并发性的另一个问题：作为抽象块功能，这两个功能可以并行运行，但在此处给出的具体示例中，它们正在读取/写入一些相同的寄存器，因此编译器/流水线/无论什么都必须做更多的工作让它们一起运行。这一切都非常复杂，但在http://www.amazon.com/Computer-Architecture-Quantitative-Approach-Edition/dp/1558605967中有很好的介绍。

哪些其他部分不能从多线程中受益取决于您的编程环境和机器架构。

至于如何获得百分比，在一个实际案例中可能会涉及一些挥手——我怀疑你永远不会得到一个准确的数字。如果您将代码划分为功能单元并分析每个功能单元的执行时间，这将为您提供大致适当的权重。那么如果一个占用 90% 执行时间的部分可以通过多线程来改进，你说你的 90% 的“任务”可以得到如此改进。

Answer 2

如果你想看看多线程可以改进什么，你应该看看算法而不是代码。

通常，并行算法应该从头开始设计为并行的。“并行化”代码而不是算法本身要困难得多。

查看内存访问中的依赖关系（空间依赖关系），查看操作序列（时间依赖关系），了解您的计算机体系结构，您将知道如何为您的任务构建合适的算法。

根据公式本身 - Wiki 有很好的解释http://en.wikipedia.org/wiki/Amdahl 's_law

Answer 3

Amdahl 将所有工作分为两组：完全可并行化和完全不可并行化。

将后者视为您永远无法摆脱的工作。您可以摆脱以前完美的海湾添加资源。

如果你读取一个文本文件并逐行处理它，你永远无法摆脱顺序读取文件来解析这些行。但是，您可以并行化各个行。如果读取文件需要 1 秒，那么您的代码将永远不会运行得比这更快。

对于真正的代码，你可以连接一个分析器来查看每个部分花费了多少时间。希望您可以将每个部分归为其中一个类别。完成此操作后，您可以轻松估计加速，它会非常准确。