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

Question

我知道Amdahl定律和并行程序的最大加速比。但是我不能很好地研究古斯塔夫森定律。什么是古斯塔夫森定律?安达尔定律和古斯塔夫森定律有什么不同？

Answer 1

Amdahl定律

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

​

​

古斯塔夫森定律

Amdahl的观点专注于固定的计算问题大小，因为它处理的是需要固定数量的顺序计算时间的代码。古斯塔夫森的反对意见是，大规模并行机器允许以前不可行的计算，因为它们能够在固定时间内对非常大的数据集进行计算。换句话说，并行平台不仅仅是加速代码的执行:它可以处理更大的问题。

假设您有一个应用程序需要在N处理单元上执行一个time ts。在这些计算时间中，必须按顺序运行一小部分(1-f)。因此，此应用程序将在全时序机上运行，时间t等于

​

​

如果我们增加问题大小，我们可以增加处理单元的数量，以保持代码并行执行的时间等于f·ts。在这种情况下，顺序执行时间随着N的增加而增加，它现在成为问题大小的度量。然后加速就变成了

​

​

那么效率将会是

​

​

从而使效率趋于f，从而提高N。这些相当乐观的加速和效率评估的陷阱与这样一个事实有关，即随着问题大小的增加，通信成本将增加，但通信成本的增加不符合古斯塔夫森定律。

参考

G. Barlas，多核和GPU编程:集成方法，Morgan Kaufmann

M.D. Hill，M.R.Marty，多核时代的Amdahl定律，Computer，Vol.41，N.7，pp.33-38,2008年7月。

GPGPU

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

Amdahl's law and GPU Amdahl's Law for GPU Is Amdahl's law accepted for GPUs too?

Answer 2

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

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

古斯塔夫森定律更好地反映了这种情况。例如，我们不能使用一台有20年历史的PC来玩今天的大多数视频游戏，因为它们太慢了。

Answer 3

Amdahl定律

通常，如果作业的一小部分不可能被划分为并行部分，那么整个工作只能并行地获得1/f倍的速度。这是Amdahl定律。

古斯塔夫森定律

一般来说，对于p个参与者和不可并行的部分，整个事情可以更快地获得p+(1−p)f倍。这就是古斯塔夫森定律