多核的陷阱：从程序的角度探讨计算机的极限

本文经「原理」（微信公众号：principia1687）授权转载，禁止二次转载

上期 我们讲到，在功耗非线性增长的迫使下，芯片厂商开发出了 多核芯片 ，试图通过多核来解决之前单核的时钟频率增加所带来的功耗问题。然而这种决定忽略了另外一个很重要的问题。要讲清楚这个问题，我们先来讲个故事。

从前有一个不知足的地主，之前都是雇一个长工耕田。这个长工也很配合，随着时间的推移技术越来越好，耕田也越来越快。但有一天这个劳工达到了体能极限，再要他快就该残了。于是地主就琢磨着他这块田怎么能再快点耕完。终于有一天地主下了个血本从市场上又买了另外三个技能相当的长工扔到了田里，并满心希望之前一天能耕完的地现在六个小时就能搞定。于是地主六个小时之后去地里一看，瞬间后悔了。因为刚买来的三个长工也不知道自己该做什么，就坐在边上看着原先的那位苦逼工作。

故事讲到这里，可能有心的读者就已经发现了多核处理的问题。就是在此之前的绝大多数程序都是按照 串行算法 开发的，而 这些程序还不能很好地在多核芯片上并行执行 。因为整个程序里并没有启用多余的核进行处理，而这些多余的核在大多数时间里也都是空闲的。 （当然需要说明的是这种情况只是在执行单个程序时候发生，如果是执行多个不同的程序，那么多核还是会有效果的。就像如果这个地主有四块地分别分给买来的四个长工，他们还是可以有效工作的。）

于是学术界和工业开始了又一波对并行化的研究。他们一部分人希望通过 设计新的编程语言 ，让程序员人工提高程序的并行度。另一部分人则希望通过 对编译器的优化 ，让编译器自动识别程序中可并行的部分并生成可并行的二进制码。然而双方的成效都非常有限。 可并行的编程语言需要程序员有并行的编程思想 ，然而这多多少少有违人类本身的逻辑思维方式。同时，并行语言为程序调试带来了很大的挑战。使得大规模的并行程序开发变得相当困难。与此同时， 编译器能在程序中找到的可并行部分也相当有限 ，这也使得自动并行化的效率非常之低。

这么看来多核芯片真的是一个好的决定吗？程序的并行极限又在哪里呢？要解释这个问题，我们便不得不提到计算机科学界的另一个经验法则—— 阿姆达尔定律 。

阿姆达尔定律于1967年由IBM360系列机的主要设计者吉因恩·阿姆达尔 （Gene Amdahl） 首先提出。 它代表了处理器并行运算之后效率提升的能力 。该定律首先将一个程序分成了可并行和不可并行两部分，并指出程序中对某一部份进行并行后所能获得的系统性能改进程度，取决于并行部分被使用的频率，或所占总执行时间的比例。换句话说， 在并行计算中用多核处理器对单个程序的加速受限于该程序所需的串行时间百分比。 比如一个程序中如果有一半是不能被并行的，那么即便是有无限核数的处理器，该程序能得到的最大加速比也只是两倍。

阿姆达尔定律给出了下面这一个核心公式， speedup=1/(s+(1-s)/n) 。该公式计算了一个程序并行化之后所能带来的最大加速比。其中 s 为程序串行部分 （或不可并行部分） 所占比例；1-s 则为程序可并行部分所占比例；n为并行处理节点的个数，可以大致理解为处理器的核数。所以如果一整个程序都是可并行的 （s = 0） ，那么能得到的加速比上限就是 n。相反如果一整个程序都是不可并行的 （s = 1） ，那么加速比上限就是1。阿姆达尔定律通过该公式指出了多核的有效利用率和程序的可并行部分所占的百分比是密切相关的。这就像如果地主家的田地是很窄很长的，一次只能通过一个人的，那么就算买来再多的长工也无济于事。

阿姆达尔定律的结论给并行化研究的领域蒙上了一层沮丧的阴影，使得该领域像是一个一眼就能看到天花板的研究。而在阿姆达尔定律中，作者使用了两个设定作为前提。正是这两个设定让我们在1988年看到了对并行化研究不一样的前景。

阿姆达尔定律的 第一个假设是 固定负载（即计算总量不变）的量化标准 。也就是说它没有考虑到硬件发展带动下的软件更新。举个简单的例子，上世纪90年代的时候我们用英特尔奔腾处理器跑 Windows95 的操作系统，而到了如今我们有了i9处理器的同时我相信没谁的电脑里还装着 Windows95 了。换句话说，长工的技能增加的同时，地主的田地也在扩张嘛。到了上世纪80年代，Sandia 国家实验室的科学家们在使用1024个处理器时观察到了3个实际应用程序随着处理器的增加发生线性加速的现象。于是在阿姆达定律的基础上，另一个定律由此诞生—— 古斯塔夫森定律