当今绝大多数的计算机都属冯·诺依曼 Von Neumann 类型的系统结构，它的基本特征是指令的顺序执行和数据共享，促使程序中指令执行的因素是事先由程序员编写好的指令执行顺序。20世纪70年代中期出现的数据流计算机以「指令执行所需的数据是否到达」来驱动指令的执行，从而打破了冯·诺依曼计算机的体系结构。

狭义地讲，新型计算机系统是指像数据流计算机这种完全不同于 Von Neumann 计算机工作方式的计算机。但有的学者将「在体系结构上作了重大改进、而仍使用 Von Neumann 计算机工作方式的计算机系统」也称为新型计算机系统，即广义的新型计算机系统。这里讨论几种具有代表性的计算机系统。

7.1 脉动阵列计算机

脉动阵列计算机（简称“脉动阵列机”）是由一组相同的处理单元 PE 构成的阵列机。每个 PE 可完成少数基本的算术逻辑运算操作。这种阵列机的工作原理是：阵列内所有处理单元的数据锁存器都受同一个时钟控制，运算时数据在阵列结构的各个 PE 间，沿各自的方向同步向前推进，就像血液受心脏有节奏地搏动，在各条血管中同步向前流动一样。因此，形象地称其为脉动阵列结构。

脉动阵列机主要适用要求计算量很大的信号/图像的处理，以及某些特定计算类算法题目的求解，特别是需要对大量数据执行重复计算的运算受限类问题的求解。根据具体计算的问题不同，脉动阵列可以有一维线形、二维矩形/六边形/二叉树形/三角形等阵列互连构形。

图7.1给出了，在一个脉动式二维阵列结构上进行两个 $3\times 3$ 矩阵 $A,B$ 相乘的例子。每个处理单元 PE 内含一个乘法器和一个加法器，可完成一个内积步运算。每经一拍，处理单元可把 $3$ 个输入端送来的信息沿三个不同方向，即由左向右的水平方向、由下向上的垂直方向和由左下角到右上角的斜 $45°$ 方向，同时将结果传送到对应的 $3$ 个输出端，使 $a^{\prime }=a,b^{\prime }=b,d=a\times b+c$ 。现设矩阵 $A,B$ 和它们的乘积 $C$ 分别为：
$$A=\left[\begin{array}{ccc}{a}_{11}& a_{12}& a_{13}\\ a_{21}& a_{22}& a_{23}\\ a_{31}& a_{32}& a_{33}\end{array}\right]B=\left[\begin{array}{ccc}{b}_{11}& b_{12}& b_{13}\\ b_{21}& b_{22}& b_{23}\\ b_{31}& b_{32}& b_{33}\end{array}\right]C=A\times B=\left[\begin{array}{ccc}{c}_{11}& c_{12}& c_{13}\\ c_{21}& c_{22}& c_{23}\\ c_{31}& c_{32}& c_{33}\end{array}\right]$$

其中，$C_{ij}=\sum _{k=1}^3{a}_{ik}\times b_{kj}(1\le i\le 3,1\le j\le 3)$ 。在图中给出了 $t_1,t_2,t_3$ 时刻送入阵列中的数据情况，到 $t_6$ 时，从 $45°$ 方向上将同时输出 $c_{13},c_{12},c_{11},c_{21},c_{31}$ 的值，$t_7$ 时输出 $c_{23},c_{22},c_{32}$ 的值，$t_8$ 时输出 $c_{33}$ 的值。可以看出，总共只需用 $8$ 拍就可以完成两个 $3\times 3$ 的矩阵相乘，比单处理机上循环执行所需的 $27$ 拍，速度提高了两倍多。

7.2 数据流计算机

美国MIT实验室的 Jack Dennis 及其助手们，于1972年首先提出了数据流 Data Flow 模型，并证明由此而设计的数据流计算机，能够满足未来计算机理想结构的三个基本命题。这三个基本命题是:

• 要获得很高的性能价格比;
• 能跟上工艺技术进步的速度;
• 在应用领域提供较好的可编程性。

数据流计算机的研究工作曾经被冷落过一段时间。近几年来，由于VLSI技术的迅速发展，为数据流计算机的发展提供了坚实的基础; 因此，无论在硬件、软件，还是在理论研究方面，数据流计算机都有了一些较大的进步，并且已经出现了一批实用的数据流计算机系统。

本节首先介绍数据流计算机的数据驱动 Data Driven 原理，着重分析与传统的 Von Neumann 控制驱动 Control Driven 计算机的不同，然后介绍数据流程序图和数据流语言，这是研究数据流计算机必须要了解的基础知识，最后介绍数据流计算机的典型结构，分析它们的系统结构和主要工作原理。

