(Java 高并发程序设计) 一篇文章带你深入了解有关并行的两个重要定律

Bertha 。 2022-12-20 11:08 166阅读 0赞

有关为什么要使用并行程序的问题前面已经进行了简单的探讨。总的来说，最重要的应该是出于两个目的。第一，为了获得更好的性能；第二，由于业务模型的需要，确实需要多个执行实体。

在这里，我将更加关注于第一种情况，也就是有关性能的问题。将串行程序改造为并发程序，一般来说可以提高程序的整体性能，但是究竟能提高多少，甚至说究竟是否真的可以提高，还是一个需要研究的问题。目前，主要有两个定律对这个问题进行解答，一个是Amdahl定律，另外一个是Gustafson定律。

### 文章目录 ###

*   *  一、Amdahl 定律
     *  二、Gustafson 定律
     *  三、两者是否相互矛盾

## 一、Amdahl 定律 ##

Amdahl定律是计算机科学中非常重要的定律。它定义了串行系统并行化后的加速比的计算公式和理论上限。

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

所谓加速比就是优化前的耗时与优化后耗时的比值。加速比越高，表明优化效果越明显。下图显示了Amdahl公式的推导过程，其中`n`表示处理器个数，`T`表示时间，`T1`表示优化前耗时（也就是只有1个处理器时的耗时），`Tn`表示使用`n`个处理器优化后的耗时。`F`是程序中只能串行执行的比例。

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L25hbmh1YWliZWlhbg_size_16_color_FFFFFF_t_70_pic_center]  
据这个公式，如果CPU处理器数量趋于无穷，那么加速比与系统的串行化比例成反比，如果系统中必须有50%的代码串行执行，那么系统的最大加速比为2。

假设有一个程序分为以下步骤执行，每个执行步骤花费100个单位时间。其中，只有步骤2和步骤5可以并行，步骤1、3、4必须串行，如图所示。在全串行的情况下，系统合计耗时为500个单位时间。

![在这里插入图片描述][20201111194300229.png_pic_center]  
若将步骤2和步骤5并行化，假设在双核处理上，则有如图 1.10 所示的处理流程。在这种情况下，步骤2和步骤5的耗时将为50个单位时间。故系统整体耗时为400个单位时间。根据加速比的定义有：

> 加速比 = 优化前系统耗时 / 优化后系统耗时 = 500 / 400 = 1.25

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L25hbmh1YWliZWlhbg_size_16_color_FFFFFF_t_70_pic_center 1]  
由于5个步骤中，3个步骤必须串行，因此其串行化比例为`3/5 = 0.6`，即F = 0.6，且双核处理器的处理器个数N为2。代入加速比公式得：

> 加速比 = 1/(0.6+(1-0.6)/2) = 1.25

在极端情况下，假设并行处理器个数为无穷大，则有如图1.11所示的处理过程。步骤2和步骤5的处理时间趋于0。即使这样，系统整体耗时依然大于300个单位时间。使用加速比计算公式，N趋于无穷大，有加速比 = `1/F`，且F = 0.6，故有加速比 = 1.67。即加速比的极限为`500/300 = 1.67`。

![在这里插入图片描述][20201111194545378.png_pic_center]

> 根据Amdahl定律，使用多核CPU对系统进行优化，优化的效果取决于CPU的数量，以及系统中的串行化程序的比例。CPU数量越多，串行化比例越低，则优化效果越好。仅提高CPU数量而不降低程序的串行化比例，也无法提高系统性能

## 二、Gustafson 定律 ##

Gustafson定律也试图说明处理器个数、串行化比例和加速比之间的关系，如图1.12所示，但是Gustafson定律和Amdahl定律的角度不同。同样，加速比都被定义为优化前的系统耗时除以优化后的系统耗时

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L25hbmh1YWliZWlhbg_size_16_color_FFFFFF_t_70_pic_center 2]  
可以看到，由于切入角度的不同，Gustafson定律的公式和Amdahl定律的公式截然不同。从Gustafson定律中，我们可以更容易地发现，如果串行化比例很小，并行化比例很大，那么加速比就是处理器的个数。只要不断地累加处理器，就能获得更快的速度。

## 三、两者是否相互矛盾 ##

Amdahl定律和Gustafson定律的结论不同，这是不是说明这两个理论之间有一个是错误的呢？其实不然，两者的差异其实是因为这两个定律对同一个客观事实从不同角度去审视后的结果，它们的侧重点有所不同

举一个生活中的例子，一辆汽车行驶在60km的路上，你花了一个小时，行驶了30km。无论接下来开多快，你都不可能达到90km/h的速度。图1.13很好地说明了原因。

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L25hbmh1YWliZWlhbg_size_16_color_FFFFFF_t_70_pic_center 3]  
求解图1.13中的方程，你会发现如果想达到90km的时速，那么你从AB中点到达B点的时间会是一个负数，这显然不是一个合理的结论。实际上，如果前半程30km你使用了一小时，那么即使你从中点到B点使用光速，也只能把整体的平均时速维持在60km/h。

也就是说Amdahl强调：当串行化比例一定时，加速比是有上限的，不管你堆叠多少个CPU参与计算，都不能突破这个上限！

而Gustafson定律的出发点与之不同，对Gustafson定律来说，不管你从A点出发的速度有多慢，只要给你足够的时间和距离，只要你后期的速度比期望值快那么一点点，你总是可以把平均速度调整到非常接近那个期望值的。

比如，你想要达到均速90km/h，即使在前30km你的时速只有30km/h，你只要在后面的速度达到91km/h，给你足够的时间和距离，总有一天可以把均速提高到90km/h。  
因此，Gustafson定律关心的是：如果可被并行化的代码所占比例足够大，那么加速比就能随着CPU的数量线性增长。

所以，这两个定律并不矛盾。从极端的角度来说，如果系统中没有可被并行化的代码（即F = 1），那么对于这两个定律，其加速比都是1。反之，如果系统中可被并行化代码的比例达到100%，那么这两个定律得到的加速比都是n（处理器个数）。

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L25hbmh1YWliZWlhbg_size_16_color_FFFFFF_t_70_pic_center]: /images/20221120/0cbdeadebbbd46aeb4439812e4b21f40.png
[20201111194300229.png_pic_center]: https://img-blog.csdnimg.cn/20201111194300229.png#pic_center
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L25hbmh1YWliZWlhbg_size_16_color_FFFFFF_t_70_pic_center 1]: https://img-blog.csdnimg.cn/20201111194423497.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L25hbmh1YWliZWlhbg==,size_16,color_FFFFFF,t_70#pic_center
[20201111194545378.png_pic_center]: https://img-blog.csdnimg.cn/20201111194545378.png#pic_center
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L25hbmh1YWliZWlhbg_size_16_color_FFFFFF_t_70_pic_center 2]: https://img-blog.csdnimg.cn/2020111119514741.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L25hbmh1YWliZWlhbg==,size_16,color_FFFFFF,t_70#pic_center
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L25hbmh1YWliZWlhbg_size_16_color_FFFFFF_t_70_pic_center 3]: https://img-blog.csdnimg.cn/20201111195548729.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L25hbmh1YWliZWlhbg==,size_16,color_FFFFFF,t_70#pic_center