10.1　并行计算

1965年，戈登·摩尔注意到一种称为晶体管的基本元件在单块计算机芯片上的数量每年都在急剧增加。摩尔大胆预言，单块芯片上的晶体管数量大概每两年就会翻一倍，这一趋势将持续至少10年的时间。现在人们称其为“摩尔定律”，这个定律从1975年直到今天都有效，甚至在今后的很多年内都将有效。

在很长一段时间里，摩尔定律意味着计算速度的飞快提升。2005年前后，计算机开始触及物理极限，即让处理器跑得更快一点所消耗的能量超过了提升的速度能够带来的好处。人们反而要稍微降低处理器的速度，以改进能源的消耗。

然而我们还是往芯片里塞更多的晶体管。要这么多晶体管做什么用呢？现在这些芯片在同一时间可以做几件事情，以并行的方式工作，从而比同一时间只做一件事的方式更快地解决问题。

让我们来看一台特殊的机器：IBM公司的华生（Watson）。2011年2月，它在竞猜节目Jeopardy的第一集中得了冠军。华生由90台IBM POWER 750服务器组成，每台都有4个POWER7处理器。一个POWER7处理器的内部其实有8个处理器（也叫核心），所以它能同时做8套运算。这样，每台服务器就有32个核心，而华生系统一共有2880个核心。华生能同时做2880套计算，所以它能理解Jeopardy中给出的“答案”，并判断每一环节中是否该抢先对手按下抢答器。根据摩尔定律，在不远的将来，2880个并行处理核心显得微不足道，几十年后我们可能有百万核或几十亿核的计算机。

并行技术的发展对很多计算机科学领域提出了新的技术要求。一台计算机如何决定怎样把计算量在数个核心或是数台电脑上分布开来，以达到最佳的效能？我们需要考虑多核计算机因素并重写我们的通用编程语言吗？如果需要，该如何做呢？

P/NP问题同样受到并行技术的影响。记得本书开篇提到的《查理和巧克力工厂》中的小女孩维鲁卡·索尔特吗？她想要找到藏在巧克力包装纸里的金券。她爸爸就采用了并行技术，把大量的巧克力分配给几百个剥花生壳的工人，让她们同时来找金券。人们也可以这样来求解NP问题，把所有可能是团的集合分配给几台计算机以及每台计算机的几个核心。这可能会让一个持续数周的计算在几小时内结束，但对于某些NP问题的求解还是没什么帮助。如果我们动用100万台计算机，每台有10亿个核心，每个核心每秒能进行1×10¹⁸个操作，仍然需要花费几乎10¹⁰⁰倍于宇宙寿命的时间。P/NP问题在并行的世界里仍然是有效的。

而那些P类的问题，即我们能高效地解决的问题又怎么样呢？我们能最大限度地利用多计算机和多处理器的优势吗？大多数情况下我们可以通过修改算法来实现这一点。从基本的算术到找最短路径再到匹配问题，所有这些问题都有能扩展到多核来并行计算的算法。

像P和NP一样，对于那些能用并行算法快速解决的问题集合我们也起了一个名字，叫做NC，代表Nick's Class，它得名于并行算法的先驱尼古拉斯·皮彭格。如果P=NC，那任何一个我们能高效解决的问题，都能通过并行计算更快地解决。我们不知道是否有P=NC，更不知道是否有NP=NC。NP=NC意味着每一个NP搜索问题都能用极快的速度在并行计算的计算机和（或）核心上找到有效的解，这预示着一个比P=NP更加美妙的世界。NP=NC的可能性很小，但它和P=NP一样，也是一个巨大的未解之谜。