7.2.1 数据流计算机的基本工作原理

与传统的 Von Neumann 计算机不同，在数据流计算机中，一条指令能否执行的主要依据是——它所需要的操作数是否已经全部到达。因此，指令的执行不需要程序计数器 PC。一条指令执行后产生的结果并不送往存储器保存起来、以供其他指令共享，而是直接流向所有需要该结果的指令，并作为这些指令的操作数，驱动这些指令的执行。因此，程序执行时所需的数据是一次性生成和消费的，即时产生、即时使用，操作数直接以令牌 Token 或值的记号传递，而不是作为地址变量加以访问。显然，在数据流计算机中，程序中众多指令的执行是异步并行进行的，只要所需的操作数均已到达，又有可使用的计算资源，它们便可同时执行，因此最有利于计算并行性的开发。这与 Von Neumann 计算机的顺序执行、数据共享的特点完全不同。

在数据流计算机中，信息项以操作包和数据令牌形式出现。操作包由操作码、操作数和其后继指令所在地组成。数据“令牌”则由结果值和其去向目的地组成。众多的操作数和数据令牌在各个资源部件间传递，因而，数据流计算机可视为是一种信息分组通信系统结构，具有分布式多处理机组成形式。

7.2.2 数据流程序图和数据流语言

通常用数据流程序图来表示指令级的数据流程序，它是一种特殊的有向图 Directed Graph ，由多个节点和一些连接它们的弧所组成。该有向图说明了「指令之间执行顺序的约束条件」。数据流程序图中的节点除表示一般的算术逻辑操作外，还可表示常数产生、复制操作、判定操作和控制操作等。常用的节点种类有：

1. 算术逻辑运算节点
   根据节点执行的操作功能可分为算术运算节点和布尔运算节点两种。常见的算术运算节点有加、减、乘、除、加 $1$ 、减 $1$ 等，常见的布尔运算节点有与、或、异或、非等。如果按照输入端的个数，可以把节点分为单输入节点和多输入节点两种。如图7.2中的加 $1$ 和非是单输入节点，而加和与是多输入节点。
   

2. 常数产生节点
   常数产生节点没有输入端，只有一条输出线。这种节点的功能是用来产生一个常数。图7.3(a)是常数产生节点的一般示意图，图7.3(b)是常数 $2$ 的节点，及其执行操作后产生数据令牌的情况，该数据令牌携带有常数 $2$ 。

3. 复制操作节点
   复制操作节点可以是数据也可以是控制量的多个复制。如图7.3 c)、图7.3(d)所示。对于数据复制节点，图中圆点和箭头用实心表示，而在控制量（布尔量）复制节点中的圆点和箭头用空心表示。
   

4. 控制操作节点
   这类节点的特点是，其激发（或称点火）条件中要加上布尔控制端。常用的条件操作节点有如下四种：
   ① $T$ 门控节点：仅当布尔控制端为真，且输入端有数据令牌时才能激发，然后在输出端产生数据令牌、而输入端的数据令牌消失，如图7.4(a)中所示。
   ② $F$ 门控节点：与 $T$ 门控节点类似，但仅当布尔控制端为假时才能激发，如图7.4(b)所示。
   ③ 开关门控节点（$SW$ 节点）：有一个数据输入端和两个数据输出端，根据控制端值的真假确定 $T$ 输出端或 $F$ 输出端上带有输入端的数据令牌，如图7.4 c)所示。
   ④ 归约门控节点（$MG$ 节点）：有两个数据输入端和一个数据输出端，并受控制端控制。激发后，根据控制端值真假，在输出端上产生来自 $T$ 输入端或 $F$ 输入端上的数据令牌，如图7.4(d)所示。
   

5. 条件判断节点
   判断输入数据（通常是单个或两个）是否满足某种条件，如输入数据是否小于、等于、大于 $0$ ，两个输入数据的大小比较等。满足条件时，将在输出端产生 $T$ 的控制令牌，否则便产生 $F$ 的控制令牌。数据流程序图中，在空心箭头弧上流动的就是这类控制信号。图7.5中示出了单输入和双输入数据的判断操作工作情况。
   

利用上述常用节点，可以画出一些程序结构的数据流程图。例如，图7.6(a)是具有条件分支结构的数据流程图，当 $x>0$ 时，让 $x$ 加 $y$ ，否则就让 $x$ 减 $y$ 。图 7.6(b)是具有循环结构的数据程序图，实现对 $x$ 循环累加，直至其值超过 $1000$ 为止，结果由 $z$ 输出。图7.7是计算 $N$ 阶乘的数据流程序图。

