计算机功能的结构，习惯上一直受到专用元件大小和人的想法的影响。微电子学正在消除这种影响

[提要]在计算机科学的发展中，过去的主要矛盾是导线便宜而元件昂贵。微电子学的发展使这个矛盾转化了。在集成电路上，元件几乎是免费的，而元件之间和电路之间的联络却成了最占空间、最花时间的东西，这个新的矛盾正在推动着计算机的形式和理论走上一场新的革命。

计算机科学的基础理论，过去主要是开关理论，目的是用最少的元件完成给定的逻辑运算。但在集成电路中，增加一些晶体管往往反而会简化导线图式，提高运算速度。在把不同集成电路结合为更大系统时，电路的测试、封装、互连问题也超过制造电路本身的问题。因此，现在问题的关键是布线图式规则化。在某种意义上，计算机科学甚至可以说就是研究结构图式规则性的科学。

现在标准的计算机中用“母线”解决长导线所引起的矛盾，使逻辑处理单元直接同存储相连，以缩短通信通路，减少开关元件。但又因为一切操作都要经过母线这个喉咙口而带来了存取信息的浪费。集成电路可以使每一逻辑单元都有存储器，使大量逻辑元件可以同时进行操作。这就是并行处理机，包括流水线处理机、阵列处理机、微型处理器系统等不同类型。

要进一步提高通信效率，不仅要研究按时间分布指令的问题，还要研究按空间分布通路的问题。这就要对时序算法进行理论分析，最大限度地减少逻辑运算。因此，计算机科学的理论基础势将包括类似拓扑学和结晶学一类的内容，这仍然是程序设计中的规则性问题，即逻辑规则性以外的几何规则性问题。

本文原载《科学美国人》第237卷，第3期，1977年9月号。作者Ivan E·Sutherland，CarverA·Mead。

计算机科学是在这样一个时代发展起来的：计算机制造工艺中导线很便宜，而开关元件却很贵。集成电路工艺却把这种情况颠倒了过来：开关元件基本上不用花钱，而导线却成了唯一花钱的元件。在集成电路中，“导线”即实际的导电通路，它们占据了大部分空间，花费了大部分时间，因而很贵。集成电路之间的导线可能是一块印刷电路板上的扁平导电通路，它占的面积大，又会造成延迟效应，因而价钱很贵。计算机理论刚刚开始考虑价钱上的这种颠倒情况。这是因为计算机的设计还没有开始利用微电子学的全部潜在能力。随着我们逐步认识到逻辑元件和接线这两者在价钱上所发生的相对变化，并利用大规模集成所固有的全部可能性，我们可以期望，将会发生一场真正的计算革命，这不仅是计算机形式的革命，而且是设计、使用计算机所根据的理论的革命。

为什么计算理论也要修改呢？假定有人打算提出某种计算理论，希望它能实际达到两个目的：规定可计算什么的上限和指导计算机的设计与使用。这样的理论大概会加深我们对计算程序的理解，也许还能对认识和思维的本质投以光辉。这种理论可能是纯粹根据数学推理，也可能是根据物理学的基本原理。单凭数学推理，勿需求助于物理学原理，也能证明许多有关计算机的问题。但如果同时考虑到物理学原理，对一个已知物理容积的计算机必须花多少时间才能完成一个给定的程序，就能作出更加定量的回答。这是因为，信息在计算机内不可能移动得比光还快；而且，按照一定的可靠性表现一个位（bit），也即一个二进制位数的信息，也需要花费一定数量的物质、能量和空间。

计算机科学今天的实际应用，几乎完全是根据数学推理。它涉及在计算装置内进行的逻辑运算。它只是略微触及逻辑装置按空间分布的必要性，这种必要性迫使人们在装置之间设置许多通信通路。计算机科学今天的实际应用也很少涉及：这种通信在物理上的局限性怎样限制了一台物理上可实现的计算机所能完成的计算复杂程度。

某种程度上情况确实是这样，因为任何人只要把计算机看成是一台对数据进行逻辑运算、数值运算或代数运算的逻辑机，他就会自然而然地用这些学科的数学记数法看待这台机器。在这些记数法中，一页中写在这里的符号X同写在同页中那里的符号X，意义上完全相同。正如在一个计算机存储装置中所表现的那样，如果要求这些数值完全相同，那么计算机的空间必须要有通信通路。可是，这种需要通信通路的观念在记数法中是不存在的。记数法本身集中注意逻辑运算，反映人类在某一时间只能最有效地思考某一件事。一种数学证明就是我们在一段时期内专心思考的一系列数学步骤，因而我们也很容易认为计算装置在某一时间只做某一件事。计算机内部并不需要这种对数学来说按时序进行计算的方法，但是我们通常用来处理问题的数学方法，也不会促使我们考虑时序法以外的其他解题方法。目前运转的计算机几乎都是按时序对数据逐步、逐项地进行运算的。

