计算机模型与体系架构的发展从图灵机到云计算机（2）

图灵机模型从来就不考虑通信在计算中会有什么用处。正相反，图灵还就是偏偏提到过如果把两（多）部机器相连接使之互相通信，则连接好的机器与单个一部机器没有任何两样！所谓没有任何两样是指单个机器与两（多）台互相通信的机器要么都可以计算某个问题，要

图灵机模型从来就不考虑通信在计算中会有什么用处。正相反，图灵还就是偏偏提到过如果把两（多）部机器相连接使之互相通信，则连接好的机器与单个一部机器没有任何两样！所谓没有任何两样是指单个机器与两（多）台互相通信的机器要么都可以计算某个问题，要么都不可以。所谓可以计算是指图灵可计算概念。它在乎一个问题是否可以由一个图灵机在有限步数内完成，而不是在乎计算效益。比如我们可以很容易写出一个图灵机完成以下问题：输入为一个二进制数字，输出为该数字的一进制编码。比如输入为111（十进制7），输出为1111111。这个问题的计算时间与所需空间复杂度可以用输入中含有比特数目的指数函数来表示，所以是一个很低效的算法，但是它的确是一个图灵可计算问题。又比如这样的问题：写出根号下2的所有十进制数（1.414213…）。这显然不是一个可以在有限步数内完成的任务，无论连接多少台机器也无法改变该问题图灵不可计算的性质。

先从算法加速来讨论。我们日常要计算的问题不光都是图灵可计算的，而且大量的问题都是多项式步数内可以解决的问题（即算法时间空间复杂度是输入比特数的一个多项式，又叫tractable或叫易解问题，而上面提到的二进制转换为一进制问题具有指数复杂度，是intractable或难解问题）。许多易解问题都可以采用并行计算方法来加速求解。一个好的并行算法甚至可以达到线性（理想）加速，即使用p台处理器解决该问题的计算用时是使用1台处理器计算用时的1/p。比如快速排序（quicksort）就是一个可以线性加速的问题。因为快速排序可以用“分而攻之”（divide-and-conquer）的方法来求解，一个大问题可以分成p个彼此无关的小问题用p个处理器并行处理。现今很有名的（由于Google的推广工作）MapReduce函数编程方法是一个可以对任何大型可分解计算问题先做分解，将分解而得的许多小问题发出（Map function）到许多分布机器上并行处理，然后对返回的非完整结果做组合（Reduce function）得到完整结果的一个通用程序设计方法。用MapReduce方法可以对许多大型数据处理问题作有效的并行加速处理。

以前要处理一个并行算法问题不是谁想要做就可以做到的。至少需要使用专门的超算中心。如今云计算的兴起使得超算中心不再那么遥远不可及。而MapReduce方法的推广也使得采用并行计算方法来解决大型、大量数据处理的问题变得不再那么专门化了。Google在推广MapReduce上起到了很有益的作用。然而Google的MapReduce可以说是Google工程师们自用的工具，而不是一项服务。开源社区的Apache Hadoop项目实现了开放源代码的MapReduce工具。上周（4月3日）又欣闻Amazon推出了Amazon Elastic MapReduce服务（也是用Hadoop实现的）。也就是说一般用户都可以使用该服务对自己的大型计算、数据处理问题定制自己的并行处理算法，广泛分布到EC2的分布服务器上进行并行处理。这就是我在前一篇中提到当前在云计算的模式上，计算机的通信所带来的很有意义的新发展。

计算机通信网络的无所不及在云计算时代出现的另一个很有意思的现象将在下文讨论。