数据流程图实际上是数据流机器语言，较直观易懂，但编程效率很低。所以通常流行的是数据流语言，它的语言结构类似于命令式程序设计语言，但又要能方便地被编译成数据流程图，以在数据流计算机（简称“数据流机”）上执行。

常用的数据流语言有美国的 ID 和 VAL ，法国的 LAU 以及英国曼彻斯特大学的 SISAL 语言等，它们大都是单赋值语言。单赋值的含义是指，在程序中每个变量只能赋值一次，即同一变量在赋值语句的左部只允许出现一次，不允许对同一变量进行多次赋值。数据流语言一般必须具有如下两个特点:

1. 遵循单赋值规则。这有利于运算并行性的开发，也可防止“副作用”——指在程序执行过程中修改了某些参数的值。
2. 指令的执行次序由数据依赖关系确定，这就使指令执行规则简单地只依赖于数据的可用性。

美国的麻省理工学院 MIT 是研究数据流机的发源地，由 Jaok Dennis 教授领导的研究小组提出了 VAL 数据流语言，主要用于他们所开发的 MIT 静态数据流机。而由 Arvind 教授领导的研究小组首次提出了动态数据流机概念，并开发了相应的 ID 数据流语言。对于点积这样的操作，若用 ID 语言则可写成如下的过程:

procedure inner_product(a, b, n)
initial s ← 0
for i from 1 to n do
	new s ← s + (a[i] * b[i])
return s

7.2.3 数据流计算机的基本结构

依据处理数据令牌的不同，数据流计算机可分为静态和动态两大类。

1. 静态数据流机

这种数据流机的主要特点是数据令牌不带任何标号，在任何一条弧上只允许存在一个数据令牌。数据令牌沿数据流程图中的箭头方向流动，当到达某一节点时，能否激发该节点进行相应操作，要视该节点其他输入弧上是否都已有数据令牌到达。仅当该节点的所有输入弧上都出现有数据令牌，且在它的任何输出弧上都没有令牌时，它才会被激发。

典型的静态数据流计算机的结构如图7.8所示。指令存储部件中存放要执行的数据流程序，所有已收到全部所需数据令牌的指令，将由指令部件按更新部件送来的指令地址逐个取出，送到可执行的指令队列中。此时若有空闲处理机，分派程序将按先后次序，分配处理机给等待执行的指令，使它们并发执行。执行后的结果将形成新的数据令牌，它们被送到更新部件中，由后者按它们的目的地址，送往指令存储部件内相应指令的有关位置。与此同时，更新部件将已收到所有必需数据令牌的指令地址传送给取指令部件。这样便完成了一个循环流动。

由于静态数据流机中，只允许任何一条弧线上有一个数据令牌，因此它只能处理一般循环操作。为了满足迭代要求，它必须多次重复激活某些操作节点，此外还必须设置控制令牌、以识别属于不同迭代层次的数据令牌，当数据令牌从输出弧上取走时，这些控制令牌就作为确认信号，告诉所有输入弧上已到齐数据令牌的节点，可以开始执行操作。

图7.9中示出了MIT的静态数据流计算机结构。它由处理部件、指令存储部件、仲裁网络、分配网络和控制网络五部分组成，形成一个环状流水线。其中的仲裁网络和分配网络相应于图7.8 中的更新部件和取指令部件，所增加的仅是控制网络部分。指令存储部件中存放等待执行的指令，每条指令中含有相应等待接收操作数的空位，这些空位由分配网络送来的操作数填入。当全部空位被填满时，表明该指令所需的数据令牌已全部到达，此时若表示当前指令的一次执行已经结束的控制令牌，也已由控制网络送到该指令，则此指令便可被激活。该指令连同其操作数及结果送往目的地址，形成一个可执行的操作包，由仲裁网络送往处理部件处理。

仲裁、分配和控制网络均以包交换方式通信，采用第六章所叙述的 Delta 多级开关网络加以实现。

2. 动态数据流机

动态数据流机的主要特点是使数据令牌带有标号。这样就可使数据流程序图中，任一条弧上同时存在带有不同标号（或称颜色）的数据令牌。此时，不需要像静态数据流机中那样，依赖控制令牌来确认指令间数据令牌的传送，而只要对令牌标号进行比较，就可加以识别。为此，需要有一个称为匹配部件的硬件机构，将标号附加到数据令牌上，并完成标号的匹配工作。图7.10中示出了这种动态数据流机的结构。

