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

按照图灵（Alan Turing）给出的计算机模型，计算机是由一个有限状态读写头和一个存储器构成。有限状态读写头从一个初始状态开始，对存储器上的（输入）数据进行读或写操作，经过有限步操作之后停机，此时存储器上的（输出）数据就是计算结果。这样的计算机模型叫做图灵机。下面是一个非常简单的图灵机例子：它会从左至右扫描一串二进制数字，如果该数字能够被3整除（是3的倍数）则在该数字串的末尾写出Y，否则写出N，然后停机。

—————————

| 有限状态读写头 |

—————————

               ||

               \/

             ——————————————————————————

             | 10101                          （无限长）存储带

             ——————————————————————————

这个读写头共有3个状态，“状态一”为初始状态，按如下方法从左至右扫描存储带上的数字或写出字符：

状态一：读入为0，留在状态一，读入为1，进入状态二，读入为空，写Y, 停机。

状态二：读入为0，进入状态三，读入为1，进入状态一，读入为空，写N, 停机。

状态三：读入为0，进入状态二，读入为1，留在状态三，读入为空，写N, 停机。

例子中存储带上的输入二进制字符串代表十进制数21，是3的倍数，的确读写头扫描完毕后会写出Y并停机。

图灵机模型对于一大类有限步数可计算问题给出了一个普适性的定义。每一个这样的问题都存在一个图灵机可对其进行计算给出答案。我们知道对有些问题随机方法比确定的方法要快。比如用杆秤秤重时，随机拨动秤砣的方法要比任何确定性的拨动秤砣方法更快地找到所秤物体的重量。随机计算方法的图灵机模型可以在基本图灵机上外加上一条存储带，存储着随机数串供有限状态读写头读取。

在如上图灵机的例子中我们可以把有限状态读写头看作是机器的程序执行代码，而存储带上存的只是被处理的数据。图灵在描述他的另一个机器模型Universal（通用）机器时还提出了可以把有限状态指令也存放在存储带上，让读写头根据读入的指令进行下一步操作。可以证明这样存储有指令的通用图灵机能够实现任何一个图灵机，比如我们在上面给出的专用图灵机，也就是说可以解决任意一个图灵可计算问题。现在我们广泛使用的计算机的确就是采用了存储指令这一原理因而可以解决“万能”计算问题的。具体实现方法是：对于需要解决的问题用软件编制程序，再把程序和数据都存放在同一个存储器（内存）里，由中央处理器（CPU）根据指令对数据进行操作。这样的机器也叫做“存储程序计算机”（stored program computer）。在为第一台存储程序计算机EDVAC研发计划做顾问时，约翰·冯·诺伊曼（John von Neumann）写了一个草案报告描述了这种带有中央处理器、内存、I/O、总线的存储程序计算机。所以存储程序计算机还有另外一个学名，叫做冯·诺伊曼体系架构（Von Neumann Architecture）。

在我们今天使用的存储程序计算机里，与中央处理器直接发生操作关系的存储器通常叫做内存。内存的读写速度快，能够与中央处理器的速度相匹配，但是价格昂贵，而且是挥发式的，即断电时所存储的内容立刻丢失。所以外部存储器（外存）就成了现代计算机发展过程中的一个不可缺少的组成部分。低速、大容量、非挥发、廉价的外存对应于高速、小容量、挥发、昂贵的内存，前者对于后者是一个非常有效的补充。两者通过I/O进行交互。早期的外存有穿孔纸带、卡片、磁带，后来又有软、硬磁盘、光盘，如今发展到半导体固态外存（如闪存）。

值得注意的是，半导体固态外存的速度越来越快，相信以后新技术的出现一定可以使这类外存的速度与内存的无甚差别，而且固态外存的价格也正在飞速下降（从08年一季度到09年一季度闪存硬盘价格环比下降了76%）。于是我们自然就有了如下的想法：未来的计算机是否还需要有内、外存储器之分呢？

如果把一台机器看作为单个处理器，从这个角度来看，我相信内、外存储器用I/O相连的这种现代计算机体系架构将会逐渐消失。图灵本来给出的计算模型就根本没有内、外存储器之分的概念。我想外存的发展完全是由于内存在实现技术上存在着发展过程上的局限性所造成的。内、外存储器之分并非计算的本质。所以与之有关的技术如AutoSave, Swap, Checkpoint等等也会随着内、外存储器区别的消失而消失。

然而通信早就成为现代计算机体系架构中的一个极其重要的组成部分。计算机由于互联通信而应用价值大大增加。在现代计算机的通信模型上，内、外存储器在概念上和使用上还会有很明显的差别。在当前正在发生的云计算的模式上，计算机的通信模型又有很有意思的发展。将在下文讨论。
 

图灵机模型从来就不考虑通信在计算中会有什么用处。正相反，图灵还就是偏偏提到过如果把两（多）部机器相连接使之互相通信，则连接好的机器与单个一部机器没有任何两样！所谓没有任何两样是指单个机器与两（多）台互相通信的机器要么都可以计算某个问题，要么都不可以。所谓可以计算是指图灵可计算概念。它在乎一个问题是否可以由一个图灵机在有限步数内完成，而不是在乎计算效益。比如我们可以很容易写出一个图灵机完成以下问题：输入为一个二进制数字，输出为该数字的一进制编码。比如输入为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的分布服务器上进行并行处理。这就是我在前一篇中提到当前在云计算的模式上，计算机的通信所带来的很有意义的新发展。

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

转载本站文章《计算机模型与体系架构的发展——从图灵机到云计算机》,
请注明出处：https://www.zhoulujun.cn/html/theory/ComputerScienceTechnology/Constitution/2015_0729_217.html