本文经「原理」（微信公众号：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个实际应用程序随着处理器的增加发生线性加速的现象。于是在阿姆达定律的基础上，另一个定律由此诞生——古斯塔夫森定律。
古斯塔夫森定律于1988年由约翰.古斯塔夫森（John Gustafson) 提出。古斯塔夫森指出，阿姆达尔定律的问题出在它的前提过于理想化。硬件性能的提升会直接导致软件规模及复杂度提升。即使算法仍然存在着串行部分，但由于程序规模的不断扩大，算法中串行部分所占比例往往会持续减少。至此，他给出了另外一个公式：Speedup= s + (1-s)n，其中 s 是给定任务中不可并行的时间占实际执行时间的百分比，n 代表并行计算节点个数。并指出在许多实际的应用程序中，因处理器核数的持续增加而得到接近线性的加速效果是可能的。
同古斯塔夫森定律一样，阿姆达尔定律的另一个设定是假设程序中可并行的部分在实际情况中可以完全被并行。这种设定作为一个纯数学模型忽略了可并行化在执行的时候所带来的开销。于是，大卫.费舍尔（David. Fisher）于1988年发表论文“Your Favorite Parallel Algorithms Might Not Be as Fast as You Think” [1]，并提出这样一个理论。如果一个输入大小为 n 的程序在串行时需要 T(n) 个步骤来完成，那么该程序被 d 个计算节点（可粗略看作处理器核数）并行之后所需的执行步骤数会以 T(n) 的 d+1 次方根增加。这个结论将逻辑门以及铜线连接的延迟考虑进去，打破了古斯塔夫定律中线性加速效果的可能，并将可并行化的加速上限设在了一个更低却更现实的高度。同时，在铜线延迟开始超过逻辑门延迟的如今，信号已然无法在一个时钟周期内被传达到芯片的所有地方。这也同样在并行处理的过程中加入了串行依赖[2]。
和之前两期介绍到的，科学家们试图以各种新科技突破现有的物理极限不同，在并行化领域里我们现在所能达到的离阿姆达尔提出的极限还很远。多数科学家们还在试图用各种方法去接近阿姆达尔定律所提出的极限。CNFET晶体管的出现大大的改善了内部连接的延迟[3]。英特尔在2013年声称其打算用硅光产品代替原有的铜线来连接芯片中的不同核[4]。当然研究领域里也不乏试图再次突破现有体系所带来的物理极限的尝试。其中最大的项目要数对量子计算机的研究。从底层电路到计算机体系结构，再到上层的算法设计，学术界和工业界都投入了大量的精力进行研究。然而，虽然对于某些应用, 量子计算机确实在理论上会优于传统计算机[5]，但现阶段量子计算机的整个容错系统会带来巨大的开销，从而大大的抵消了其在理论上能够带来的优势[6]。加之量子计算机从本质上来讲也是一个图灵机，其程序本身的复杂程度使得即便是量子计算机也很难超越费舍尔所提出的并行化加速上限[7]。
虽然从阿姆达尔定律提出之后并行化的研究屡遭质疑，多核技术的出现与流行对计算机体系结构，算法及程序设计都带来了重要的影响和新的挑战。而未来这些方面都需要去适应多核芯片的发展。并行化的研究面临着诸多的机遇和挑战，但相信未来会有更大的突破。