匹配部件将处理部件中，各处理单元送来的结果数据令牌赋予相应的标号，并将流向同一指令的数据令牌匹配成对或组，然后将它们送往更新/取指部件，由该部件将需要它们的指令从指令存储器中取出，然后将已收到的数据令牌组和取出的指令、合并成一条可执行的指令，送入可执行指令队列。由于在动态数据流机中给数据令牌赋予标号，从而可区分出不同层次的迭代执行。因此，动态数据流机可最大限度地开发数据流程序图中的并行性。

动态数据流机可分为网络型和环型两种组成形式。它们的典型代表分别是MIT的动态数据流机和英国曼彻斯特大学的动态数据流机。图7.11中示出了曼彻斯特大学的环型动态数据流机。该机进行数据流运算时，所完成的主要功能是：对数据令牌进行匹配，将匹配成功的指令从指令存储器中取出和执行该指令。这三个功能分别由图7.11中的匹配部件 MU 、指令存储器IS 和处理部件 PU 完成，部件间按流水方式工作。

为了缓冲同一时间由处理部件产生的多个数据令牌，在匹配部件之前设置了一个令牌队列 TQ 。每个令牌包由 $4$ 部分组成——数据类型 $5$ 位、数据值 $32$ 位、标号 $36$ 位和目的节点的地址 $23$ 位，总长度为 $96$ 位。匹配后，令牌包长度增至 $133$ 位（增加了另一个数据令牌值的长度 $32$ 位和类型位 $5$ 位) 。从指令存储器取出的操作码长度为 $10$ 位，再加一个可选的目的地址长度 $23$ 位，形成一个 $166$ 位长的可执行信息包，送往处理部件。操作后输出的结果令牌包又变为 $96$ 位长。

各个部件异步工作，具有不同的时钟频率。每个 PU 中有 $20$ 个功能部件，每个功能部件的最大处理速度为 $0.23\text{MIPS}$，因此 PU 的持续性能可超过 $1\text{MIPS}$ 。TQ、MU、PU 以及指令存储器构成了一个称为 PE 的流水环，该样机最多可支持 $7$ 个这样的流水环（通过开关网络连接到系统中）。样机的主机是一台 VAX ll/ 780 ，通过开关网络与流水环相接，此外开关网络还将I—结构存储器连接到系统中。

I—结构存储器是一个数据结构存储器，这是为了提高「数据流计算机在处理数据结构时的性能」而设置的。如前所述，数据流机中无共享的数据存储器，每个数据的使用都是一次性的，若要多次使用某个数据，就必须多次加以复制。对于单个标量元素，这种复制开销还不算大，但若要对整个数据结构进行多次复制，而且数据结构中包含的元素较多时，开销就很大了。例如，对于一个有 $10000$ 个元素的数据结构，如果欲将第 $500$ 号元素赋予新值，则将得到一个新的数据结构。在有共享数据存储器的冯·诺依曼机中，只需用地址读出这一元素，加以修改后再写回就可以了。但在数据流机中，还必须复制其余的 $9999$ 个元素，才能构成这一新的数据结构，因此时空开销都很大。采用传统共享存储器概念的I—数据结构存储器，就是为了解决这一问题而设置的。应注意的是，数据结构本身不在系统中流动，而是以指向该数据结构的一个指针来代替。

7.2.4 数据流计算机存在的主要问题

由前面所介绍的、数据流计算机的基本工作原理，我们可以看到，数据流计算机的最大优点是能充分开发细粒度（指令级）的并行性，因此从原理上讲，由它组成的计算机系统可获取很高的性能，但它也存在以下一些问题:

1. 指令级的数据驱动，导致每条指令的执行有较大的时间开销，因为在运行时，需要对每一次操作进行数据相关分析。
2. 由于数据流程序的操作包代码长度较长，将占用较多的存储空间。此外，由于数据流机没有共享的数据存储器，因此不能保存如数组那样的数据结构，当处理大型数组时，就要复制大量数据，造成存储空间的很大浪费，并增加很多不必要的数据传输开销。
3. 当机器规模变大时，接到转接网络上的流水环数将增加，从而使转接网络变成系统性能的新瓶颈口。

由于上述的原因，数据流机至今仍不能成为商品化机器，日本在第五代计算机的研究计划中，曾试图把数据流机结构作为并行推理机的一种实现方案，并力图使之成为商品化机器，但最终并未获得成功。但数据流机的基本工作原理及其结构，已在一些计算机特别是专用计算机设计中得到了应用。

---

7.3 归约机

归约机和数据流机一样，都是基于数据流的计算模型，只是其采用的驱动方式不同。数据流机是采用数据驱动，执行的操作序列取决于「输入数据的可用性」；归约机则是需求驱动，执行的操作序列取决于「对数据的需求」，对数据的需求又来源于函数式程序设计语言对表达式的归约。

