阿姆达尔定律及其在计算机组织中的证明

什么是 Amdahl's Law？

Amdahl's Law 是计算机体系结构中的一个原理，它描述了一个程序在部分并行化时的潜在加速比。该定律由 Gene Amdahl 于 1967 年提出。

根据 Amdahl's Law，程序的加速比由程序中无法并行化的部分决定。数学上，Amdahl's Law 可以表示为

其中

加速比是并行化程序所实现的性能提升。

这里 P 代表程序的比例。

这里 N 是可用的处理器或计算资源的数量。

例如，如果一个程序有 20% 的部分是顺序的且无法并行化，那么最大理论加速比将是 5 倍 (1 / (0.2 + (0.8 / N)))。处理器数量与加速比成反比。

在并行化的情况下，Amdahl's Law 是什么？

Amdahl's Law 的并行化侧重于可并行部分 (P) 和处理器数量 (N) 的影响。

该定律表明，程序的非并行化部分限制了加速比。它不取决于处理器的数量。随着处理器数量的增加，非并行化部分的影响变得相对更重要。

根据 Amdahl's Law，加速比与程序的非并行化部分成反比。随着非并行化部分减少，加速的潜力增加。

例如，如果一个程序 80% 是可并行化的，20% 是顺序的，那么最大理论加速比将是

加速比 = 1 / ((1 - 0.8) + (0.8 / N))

该公式表明，随着处理器数量 (N) 的增加，加速比将受程序顺序部分的限制 (1 - 0.8 = 0.2)。

Amdahl's Law 的优点

Amdahl's Law 有几个优点。以下是使用 Amdahl's Law 的一些优点：

• 性能估算： Amdahl's Law 帮助开发人员和系统架构师评估并行化工作对整体性能的影响。
• 优化焦点： 它允许开发人员专注于优化和改进顺序代码的性能。
• 资源分配指导： Amdahl's Law 有助于确定并行计算系统中计算资源的最佳分配。决策制定：它有助于评估关于加速比和性能的潜在投资回报。这些信息有助于就目标并行级别和资源分配做出决策。

Amdahl's Law 的缺点

以下是 Amdahl's Law 的一些缺点：

• 简化的假设： Amdahl's Law 基于简化的假设。在该定律中，问题可以分为独立的并行部分和顺序部分；这在复杂的实际程序中可能不成立。
• 忽略其他因素： Amdahl's Law 只关注程序的可并行部分和非并行部分的影响。它不关注影响性能的其他因素，例如内存访问模式、通信开销、负载不平衡和同步成本。这可能导致加速比预测不准确。
• P 和 N 的确定不准确： P 和 N 的值有时并不准确。P 和 N 的值可能因程序、使用的算法、输入大小等而异。
• 过度简化程序行为： Amdahl's Law 告诉我们程序行为不会改变。但实际上，程序行为可能因输入数据、运行时条件和其他因素而异。

Amdahl's Law 和 Gustafson's Law 的区别？

Amdahl's Law 和 Gustafson's Law 是描述并行计算系统可伸缩性的两个不同原理，但它们都有不同的方面和不同的假设。

Amdahl's Law 由 Gene Amdahl 于 1967 年提出，它解决了程序在部分并行化时的潜在加速比。

John L. Gustafson 在 1988 年提出了一个定律，后来被称为 Gustafson's Law。Gustafson's Law 使用“扩展效率”的概念而不是加速比来表示。扩展效率的公式是

E = 1 - f + fN

Amdahl's Law 的推导

为了推导 Amdahl's Law，我们将首先考虑一个程序，其中有 "f" 部分代码是顺序的，而 "1 - f" 部分代码可以并行执行。假设有 "N" 个处理元素或线程。

• 设顺序部分的程序完成时间为 "Ts"，而并行部分在单个处理元素上执行的完成时间为 "Tp"。那么程序的总执行时间将是

T = Ts + Tp

• 在并行化代码时，顺序部分 (Ts) 保持不变，而可并行部分 (Tp) 可以平均分配给 "N" 个处理元素。因此，可并行部分可以在时间内并行执行

Tp' = Tp / N

• 现在，并行化程序的总执行时间将是

T' = Ts + Tp' = Ts + Tp / N

• 通过并行化程序实现的加速比可以表示为原始执行时间 (T) 与并行化执行时间 (T') 的比率

S = T / T' = (Ts + Tp) / (Ts + Tp / N)

• 现在将分子和分母都除以 Ts

S = (1 + Tp / Ts) / (1 + Tp / (N * Ts))

• 现在表达式可以写成以下形式：

S = (1 + (Tp / Ts)) / (1 + (Tp / (N * Ts)))

• 现在，将可并行化的程序部分 (1 - f) 表示为

Tp / Ts = α

• 将此值代入表达式，我们得到

S = (1 + α) / (1 + α / N)

• 现在将分子和分母都乘以 N，我们得到

S = N / (N * (1 + α / N)) = 1 / (1 + α / N)

• 代入 α = Tp / Ts 的值，我们得到 Amdahl's Law

S = 1 / (f + (1 - f) / N)

这是 Amdahl's Law 的最终推导。该公式表示当在 "N" 个处理元素上执行具有 "f" 部分顺序代码和 "1 - f" 部分可并行代码的程序时，可以实现的最大加速比。