过去，由于逻辑元件速度慢、价格高，而导线相对来说速度快、价格便宜，因而还可以忽略通信费用。时序机适用这种工艺，因为可以用最少的开关元件来制造。过去，我们一直被自然的倾向、被我们所习惯的数学计数法、被工艺的原因束缚，而发展的某种类型计算机和一大批计算理论，现在都由于集成电路工艺的发展而过时了。我们之所以有可能忽略物理学原理对计算机内部通信通路所施加的限制，因为这种通信并没有明显地减慢我们的运算速度，而且费用也只占计算机制造成本的一小部分。集成电路工艺使逻辑元件基本上不用花钱，只剩下通信费用成为主要费用，这就迫使我们不仅在所制计算机的种类方面，也在计算机的理论基础方面卷入一场革命。

发展一种新的计算机理论基础是不容易的，这项工作的确已经部分地被推迟了，因为很难把逻辑概念同拓扑学、时间、空间、距离的概念结合起来，以适应一种新的理论的需要。本文将概述一下这样一种理论所必须包含的要点，首先检查一下一种简单的现有理论用于小型逻辑网络的不足之处。然后再看看，接线与逻辑元件相对价格的改变将怎样必然改变将来制造的计算机的性质。最后还希望概述一下某些适合于这种新型结构的计算理论的要点。这样一种理论将完全不同于计算机科学现有的基础，所以我们有理由认为，集成电路工艺对计算机设计和智能结构的影响都是革命性的。

大多数计算机科学课程都包括一门开关理论课，尽管它大都与现代计算机的应用无关。开关理论是为了帮助设计自动电话系统中用继电器操作的开关网络而提出的，可指导设计人员用最少的继电器把完成某一给定逻辑运算的网络公式化。这个理论已扩大到逻辑元件的新型网络（例如常规逻辑门最少的逻辑网络）的设计。

然而，这并不能保证这样一种数目最少的网络在集成电路中所占空间最小，也不能保证它完成任务的时间最短。集成电路的设计师们发现，他们常常可以在一个设计中增添一些晶体管而节约空间和时间，因为在这种网络中加入若干晶体管，可以简化设计中导线的图式并提高运算速度。开关理论的确可以把开关元件的数目减至最少，但却忽略了通信通路的代价和时延。根据目前的工艺，电路面积中元件之间的联络所占面积通常远远超过开关元件所占面积，而且联络时延要比逻辑时延大得多。因此，这种把计算任务的费用减至最少的理论，不仅要考虑到开关元件在面积与时间方面造成的费用，还要考虑到由于把数据从一处传递到另一处在更大的面积与更长的时间方面造成的费用。今天的开关理论是根据一种已经过时了的价格作用，对集成电路的设计大都无用。

把集成电路结合到更大的系统中去时，开关理论在设计阶段用处更小。在大多数情况下，集成电路的测试、封装、互连费用比制造电路本身的费用要大得多。这种费用大部分同电路所包含的特殊功能无关。即使不管电路的成本，从一块集成电路片到另一片之间的联络比同一块集成电路片上的联络要慢得多。给你一本标准电路的产品目录，就会有许多因素促使你引进更为复杂的集成电路，因为只用不多几个就能降低封装和互连的高昂费用。事实上，设计人员也往往说明集成电路里包含一些多余的元件，去掉这些不需要的开关元件成本也不能有所降低。开关理论对这样一些有关成本和速度的重要问题却毫不理会。

到目前为止，通路的费用问题在计算机科学的理论成果中虽然还没有真正的地位，但在实际设计人员的设计中却起了作用。西摩· 克雷（Seymour Cray）曾设计了许多功率最大的计算机，他举出“导线帘子厚度”和“散热”是计算机设计的两个主要问题。显然，控制互连的几何结构是非常重要的。如果连接可以按规则的图式进行，那么花费较小，占的空间也较小，因而速度也较快。