7.3.1 函数式程序设计语言

函数式程序设计语言是由所有函数表达式的集合、所有目标（也是表达式）的集合及所有由函数表达式到目标的函数集合三部分组成。函数是其基本成分，是从一批目标到另一批目标的映射。从函数程序设计的角度看，一个程序就是一个函数的表达式。通过定义一组“程序形成算符” Program-Forming Operators ，可以用简单函数（即简单程序）构成任意复杂的程序，也就是构成任意复杂函数的表达式。反过来，如果给出了一个属于函数表达式集合中的复杂函数的表达式，利用提供的函数集合中的子函数，经过有限次的归约代换之后，总可以得到所希望的结果，即由常量构成的目标。函数表达式的每一次归约，就是一次函数的应用，或是一个子表达式（子函数式）的代换（还原）。

以表达式 $z=(y-1)\times (y+x)$ 为例，可以理解成 $z=f(u)$ ，而 $f(u)$ 等价于 $g(v)\times h(w)$ ，其中 $g(v)=y-1$ ，$h(w)=y+x$ ，也就是说，函数 $z=f(u)$ 的求解可归约成求两个子函数 $g(v)$ 和 $h(w)$ 的积，而 $g(v)$ 和 $h(w)$ 又可以分别继续向下归约。

函数式程序本质上属于解释执行方式。从函数式程序的归约来看，机器内部通常采用链表的存储结构，且依赖于动态存储分配，存储空间的大小无法预测，需要频繁地进行空白单元的回收，使空间、时间开销都较大，频繁的函数应用和参数传递，加上自变量动态取值，同样的计算往往要重复多次。所以，必须针对函数程序设计语言的特点和问题，设计支持函数式程序运行的新计算机，这就是归约机。

7.3.2 归约机的结构特点

归约机一般有如下一些结构特点：

1. 归约机应当是面向函数式语言，或以函数式语言为机器语言的非 Von Neu-mann 型机器。其内部结构应不同于 Von Neumann 型机器。例如，应采取适合于归约的存储结构和存储器结构，要有函数定义存储器和表达式存储器，而不是 Von Neumann 型机器的程序存储器和数据存储器这种组成方式。归约机的处理对象是多个运算或函数应用嵌套组合的表达式，处理器根据表达式携带的运算信息来处理表达式中的数据。因此，处理的数据和操作的信息应当合并存储，而不是像 Von Neumann 型机器那样，数据按地址存储，且数据中不含运算信息。应当有相应部件来跟踪指示表达式归约的顺序和路径，而不是 Von Neumann 型机器采用程序计数器硬件。采用适合于归约特点的、需求驱动或数据驱动的控制方式和机构，而不是 Von Neumann 型机器的按控制驱动的控制方式和机构。
2. 具有大容量物理存储器，并采用大虚存容量的虚拟存储器，具备高效的动态存储分配和管理的软硬件支持，满足归约机对动态存储分配及所需存储空间大的要求。
3. 处理部分应当是一种多处理器或多处理机并行的结构形式，以发挥函数式程序并行处理的特长。
4. 采用适合函数式程序运行的多处理机互连的结构，最好采用树形方式的互连结构或多层次复合的互连结构。
5. 为减少进程调度及进程间通信开销，尽量使运行进程的节点机紧靠该进程所需用的数据，并使运行时需相互通信的进程所占用的处理机也靠近，并使各处理机的负荷平衡。

7.3.3 面向函数式语言的归约机

归约机按其归约模型可分为串归约 String Reduction 机和图归约 Graph Reduction 机两类。两者的区分主要是对函数表达式所使用的存储方式不同，前者以字符串形式存储，而后者则以图的形式存储。

我们仍以表达式 $z=(y-1)\times (y+x)$ 为例，假定 $x=2,y=5$ 。

• 串归约方式是——当提出求函数 $z=f(u)$的请求后，立即转化成执行「由操作符 $\times$ 和两个子函数 $g$ 与 $h$ 的作用」所组成的“指令”。$g$ 和 $h$ 的作用又引起“指令” $(-,y,1)$ 和 $(+,y,x)$ 的执行。于是，从存储单元中分别取出 $y$ 和 $x$ 的值，算出 $y-1$ 和 $y+x$ 的结果，然后将返回值再各自取代 $g$ 和 $h$，最后求 $(\times ,4,7)$ ，得结果 $28$ 。这种归约方式表示见图7.12(a)。
  可以看到，串归约实际上是一种「不断地在定义表达式集合中查找和复制的过程」，而且对每次函数作用都要重复执行，因而，时间和空间的辅助开销都比较大。
