古斯塔夫森的法律与阿姆达尔定律

Question

我知道Amdahl定律和并行程序的最大加速.但我无法正确研究古斯塔夫森定律.什么是Gustafson定律,Amdahl和Gustafson定律之间有什么区别？

Answer 1

阿姆达尔定律

假设您有一个顺序代码,并且f其一小部分计算是并行化的,并且N在并行工作的处理单元上运行,而其余部分1-f无法改进,即无法并行化.Amdahl定律指出并行化实现的加速是

古斯塔夫森定律

Amdahl的观点主要关注固定计算问题的大小,因为它处理的代码采用固定数量的连续计算时间.Gustafson的反对意见是大规模并行机器允许以前不可行的计算,因为它们能够在固定的时间内对非常大的数据集进行计算.换句话说,并行平台不仅可以加速代码的执行,还可以处理更大的问题.

假设您有一个应用程序需要花时间ts在N处理单元上执行.在该计算时间中,(1-f)必须按顺序运行分数.因此,该应用程序将在t等于的时间内在完全顺序的机器上运行

如果我们增加问题大小,我们可以增加处理单元的数量,以保持代码并行执行的时间部分等于f·ts.在这种情况下,顺序执行时间增加N,现在成为问题大小的度量.然后加速成为

那么效率就是

因此效率往往会增加N.这些相当乐观的加速和效率评估的缺陷与以下事实有关:随着问题规模的增加,通信成本将增加,但通信成本的增加不是由Gustafson定律解释的.

参考

G. Barlas,多核和GPU编程:综合方法,Morgan Kaufmann

MD Hill,MR Marty,Amdahl在多核时代的定律,计算机,第一卷.41,n.7,pp.33-38,2008年7月.

GPGPU

关于适用于通用图形处理单元的Amdahl定律,有一些有趣的讨论,请参阅

Answer 2

我们正在从不同的角度看待同一个问题。阿姆达尔定律说，如果你有 100 个以上的 CPU，你解决同样问题的速度能快多少？

古斯塔夫森定律是说，如果一台有 100 个 CPU 的并行计算机可以在 30 分钟内解决这个问题，那么一台只有一个这样的 CPU 的计算机解决同样的问题需要多长时间？

古斯塔夫森定律更好地反映了情况。例如，我们不能使用 20 岁的 PC 来玩当今的大多数视频游戏，因为它们太慢了。