如果不能把互连路线的几何图形仔细地加以控制，当需要连接的逻辑元件数目增加时，互连路线所需空间的增加就会超过线性的增长。这种非线性增长的原因是，较大系统不仅需要较多的导线，而且导线的平均长度也比较长。由于互连通路在数量和长度两方面都增加了，用于联络的总面积或体积也就不按比例而增加：器件如排列杂乱，互连两倍的器件则需要四倍的联络空间。为了提供较多的接线空间，较大印刷电路板上元件之间的间隔应比较小印刷电路板上的间隔宽；正如洛杉矶市高速干线应比佐治亚平原的更为拥挤。

较长的通信通路，不仅要占大得多的空间，作用速度也比短通路慢得多。这是因为，即使以光速传播的信号，也要一定的时间才能穿过通路，此外，还因为较长的通路可以储存较多的能量。（在集成电路内部，光速所规定的速度极限还不是重要问题，因为相对于逻辑元件的转换时间相比，距离还是短的；因能量储存而造成的延迟作用却很重要。）要把某一个信号通路从一种带电状态转换为另一带电状态，必须散去在通路中储存的能量，把它变成熟。因此，必须设计一个功率较大的激励电路，为快速转换长导线提供较大的功率，否则就得容忍较多的能量通过一个功率较小的激励电路所引起的时延。功率较大的激励电路自己也要激励，因此不仅所占面积更大，而且速度也比小激励电路慢得多。

此外，功率较大的激励电路所产生的热量还必然散入到也占空间的某种结构中。很有可能，某一工艺传输信号所需能量和散热结构的大小，给这种工艺所能制造出来的系统的复杂程度规定一个上限。超过这个限度，为提供空间（以容纳激励较长导线所需电路）而造成的导线长度的增加，就可能超过原来使用功率较大的激励电路可能造成的导线长度的增加！迄今还没有任何理论谈到这种可能性给予速度和复杂性所规定的极限。

互连增加得不成比例，可以通过把互连图式设计得很有规则而加以避免。集成电路中的布线图式和集成电路之间的互连图式，已出现一种非常规则的趋势。例如，唯读存储器就是以一种简单而又非常规则的集成电路图式实现复杂而又不规则的逻辑功能的。这种规则性是可取的，因为它不仅简化了这种功能的规格，而且从互连的观点看，还可能是最有效的布线图式。我们相信，规则布线图式在未来的设计中的作用将越来越大。在某种程度上，计算机科学将成为研究结构图式规则性的一门科学。

一个典型的计算机，其结构包括单个逻辑处理单元，这个单元通过由20到100根长导线组成的“母线”（bus）同随机存取存储器相连。母线，正如其英文名称bus（公共汽车）所表示的那样，给数据提供公共交通工具，实际上却像一条电话合用线。通信母线通常是一条50到100英尺长的柔性电缆。为母线规定的信号传递方式，是使所有与母线相连接的设备都能以同一方式进行联络，并能避免相互干扰。计算机采用母线结构的主要优点，是任何连到母线上的设备都能直接同所有其它设备联络。而且，这种方案和母线结构可经历几代硬件的发展，从而使整个计算设备可以采用新的存储器、新的输入- 输出装置，甚至是新的处理单元。另外，在连到母线上的每个单元中，用于联络的开关元件也可以减至最少，因为每一单元只需同一条母线联络便可以把消息送到任何地点。

母线结构的缺点是它造成一条通信喉咙口。一台典型的计算机，假定存储容量为100万字（3200万位），而存储器由2,048个集成电路组成，每个电路约可存储16,000位。每一次查询存储器，都有可能从2,048集成电路中的每一电路读出128位信息值。集成电路所存取的25万位信息中，只有2,048位（一个电路中取一位）传送到集成电路组件外面，而这2,048位中又只有32位经过通信母线传送到计算机的逻辑处理单元。假定通信母线把存储器和逻辑处理单元连接起来——实际上我们是讲通信母线把它们隔离开来。在一台大型计算机中，存储器每次存取，只能选取很少几位经存储器母线传送到中央处理单元，在存取上就会浪费数以千计位信息量。人们之所以容忍这种浪费，有两个理由。第一，它简化了我们对计算机的概念，同一次只做一件事的自然倾向一致起来。第二，它给计算机各部件之间提供了一个简单的联系方法。