• 图归约方式与串归约方式主要的不同在于，定义表达式时设置了 $z/1,z/2$ 等指针，如图7.12(b)所示。这样，下一层作用的返回结果将直接取代上一层作用的自变量，省去了归约时的复制开销；同时，实现了自变量返回值的共享，不用对同一函数作用重复执行，就可以直接引用此函数求值的结果。
  

总之，归约方式体现了按需求驱动的思想，根据对函数求值的需求来激活相应的指令。而且，不论是采用先内后外、或先外后内、或先右后左、或先左后右的顺序归约，也不论是采用串行归约、还是并行归约，都不影响最终结果值。

根据机器所用归约方式的不同，相应就有串归约机和图归约机两类。

---

7.4 人工智能计算机

近年来，人工智能技术已经在许多领域中得到了广泛的应用，例如自然语言理解、计算机视觉和机器人等。随着人工智能应用从实验室走向现实世界、以及人工智能软件复杂性的日益增加，计算吞吐率和成本已成为设计人工智能计算机时，需要仔细权衡的因素。由于传统的 Von Neumann 计算机主要是为顺序的和确定性数值计算而设计的，因此不适宜于人工智能方面的应用。

7.4.1 人工智能计算特征

人工智能 Artificial Intelligent, AI 计算机与传统的 Von Neumann 计算机不一样，因此两者的计算特征有很大差异。AI 的计算有如下特征:

1. AI 计算的主要对象是符号而不是数值，常用的基本符号操作包括比较、选择、排序、匹配、逻辑集合运算（合、交和非）、分类以及模式检索和识别等。在更高层次上，符号操作还应包括如句子、语音、图形和图像等的模式操作。
2. AI 计算是非确定计算。即很多 AI 算法具有不确定性，这是由于「缺少对求解问题的完全理解」和「缺少相应知识」造成的。因而在求解时，往往要对所有的可能性进行穷尽枚举，或是对求解空间进行有控制的搜索。
3. AI 计算是动态进行的。由于缺少完整知识和对求解过程的预见性，往往需要在求解过程中建立新的数据结构和函数。此外，由于求解问题所需的存储空间较大，无法在事先一次分配到位，因而不得不在求解问题过程中，对存储空间以及其他资源进行动态分配和回收。任务可能是动态建立的，通信拓扑也可能需要动态地变换。
4. 具有并行和分布处理的巨大潜力。在确定性算法中，往往存在有一组独立任务，可以并发地进行处理，这类并行性称为 AND 并行性。由于 AI 算法具有不确定性一面，则为并行处理提供了 OR 并行性的机会。
5. 知识管理问题。在减少 AI 求解问题的复杂性方面，知识起着很重要的作用，有用的知识越多意味着无用的搜索越少。由于知识量很大，因此必须加以管理。此外，所获取的知识可能有模糊成分，具有试探和不肯定特性。因而知识的表达、管理、加工以及知识学习都是很重要的问题。
   需要指出的是，在许多 AI 应用中，求解时需用的知识可能是不完善的，因为在求解问题时，可能知识来源还未曾知道，或者在设计时无法预见将来的环境变化，所以 AI 系统应设计成开放的，允许不断求精和能够获取新知识。

总的来讲，改善 AI 任务求解的计算效率有两个基本方法，即使用探测知识指导搜索和使用更高速的计算机。AI 处理的基本要点是有关知识的获取、表示和智慧地加以使用。就知识获取而言，AI 系统应能从视觉、声音和书写等各种信息源获取信息。由于这些信息的来源往往是不完整、不精确，甚至是相互矛盾的，因此必须对它们进行正确的识别和理解。

知识的表示主要是对有关对象、关系、目标、动作以及处理过程的信息加以编码，形成数据结构和编写成过程。知识的表示应便于增加、修改和便于对知识进行加工。目前常用的知识表示方式有语义网络、框架结构、脚本、对象、生成系统、过程模式、谓词逻辑以及关系数据库等。

知识的处理主要用于问题求解、逻辑演绎和情报检索等。常用的主要方法有状态空间的遍历、问题归约、正向和反向的勾链、分辨、规划、探试搜索以及剪枝等。在这些方法中，对输入、输出的要求远大于对计算的要求，而且操作往往是在全局范围内进行的，不具有局部性。

7.4.2 AI 计算机的分类和设计方法

AI 计算机一般可分为四类:

1. 基于语言的 AI 计算机
   这类 AI 计算机的设计目标是，高效地执行像 LISP, PROLOG, FP 等面向 AI 的高级程序设计语言。在这类机器中设有专门硬件，以支持有关语言的基本操作。如 LISP 机中采用面向堆栈的、带标志位的系统结构。 FP 计算机中采用图或链表来表示程序和数据，通常用多处理机来加以实现。PROLOG 机则需要有硬件支持模式匹配和归一的基本操作，并应有逻辑推理功能部件。
