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

参考

https://blog.csdn.net/yutianzuijin/article/details/8489555

https://blog.csdn.net/qq_34594236/article/details/79674204

加速比=优化前系统耗时/优化后系统耗时

G.M.Amdahl在1967年提出了Amdahl’s law，针对并行处理的scalability给出了一个模型，指出使用并行处理的提速由问题的可并行的部分所决定。这个模型为并行计算系统的设计者提供了指导。 其形式如下：

 f为问题中可被并行处理的部分的比例，m为并行处理机的数量，Speedup为并行后相比串行时的提速。

这就是加速比的计算公式，从公式可以看出增加处理器的数量（提升n的值）并不一定能有效地提高加速比，如果系统的并行化程序不高，即F的值接近100%，就算n无穷大，加速比也是趋近于1的，并不会对系统的性能优化起到什么作用，而成本却无限增加了。所以，我们可以从“加速比”的公式中看出，单纯地增加cup处理器的数量并不一定可以有效地提高系统的性能，只有在提高系统内并行化模块比重的前提下，同时合理增加处理器的数量，才能以最小的投入得到最大的加速比，这就是阿姆达尔定律要告诉我们的核心思想，它很直观地反应了加速比与处理器个数、系统串行比例之间的关系。

    Amdahl’s law表明在问题的可并行部分不大时，增加处理机的数量并不能显著地加快解决问题的时间。这让计算机界产生了悲观的情绪，有人认为搞多处理器的机器没什么前途。但是，Amdahl’s law忽略了一些重要的事实。Amdahl’s law是一个fixed-size model，就是要解决的问题的大小是固定的，可并行化的比例是固定的。而在实际中，我们不会用1000个处理机来处理一个小问题，当我们的计算能力的总和增加之后，可以也应该去解决更大的问题。当问题更大的时候，通常情况下，这个问题也有更大的可能被分为可并行化的小问题（或者说处理多个相互独立的问题），也就意味着f更大（更接近1），能得到更大的Speedup。

    直到1988年，Gustafson提出了一个fixed-time model，也即Gustafson’s Law，人们对重拾对大规模并行计算的信心。Gustafson’s Law可表示为以下公式：

们定义a为系统串行执行时间，b为系统并行执行时间，n为处理器个数，F为串行比例，那么系统执行时间（串行时间+并行时间）可以表示为a+b，系统总执行时间（串行时间）可以表示为a+nb

 其中，串行比例F=a/a+b,其代入上面的公司，可得到：

 从公式中可以看出，F（串行化程度）足够小，也即并行化足够高，那么加速比和cpu个数成正比。

对一个在单处理机上的工作w，我们将其扩大到m个核上，scaled workload为w’=(1-f)w+fmw。对在串行条件下对w’的处理时间比上在并行条件下对w’的处理时间即为Speedup。在这个模型中，问题的规模是可以被扩大(scale)的。从这个公式可以看到，f固定时，speedup显线性增长。     在1990年，Sun and Ni提出了memory-bounded model，即Sun and Ni’s law。形式如下：

 在这个模型下，workload被scale的方式不同，workload跟随着memory的增长而以某种方式增加（G(n)）。在这个模型里，Speedup也随处理机的数量的增长而线性增长，而且比Gustafson’s Law的增长情况更乐观。     其实，这几个模型其实在本质上是一致的，并没有冲突，那为什么Speedup会有那么大的不同呢？这是因为处理机的使用率。当workload被scale，而不是fix时，增加的处理机就会有事可做，保持一个比较高的使用率。也就是这些computing capacity没有被浪费掉。如果没有被浪费掉，这些computing capacity就在一定的时间多完成了一些工作，完成整个工作的时间就缩短了。所以，Speedup就变大了。     结论是，多搞些处理机是没错的，但是要有具有好的scalability的系统支持，以提高处理机的使用率