我们为这一方便付出了很高的代价。在存储器和逻辑处理单元还要用别的工艺制造的时代里，我们很少有选择的余地。可是现在，当硅集成电路主宰了计算机中的存储任务和逻辑处理任务时，就没有什么理由再继续忍受这种浪费了。现在已能把存储器母线分布在几千个集成电路上，使每一逻辑单元都有存储器，信息只要移动不到1毫米的距离就能从存储器到达处理设备。而存储器和处理设备都处于同一块集成电路中，几千块集成电路片都是这样。我们才刚刚开始探索这种打破传统结构的系统。为了有效地运用这种系统，我们必须学会使许多已知问题的复杂程度同在我们所能制造的系统中的简单、固定的联络图式相配合。

大量逻辑元件能同时进行操作的计算机，叫做并行处理机。（诚然，某种程度上每一台计算机都是并行处理机。共同表现一个数字的各个位在平行的通信通路上同时移动；二进制加法由一个加法电路对这个数字的各个位同时操作而完成；乘法或者由连续相加完成，或者按更快的方式，以包容许多个分离的加法电路且进行并行操作而完成。然而，超过基本算术运算水平以上的并行操作，今天的计算机中还很少见。）现有的真正平行处理的最简单形式，还只是几个独立的处理机共同操作于公用的存储器；一个典型的大型计算系统要有二个到几十个处理机同时操作。然而就典型来说，这种处理机具有完全独立的功能，连它们的存在甚至也可以瞒住用户。例如，操纵磁带或磁盘的输入- 输出装置，或者调度中央处理机的资源，就可以把分开的处理机同用户的键盘相连。这种“多重处理”系统对于用户算法，影响很小。

真正能算作并行处理机的系统，已造出了三种。其中一种是“流水线”处理机，里面执行特定任务的处理元件一个接一个地依次连接起来。待处理的作业流过处理机，正像工件沿装配线而移动。通信是简单的，因为信息只沿着一条固定的通道流动，而且不同的处理步骤之间距离很短。流水线处理机提高效率的根据同装配线一样：功能专门化，通信缩到最少限度。流水线操作可以使高速计算机的运算部分以最高速度处理数序。如果待完成的任务变化极度不定，流水线处理机就不那么有效了。

在第二种类型的并行处理机中，许多相同的处理元件在单一的指令序列控制下解决同一问题的不同部分。这样的机器已制成许多台，其中最大最有名的是ILLIAOIV。兰德公司（Rand Corporation）新建的一个流体动力模拟车间已提出制造这种新式并行处理机。这台假想的机器中要有10,000个处理器，每个都具有运算能力和记忆能力，每个都造在一块集成电路上，都接受一个公用指令装置的命令。所有的处理器都严格地同步执行命令。把这些处理器排成100×100的方阵，每一处理器只同东、西、南、北四个方向上相邻的处理器交换数据，并在每个方向上的单一导线中进行较慢的位串行通信。我们估计，这样一部机器大约要用5微秒的时间才能把一个64位的数从一个处理器传送到相邻的处理器。以今天的标准来看，这太慢了。当然，它能在任何一个5微秒的周期内传送10,000个这样的数。它也能用大约5微秒完成一次乘法运算，但也能用这段时间完成10,000次乘法运算，因为乘法运算的平均速度为每秒20亿次。像这样一部机器，叫做阵列处理机或单指令流、多数据流机。对于高度规则的任务，如流体动力学计算、天气的数值模拟、大矩阵反演等，用它们是再合适也没有了。

第三种类型的并行处理机则是：其中若干分立的独立处理器在分立的自备控制结构下完成任务的各个独立部分，并根据需要交换数据和指令。当然，微型处理器的出现使许多人想到，有可能制造由几千个分立的微型处理器组成的系统，可以对巨大任务协调工作。这样的多指令流、多数据流机，还造得很少，对它们的性能也了解得很肤浅。

对这三种类型的并行处理机，在设计或使用上都要求发现某些方法，使它内部的简单通信图式可以适应于待解决问题中固有的通信任务。随着集成电路工艺的发展，将会出现速度更快、复杂程度更高的单个电路。然而，信息从一个电路传到另一电路所造成的延迟和成本的问题，还看不出有什么解决的办法。为了更有效地通信，要连接更多的集成电路，要有更大的地方来容纳，要有更多或更大的通信激励电路，从而还要散掉更多的热量。为了使大型计算系统的性能得到最大程度的发挥，程序设计人员将不得不面对物理实在对通信所施加的限制。

由于从每个元件到每个其它元件的通信效率不高，程序设计人员将必须使他的解题公式与现有的通信通路相适应。虽然这是一个艰巨的任务，但如能成功，计算机的处理能力将空前提高。