2. 基于知识的 AI 计算机
   这类 AI 计算机的设计目标是，能对具体所采用的知识表示方法如语义网络、框架、规则、对象等给以支持。比较常见的有：基于规则的 AI 计算机，如 DADO 2 以及 NON-VON 计算机；基于语义网络的 AI 计算机，如 Connection machine ；基于对象的 AI 计算机，如 FAIM-1, Dorado, SOAR 。这些 AI 计算机中通常包含有大量处理器，每个处理器的功能比较简单，且带有一个小容量的局部存储器。
3. 连接式 Connectionist AI 计算机
   在这种 AI 计算机中，知识不是用符号来表示的，而是直接编码成处理单元间的互连模式。这些处理单元既协同又相互竞争地求解问题。连接式 AI 计算机主要使用连接来实现信息的存储，类似于神经或细胞的互连。系统中每一个连接被赋有一定权值，由权值的模式来形成知识的表示。连接关系将大量的处理细胞元连接起来，每个细胞只完成非常简单的基本操作，如位比较等。在连接系统中的每个细胞元，计算所有与它相邻细胞元状态的带权和。该细胞元的新状态是该带权值和该细胞元以前状态两者的函数。
   连接式 AI 计算机的最大优点是，它能就近地同时将整个知识库系统作用于求解问题，所有细胞元是并发地活跃的，所有计算直接受控于编码在网络连接中的知识库。从原则上讲，连接式系统的求解时间是固定的，不受求解问题大小的影响。由于知识被编码在整个细胞元的网络中，而不像一般符号处理式的 AI 计算机是存放在特定的存储单元中，因此即使失去个别细胞元，对整个系统性能不会有很大影响，故具有较强的容错能力。连接式 AI 计算机的最大弱点是可编程性和可维护性较差，因此这种 AI 计算机仍处于实验研究阶段。
4. 带智能接口的 AI 计算机
   在这种 AI 计算机中，通常在人—机之间提供语音识别、自然语言理解、图像处理和计算机视觉等智能接口。这种 AI 计算机的应用针对性和实用性较强，因此有较广阔的应用前景。应指出的是，在这种系统中不单纯进行符号处理，数值计算也占有相当比例，如对语音和图像的低层次处理主要是数值计算，仅在高层次上才对音素和图像的符号表示加以处理。

7.4.3 PROLOG 推理机

由于日本于1982年开始的第五代计算机研究计划中，把 PROLOG 语言作为样机的核心语言，从而引起了对 PROLOG 推理机的研究热。充分开发存在于用 PROLOG 语言书写的程序中的各种并行性，可以加快 PROLOG 程序的执行。在 PROLOG 程序中一般存在有 AND, OR 和归一三种并行性。

• AND 并行性是指逻辑上相与的子句的同时执行，即要获得主目标的求解，必须先使所有子目标同时获得求解，但这种 AND 并行性操作，是在「所有子目标共享的变量和数据集」上进行的，因此需要进行一致性检查。
• OR 并行性是指对所有可能求解路径的并发搜索。由于与每条求解路径有关的变量和数据互不共享，因此不需要进行一致性检查。
• 归一并行性是指在 PROLOG 数据库中将所有子句进行并行匹配，并将匹配变量并发地固化为常数值。

为了支持上述三种并行性的开发，日本在第五代计算机研究计划中研制了并行推理机的样机 PIM 。该系统由多个推理模块组成，每个模块有自己的局部进程池和归一部件，如图7.13所示。一个专用互连网络将所有推理模块连接起来，进程池可通过该互连网络在各推理模块间迁移。系统中还有另一个网络，它用来连接推理模块和结构存储器模块，后者主要用来存放表、向量、矩阵以及其他的结构数据。

7.4.4 AI 计算机的研究进展

日本于1982年到1991年开展了为期十年的第五代计算机研究计划，即人工智能计算机的研究计划。受其激发，美国、英国以及西欧各国也相继在此期间，开展了人工智能计算机的研究，研制出不少样机，取得了不少阶段性成果。

日本第五代计算机的研究计划分三个阶段进行。第一阶段为三年，主要是对并行推理机的基本结构、并行推理机制以及知识库机结构等进行研究和模拟试验。阶段成果是推出了顺序推理机 Sequential Inference Machine, SIM 样机以及 Delta 关系数据库机。第二阶段用了四年时间，侧重研究并行推理机 Parallel Inference Machine, PIM 以及知识库子系统的管理软件系统。最后阶段的三年，主要是构建一个智能信息处理系统，它以 VLSI 技术实现的知识库机和并行推理机为硬件核心，并配以基本核心软件和应用软件。