我们相信，正如计算机科学目前所关心的主要部分是按时间分布指令的顺序，未来计算机科学的主要方向将是研究按空间分布通信通路。如果处理器只能同紧邻通信，那么有哪几种可能的安排呢？显然，可以把处理器排成一条直线。这些处理器可以按上述的流水线方式工作，每个处理器把数据依次传给下一个，或根据中央指令装置的命令进行共同操作。这种近邻连接对于像分类等任务是高度有效的，因为只要局部交换数据就够了。另外还可以把处理器连成阵列，使每个处理器有二个以上的邻居。这种阵列的基本结构很像晶体结构，可以进行各种形式的局部通信。在我们加州理工学院实验所中，我们正在考虑这种结构可能形成的不同通信通路的性质。

几年以前，当时在贝尔实验所工作的R · S · 盖恩斯（Gains）和C · Y · 李（Lee）描述过三种不同类型的互连通路。一种类型是：互连通路对所有的处理器是公用的；对于把指令送给各处理器，把计算过程中某些重要值“广播”给所有处理器，它是有效的。第二种类型的通信通路，能使每个处理器同时对相邻的处理器进行“谈话”。这种通路能按流水线的要求进行通信，如果每一处理器本身具有存储功能，这种通路还能同时把信息从所需位置上移开，在存储器的任何地方打开一个空位。第三种通路能使若干处理单元说出它们共同处理的某些结果，这种通路能够指明，究竟是没有处理器、有一个处理器还是有一个以上的处理器包含着某种已知条件，它也能够指明，哪一个处理器包含着最小值，哪一些处理器处于某一特定线上的头尾之间。

对时序算法的理论分析，已成为当代计算机科学的奠基石。为时序机选择有效算法的理论已有许多，并在不断发展。不出所料，这些理论都在集中探讨各种算法，使完成某些任务所需的逻辑运算的次数减至最少限度。例如前已指出，如果要把数排成序列，最好采用各种“快速分类”算法，因为它们只需进行n(log?n)次比较。这类理论假设在存储器中所有数据元的可接近性都是相等的，而且数据的传输都是自由的。

但是，存储器内诸数据元的可接近性绝不是真正相等的，尽管可以人为地把所有数据元的存取时间都放慢到最难接近的数据元的存取时间，从而使它们在一个随机存取存储器中的可接近性相等。由于随机存取存储器中的信息须作长距离传送，因此，现有工艺制作的随机存取存储器中的数据传送速度，不可避免地比更有条理的按序存取装置所能达到的数据速度要低。而且，数据由存储单元传送到比较电路，也从来不是真正自由的：大多数计算机的传送时间都大大超过比较时间。例如，对算法进行分析以表明哪一特殊分类算法最好，就是根据某种计算机执行这种算法的情形来判断的，但这种机器可能并不是最佳的；如果把这个任务交给另一种结构的计算机去完成，分类可能完成得更快。

算法理论的工作还没有集中探讨计算费用和通信费用之间的真正关系。假定有一块空白硅片，在上面怎样布置导线、逻辑门电路等等，人们可以自由作出决定，那么，选择什么才能在最短时间内和最小硅片面积上完成给定的计算任务呢？我们没有任何根据对计算结构的安排作出合理选择。我们对某一特定结构——对具有随机存取存储器的时序机，的确已有大量经验。也许这类计算机效率是高的，因为在总体上它最能适应各种各样的计算任务。但是越来越多的证据却又说明，并行结构对于执行适合于并行运算的任务，可以胜过普通计算机好几个数量级。随着这类非传统结构的出现，人们正发现它的应用范围也越来越广了。人们当然期望，注意降低系统方面的实际成本，也即通信系统方面的实际成本问题，以进一步提高性能，而不是仅仅考虑逻辑处理的成本——一种现在几乎快没有了的成本。

我们相信，正确阐明通信成本的适当理论，将成为计算机设计的重要指导，而集成电路的革命提供了这种可能性。我们也相信，这种理论的基础将建立在对规则性的研究上，因此，计算机科学势必包括类似于拓扑学和结晶学的许多理论。这样的发展虽然带有革命性，但本质上还是所有程序设计任务中探讨规则性的继续。因此，计算机科学家们只要在他们已开始熟悉和重视的逻辑规则性问题中，把几何规则性问题也加进去就是了。

（陆秉正译，东川校）