由于对人工智能机的基本问题的认识还不成熟，再加上期望的研究目标定得过高，因此日本第五代计算机研究计划并不算成功。但不管如何，第五代计算机研究计划的实施，使人工智能计算机的研究前进了一大步，同时也从中获得了宝贵的经验和教训。

目前不少研究人工智能的专家认为，人工智能机研究的关键在于对人工智能软件的研究和开发，人工智能机的硬件工作平台应使用通用的高性能并行机。花费众多的人力、物力和财力去研究和开发专用的工作平台来实现人工智能机的方法并不经济有效。一般而言，用专用芯片构成的工作平台的性能仅能将速度提高 $10$ 倍，而通用芯片的速度大约每三年就能提高 $10$ 倍，这样专用机工作平台，最多能保持三年优势，然后就会被通用芯片赶上。此外，用专用芯片构成的工作平台，不但价格昂贵，而且换代升级很困难，因此缺乏竞争能力。

7.4.5 RWC 研究计划

日本在研制第五代计算机的基础上，自1992年起又推出了一个为期十年、称为真实（现实）世界计算机 Real World Computing, RWC 的研究计划。所谓真实世界，是指在不断产生变化的、不完全的、包含互相矛盾的、复杂相关的信息的世界。21世纪是高度信息化社会，需要处理的信息不但量大，而且随着多媒体技术、各种传感技术的迅速发展以及计算机的应用领域日益扩展，使得要处理的信息的质的多样化也不断增大。所要处理的这些信息往往是模糊、复杂和不确定的。人类在处理这些信息时，通常是采用直觉判断方式，这种柔性（灵活）的信息处理方式，比起传统计算机以及智能推理机采用硬性（刚性）的信息处理方式要有效得多。编程困难的软件危机，促成了对智能推理机的研究，而算法设计困难的软件危机，则促进了对柔性信息处理系统的研究。

RWC 研究计划是由日本通产省主持的，研究计划分前、后两期进行，每期时间为五年。要求最终建成的柔性信息处理系统，使任何人都可以存取和利用网络上的大量信息资源，而不感觉到计算机的存在。此外，系统应具有开放性 Openness 、强壮性 Robustness 和实时性 Realtime 。

RWC 计划的主要研究内容有以下四个方面：

• 柔性信息处理的理论基础研究。也称为软逻辑基础。其中包括：信息的柔性表示、存取和调用；各种信息的综合及各种处理模块的集成；对信息及处理模块的评价；自学习和自组织能力以及优化技术。
• 面向应用的新功能的开发研究。研究内容包括：柔性识别与理解（包括柔性的图像理解、语音理解、自然语言理解、手势理解等）；柔性推理与问题求解；柔性的人机界面（如虚拟现实）与模拟；柔性自主控制。
• 超并行计算系统。主要研究内容为：超并行系统结构及超并行软件。
• 神经系统。研究内容涉及：神经模型；其他生物功能，如人工生命、遗传算法、进化算法、生态学算法等；神经系统的硬件（VLSI 神经芯片）及软件（神经网仿真系统、神经网语言及操作系统等）。

RWC 计划中所要研制的超并行计算机系统结构，将具有如下重要特征：

• 能适应不确定计算的柔性和具有高性能的计算能力。
• 具有通用性，能支持编程的多种风范。
• 具有高安全性和高可靠性。此外需有实时处理能力。
• 具有支持并行操作系统的功能。

其中涉及到的新技术、新概念有：减少处理机间通信开销；超线程 Super-thread ；通信速率可与计算速度相比的高性能互连网络，以及对超并行操作系统的支持。

RWC 计划预定在1996年能推出 RWC 的样机系统，有 $1024$ 个处理单元，性能可达到 $100\text{GFLOPS}$ 。在对 RWC 样机进行系统评价后，将开发柔性信息处理系统的工作平台。这种平台系统将是含有百万个以上的处理单元的通用超并行计算机，性能预期可达 $125\text{TIPS}$ ，即每秒可执行 $125$ 万亿条指令。神经网系统也是超并行计算机系统的原型之一，期望规模可达到 $100$ 万个单元，速度指标为 $10\text{TCPS}$ ，即每秒可完成 $10$ 万亿次连接更新。

当然，RWC 计划的主要目标，并不单是研制一台具有柔性信息处理能力的计算机，而是在同时还要开发柔性计算所需的基本技术，包括并行系统结构、操作系统、语言以及系统支撑环境等。