第8章__其它计算机结构.

1、第第8 8章章 其它计算机结构其它计算机结构8.1 8.1 脉动阵列机脉动阵列机8.2 8.2 大规模并行处理机大规模并行处理机MPPMPP与机群系统与机群系统8.3 8.3 数据流机数据流机8.4 8.4 归约机归约机8.5 8.5 智能机智能机本章重点：本章重点： 脉动阵列机原理和结构特点，大规模并脉动阵列机原理和结构特点，大规模并行处理机行处理机MPPMPP与机群系统的特点，数据流机的与机群系统的特点，数据流机的原理和组织，归约机结构特点和两种形式，原理和组织，归约机结构特点和两种形式，智能机的特点和组成。智能机的特点和组成。本章难点：本章难点： 脉动阵列机原理和结构特点，数据流机的脉动

2、阵列机原理和结构特点，数据流机的原理和组织，智能机的特点和组成原理和组织，智能机的特点和组成。8.1 8.1 脉动阵列机脉动阵列机8.1.1 8.1.1 脉动阵列结构的原理和特点脉动阵列结构的原理和特点 脉动阵列结构是由一组处理单元脉动阵列结构是由一组处理单元PEPE构成的构成的阵列。每个阵列。每个PEPE的内部结构相同，一般由一个加的内部结构相同，一般由一个加法法/ /逻辑运算部件或加法逻辑运算部件或加法/ /乘法运算部件再加上乘法运算部件再加上若干个锁存器构成，可完成少数基本的算术逻若干个锁存器构成，可完成少数基本的算术逻辑运算操作。辑运算操作。 阵列中的输入数据流和结果数据输出流可阵列中

3、的输入数据流和结果数据输出流可各自沿着多个方向向前推进。就好象血液受心各自沿着多个方向向前推进。就好象血液受心脏压力有节奏地搏动在各条血管中同步向前流脏压力有节奏地搏动在各条血管中同步向前流动一样。动一样。 脉动阵列机主要适用要求计算量很大的信号脉动阵列机主要适用要求计算量很大的信号/图象的处理，以及某些特定计算类算法题目的求图象的处理，以及某些特定计算类算法题目的求解，特别是需要对大量数据执行重复计算的运算解，特别是需要对大量数据执行重复计算的运算受限类问题的求解。受限类问题的求解。 根据具体计算的问题不同，脉动阵列可以有根据具体计算的问题不同，脉动阵列可以有一维线形、二维矩形一维线形、二维

4、矩形/六边形六边形/二叉数形二叉数形/三角形等三角形等阵列互连构形，如阵列互连构形，如207207页图页图8.18.1所示。所示。 例：例： 在一个脉动式二维阵列结构上进行两个在一个脉动式二维阵列结构上进行两个3*3矩阵矩阵A、B相乘的例子。如相乘的例子。如207207页图页图8.28.2所示。所示。脉动阵列结构的主要特点：脉动阵列结构的主要特点：1、结构简单、规整，模块性强，可扩充性好。非、结构简单、规整，模块性强，可扩充性好。非常适合用超大规模集成电路实现。常适合用超大规模集成电路实现。2 2、PEPE间数据通信距离短、规则，使数据流和控制间数据通信距离短、规则，使数据流和控制流的设计、同

5、步控制等均简单规整。流的设计、同步控制等均简单规整。3 3、脉动阵列中所有、脉动阵列中所有PEPE能同时运算，具有极高的计能同时运算，具有极高的计算并行性，可通过流水获得很高的运算效率和吞算并行性，可通过流水获得很高的运算效率和吞吐率。吐率。4 4、脉动阵列结构的构形与特定计算任务和算法密、脉动阵列结构的构形与特定计算任务和算法密切相关，具有某种专用性，限制了应用的范围。切相关，具有某种专用性，限制了应用的范围。这对这对VLSIVLSI是不利的。是不利的。8.1.2 8.1.2 通用的脉动阵列结构通用的脉动阵列结构 造成脉动阵列机应用范围有限的关键因素造成脉动阵列机应用范围有限的关键因素是，受

6、阵列结构的通用性和是，受阵列结构的通用性和i/oi/o带宽约束所限制带宽约束所限制的阵列结构规模大小。的阵列结构规模大小。发展通用脉动阵列结构的途径主要有三种：发展通用脉动阵列结构的途径主要有三种：1 1、通过增设附加的硬件，对阵列的拓扑结构和互、通过增设附加的硬件，对阵列的拓扑结构和互连方式用可编程开关进行重构，即经程序重新配连方式用可编程开关进行重构，即经程序重新配置阵列的结构。置阵列的结构。2 2、用软件把不同的算法映象到固定的阵列结构上。、用软件把不同的算法映象到固定的阵列结构上。3 3、探寻与问题大小无关的脉动阵列处理方法，以、探寻与问题大小无关的脉动阵列处理方法，以及及VLSIVL

7、SI运算系统的分割矩阵算法，使它们可以克运算系统的分割矩阵算法，使它们可以克服阵列只能求解固定大小题目的缺陷，同时探寻服阵列只能求解固定大小题目的缺陷，同时探寻发展适合一类计算问题的通用算法和相应的设置发展适合一类计算问题的通用算法和相应的设置方案。方案。8.2 8.2 大规模并行处理机大规模并行处理机MPPMPP与机群系统与机群系统8.2.1 8.2.1 大规模并行处理机大规模并行处理机MPPMPP 由于由于VLSIVLSI和微处理器技术的发展，以及高科和微处理器技术的发展，以及高科技应用领域对计算机和通讯网络在计算、处理和技应用领域对计算机和通讯网络在计算、处理和通信性能上不断提出更高的要

8、求，使发展大规模通信性能上不断提出更高的要求，使发展大规模的并行处理成了的并行处理成了2020世纪世纪8080年代中期计算机发展的年代中期计算机发展的热点。热点。 大规模并行处理机大规模并行处理机MPPMPP是由数百至数万个高是由数百至数万个高性能、低成本的性能、低成本的RISCRISC微处理器用互连网络互连而微处理器用互连网络互连而成。成。 这种处理机可进行中粒度和细粒度大规模并这种处理机可进行中粒度和细粒度大规模并行处理，构成行处理，构成SIMD或或MIMD系统。它具有性能系统。它具有性能价格比高和可扩展性好的优点。价格比高和可扩展性好的优点。 典型的大规模并行处理机典型的大规模并行处理机

9、MPP ：参阅教材参阅教材209页页相关内容。相关内容。 MPP的系统软件要求能让用户像使用单处理的系统软件要求能让用户像使用单处理机那样来使用机那样来使用MPP，性能却要数倍于单处理机，性能却要数倍于单处理机的，为此，操作系统采用微内核和大外壳。内核的，为此，操作系统采用微内核和大外壳。内核只提供中断处理、进程调度、进程间简单通讯及只提供中断处理、进程调度、进程间简单通讯及其它最基本的功能，将大量的服务功能搬移到内其它最基本的功能，将大量的服务功能搬移到内核之外。核之外。8.2.2 8.2.2 机群系统机群系统 机群系统是将多个高性能的工作站或高档机群系统是将多个高性能的工作站或高档微型计算

10、机，使用高速的通信网络加以互连组微型计算机，使用高速的通信网络加以互连组成的系统。成的系统。 在并行程序设计和集成开发环境的支持下，在并行程序设计和集成开发环境的支持下，进行统一调度和协调处理，以实现对中、粗细进行统一调度和协调处理，以实现对中、粗细粒度并行进程的高效并行处理。粒度并行进程的高效并行处理。 机群系统中的主机和网络可以是同构的，机群系统中的主机和网络可以是同构的，也可以是异构的。主机间的通讯主要采用消息也可以是异构的。主机间的通讯主要采用消息传递。从结构和结点间的通讯来看，是一种分传递。从结构和结点间的通讯来看，是一种分布式存储方式，而从用户来看，表现出是一个布式存储方式，而从用

11、户来看，表现出是一个完整的并行系统。完整的并行系统。 机群系统比起传统的并行处理系统有机群系统比起传统的并行处理系统有如下几个明显的优点：如下几个明显的优点：1 1、系统有高的性能价格比。、系统有高的性能价格比。2 2、系统的开发周期短。、系统的开发周期短。3 3、系统的可扩展性好。、系统的可扩展性好。4 4、系统的资源利用率高。、系统的资源利用率高。5 5、用户投资风险小。、用户投资风险小。6 6、用户编程方便。、用户编程方便。 基于机群系统的上述优点，使之已成为当基于机群系统的上述优点，使之已成为当前并行处理系统研究的热点。前并行处理系统研究的热点。8.3 8.3 数据流机数据流机8.3.

12、1 8.3.1 数据驱动的概念数据驱动的概念 Von NeumannVon Neumann型计算机的基本特点是在程序计数器型计算机的基本特点是在程序计数器集中控制下，顺次地执行指令。因此，是以控制流方式集中控制下，顺次地执行指令。因此，是以控制流方式工作的。工作的。其本质仍是指令在程序计数器控制下顺序执行，其本质仍是指令在程序计数器控制下顺序执行，这就很难最大限度地发掘出计算的并行性。这就很难最大限度地发掘出计算的并行性。 开发并行性的另一种途径是改用数据驱动的数据流开发并行性的另一种途径是改用数据驱动的数据流方式来工作。方式来工作。 数据驱动的数据流方式指的是，只要一条或一组指数据驱动的数据

13、流方式指的是，只要一条或一组指令所要求的操作数全部就绪，就可立即激发相应的指令令所要求的操作数全部就绪，就可立即激发相应的指令或指令组执行。执行结果的输出将送往等待这一数据的或指令组执行。执行结果的输出将送往等待这一数据的下一条或下一组指令。下一条或下一组指令。 在这种机器上不需要程序计数器，指令的执在这种机器上不需要程序计数器，指令的执行基本上是无序的，完全受数据流的驱动，与指行基本上是无序的，完全受数据流的驱动，与指令在程序中出现的先后顺序无关。令在程序中出现的先后顺序无关。只要数据不相只要数据不相关和资源可以利用，就可以并行，因而最有利于关和资源可以利用，就可以并行，因而最有利于计算并行

14、性的开发。计算并行性的开发。 控制驱动的控制流方式的特点：控制驱动的控制流方式的特点：通过访问共通过访问共享存储单元让数据在指令之间传递；指令执行的享存储单元让数据在指令之间传递；指令执行的顺序性隐含于控制流中，可以显式使用专门的控顺序性隐含于控制流中，可以显式使用专门的控制操作符来实现并行处理；指令执行顺序受程序制操作符来实现并行处理；指令执行顺序受程序计数器控制，即受控制令牌支配。计数器控制，即受控制令牌支配。 数据驱动的数据流方式的特点：数据驱动的数据流方式的特点：没有通常的没有通常的 共共享变量的概念，即没有共享存储数据的概念。享变量的概念，即没有共享存储数据的概念。指令执行顺序只受指

15、令中数据相关性的制约，数指令执行顺序只受指令中数据相关性的制约，数据是以数据令牌方式直接在指令之间传递的。据是以数据令牌方式直接在指令之间传递的。1、数据令牌的概念、数据令牌的概念 实质上是一种表示某一操作数或参数已准实质上是一种表示某一操作数或参数已准备就绪的标志。备就绪的标志。一旦执行某一操作的所有操作一旦执行某一操作的所有操作数令牌都到齐，则标志着这一才操作是什么操数令牌都到齐，则标志着这一才操作是什么操作，以及操作结果所得出的数据令牌应发送到作，以及操作结果所得出的数据令牌应发送到哪些等待此数据令牌的操作的第几个操作数部哪些等待此数据令牌的操作的第几个操作数部位等相关信息，都将作为一个

16、消息包，传送到位等相关信息，都将作为一个消息包，传送到处理单元或操作不见并予执行。处理单元或操作不见并予执行。 2、数据流计算模型、数据流计算模型（1）数据驱动计算数据驱动计算：其操作是按输入数据可用：其操作是按输入数据可用性决定的次序进行。只要所要求的输入数据全性决定的次序进行。只要所要求的输入数据全部就绪，即可驱动操作执行，是一种提前求值部就绪，即可驱动操作执行，是一种提前求值策略。策略。（2）需求驱动计算需求驱动计算：其操作按数据需求所决定：其操作按数据需求所决定的次序进行。按需求值，只有当某一函数需要的次序进行。按需求值，只有当某一函数需要用到某一自变量时，才驱动对该变量的求值操用到某

17、一自变量时，才驱动对该变量的求值操作，是一种滞后求值策略。该模型可以减少许作，是一种滞后求值策略。该模型可以减少许多不必要的值，辅助开销少，有助于提高系统多不必要的值，辅助开销少，有助于提高系统的效率。的效率。 本节所讨论的数据流机一般是指数据驱本节所讨论的数据流机一般是指数据驱动计算，需求驱动更适合于面向函数程序设动计算，需求驱动更适合于面向函数程序设计的计算机。计的计算机。 从语义上讲，数据流是基于异步性和函数从语义上讲，数据流是基于异步性和函数性的一种计算模型。性的一种计算模型。所谓异步性所谓异步性，是指一旦是指一旦操作数到齐就开始操作，这是数据流计算机操作数到齐就开始操作，这是数据流计

18、算机开拓并行性的基础。开拓并行性的基础。所谓函数性所谓函数性，是指每一，是指每一数据流操作都是消耗一组输入值，产生一组数据流操作都是消耗一组输入值，产生一组输出值而不发生副作用，具有变量出现在赋输出值而不发生副作用，具有变量出现在赋值语句左边仅一次的单赋值特性，从而保证值语句左边仅一次的单赋值特性，从而保证任何两个并发操作可以按任意次序执行，而任何两个并发操作可以按任意次序执行，而不会发生干扰。不会发生干扰。8.3.2 8.3.2 数据流程序图和语言数据流程序图和语言 数据流程序图可以看成是数据流机器的机数据流程序图可以看成是数据流机器的机器语言。数据流程序图是用结点和有向弧组器语言。数据流程

19、序图是用结点和有向弧组成的有向图。成的有向图。 它有多个结点，并用一些弧把它们连接而它有多个结点，并用一些弧把它们连接而成。每一个结点用圆圈或三角形或其它特殊成。每一个结点用圆圈或三角形或其它特殊符号表示，认为是一种处理部件，结点内的符号表示，认为是一种处理部件，结点内的符号或字母表示一种操作，所以也称操作符。符号或字母表示一种操作，所以也称操作符。弧代表数据令牌在结点间的流向。弧代表数据令牌在结点间的流向。 在数据流机中，根据这样的数据流程序图，在数据流机中，根据这样的数据流程序图，通过一个分配器或分配程序，不断分配适当通过一个分配器或分配程序，不断分配适当的处理部件来实现操作符的操作。的处

20、理部件来实现操作符的操作。例：例：教材教材213页图页图8.4和图和图8.5表示了计算表示了计算z=(a+b)*(a-b)的数据流程序图。的数据流程序图。 数据流程序图中程序的执行过程是一种数据数据流程序图中程序的执行过程是一种数据不断进行激发的过程。一个操作符的执行从每不断进行激发的过程。一个操作符的执行从每个输入端只吸收一个令牌，进行计算后，只在个输入端只吸收一个令牌，进行计算后，只在有效的输出端上产生一个输出令牌。这种单赋有效的输出端上产生一个输出令牌。这种单赋值规则使结点在生成和消亡时，可以有序地分值规则使结点在生成和消亡时，可以有序地分配和回收值，而不会产生竞争。配和回收值，而不会产

21、生竞争。1、常用的数据流结点（图见、常用的数据流结点（图见214页图页图8.6和和215 页图页图8.7）（1）常数产生结点：没有输入端，只产生常数。）常数产生结点：没有输入端，只产生常数。（2 2）算逻运算操作结点：激发后输出带相应操）算逻运算操作结点：激发后输出带相应操作结果的令牌。作结果的令牌。（3 3）复制操作结点）复制操作结点（4 4）判定操作结点）判定操作结点（5 5）控制类操作结点：）控制类操作结点：T T门控结点、门控结点、 F F门控结点、门控结点、开关门控结点、归并门控结点。开关门控结点、归并门控结点。2、数据流机器语言的表示方法、数据流机器语言的表示方法（1）数据流程序图

22、）数据流程序图：用结点和有向弧组成的有：用结点和有向弧组成的有 向图。向图。（2）活动模片：）活动模片：数据流程序可以看成是一组活数据流程序可以看成是一组活动模片组成的集合体。每一个活动模片相应于动模片组成的集合体。每一个活动模片相应于 数据流程序图中一个或多个操作结点，且由数据流程序图中一个或多个操作结点，且由4个个域组成，它们是一个操作码域、两个操作数域和域组成，它们是一个操作码域、两个操作数域和一个目的域。一个目的域。（图见（图见216页图页图8.10和图和图8.11） 活动模片就是结点在数据流机器内部具体实活动模片就是结点在数据流机器内部具体实现时的存储器映象。数据流程序图实际上是数据

23、现时的存储器映象。数据流程序图实际上是数据流机的机器语言，优点是直观易懂，但是编程效流机的机器语言，优点是直观易懂，但是编程效率很低，难以为一般用户所接受。所以要研究适率很低，难以为一般用户所接受。所以要研究适合于数据流机使用的高级语言。合于数据流机使用的高级语言。 主要是发展新的、适合于数据流控制机制的主要是发展新的、适合于数据流控制机制的高级语言。高级语言。目前主要有单赋值语言和函数程序设目前主要有单赋值语言和函数程序设计语言。计语言。另外还有逻辑程序设计语言另外还有逻辑程序设计语言PROLOG这样一类的描述式语言，也可以作为数据流机的这样一类的描述式语言，也可以作为数据流机的高级语言。高

24、级语言。单赋值语言是指在程序中，每个变量均只赋值一次，即单赋值语言是指在程序中，每个变量均只赋值一次，即同一变量名在不同赋值语句的左部最多只出现一次。同一变量名在不同赋值语句的左部最多只出现一次。因此，实际上并没有传统计算机中变量的概念，只是因此，实际上并没有传统计算机中变量的概念，只是一种值名。一种值名。例如：例如：一个程序允许出现如下语句序列：一个程序允许出现如下语句序列： C=A+BC=A+B C=C C=C* *D D F=(C-D)/E F=(C-D)/E 则所使用的语言就不是单赋值语言。则所使用的语言就不是单赋值语言。 若这时只允许程序写成：若这时只允许程序写成： C=A+BC=A

25、+B C1=C C1=C* *D D F=(C1-D)/E F=(C1-D)/E 其所用的语言就体现出单赋值的规则和要求了。其所用的语言就体现出单赋值的规则和要求了。单赋值语言的语义清楚，程序中的并行性易于被编译单赋值语言的语义清楚，程序中的并行性易于被编译程序所开发。程序所开发。8.3.3 8.3.3 数据流计算机的结构数据流计算机的结构 根据对数据令牌处理的方式不同，可以把数根据对数据令牌处理的方式不同，可以把数据流计算机的结构分为静态和动态两类。据流计算机的结构分为静态和动态两类。 静态数据流机的数据令牌没加标号。为正静态数据流机的数据令牌没加标号。为正确工作，任意给定时刻当结点操作时，

26、其任何一确工作，任意给定时刻当结点操作时，其任何一条输入弧上只能有一个数据令牌。条输入弧上只能有一个数据令牌。只有当结点的只有当结点的所有输入弧上都有数据令牌时，该结点才被激活所有输入弧上都有数据令牌时，该结点才被激活执行相应的操作。执行相应的操作。静态数据流机不支持递归的并静态数据流机不支持递归的并发激活，只支持一般的循环。发激活，只支持一般的循环。 动态数据流机最主要的特点是让令牌带上动态数据流机最主要的特点是让令牌带上标记，使得在任意给定时刻，数据流程序图任何标记，使得在任意给定时刻，数据流程序图任何一条弧上允许出现多个带不同标记的令牌。一条弧上允许出现多个带不同标记的令牌。令牌令牌的标

27、记是令牌附带的一个能识别该令牌时间先后的标记是令牌附带的一个能识别该令牌时间先后 相对关系的标号，有的机器上也称其为颜色。相对关系的标号，有的机器上也称其为颜色。动态数动态数据流机都让数据令牌带有标记，据流机都让数据令牌带有标记，通过对令牌标记的通过对令牌标记的配对来支持递归的并发激活。配对来支持递归的并发激活。8.3.4 8.3.4 数据流机器存在的问题数据流机器存在的问题 数据流计算机在提高并行处理效能上有着非常显著数据流计算机在提高并行处理效能上有着非常显著的长处，但也存在一定问题。的长处，但也存在一定问题。1 1、数据流机主要目的是为了提高操作级并行的开发水、数据流机主要目的是为了提高

28、操作级并行的开发水平，但如果题目本身数据相关性很强，内涵并行成平，但如果题目本身数据相关性很强，内涵并行成分并不多时，就会是效率比传统的分并不多时，就会是效率比传统的Von NeumannVon Neumann型机型机还要低。还要低。2 2、在数据流机中为给数据建立、识别、处理标记，需、在数据流机中为给数据建立、识别、处理标记，需要花费较多的辅助开销和较大的存储空间。但如果要花费较多的辅助开销和较大的存储空间。但如果不使用标记则无法递归并会降低并行能力。不使用标记则无法递归并会降低并行能力。3 3、数据流机不保存数组。数据流机对标量运算、数据流机不保存数组。数据流机对标量运算有利，对数组、递归

29、及其它高级操作较难管理。有利，对数组、递归及其它高级操作较难管理。4 4、数据流语言的变量代表数值而不是存储单元、数据流语言的变量代表数值而不是存储单元的位置，使程序员无法控制存储分配。的位置，使程序员无法控制存储分配。5 5、数据流机互连网络设计困难，输入、数据流机互连网络设计困难，输入/ /输出系统输出系统仍不够完善。仍不够完善。6 6、数据流机没有程序计数器，给诊断和维护带、数据流机没有程序计数器，给诊断和维护带来困难。来困难。 因此，目前数据流机尚难批量生产，仍需因此，目前数据流机尚难批量生产，仍需进一步改进。进一步改进。8.4 8.4 归归 约约 机机 归约机和数据流机一样，都是基于

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

31、达式到目标的函数集合集合3部分组成。部分组成。 函数是其基本成分，是从一批目标到另一批函数是其基本成分，是从一批目标到另一批目标的映射。目标的映射。 函数式程序本质上是属于解释执行方式，函数式程序本质上是属于解释执行方式，从函数式程序的归约来看，机器内部通常采用从函数式程序的归约来看，机器内部通常采用链表的存储结构，且依赖于动态存储分配，存链表的存储结构，且依赖于动态存储分配，存储空间的大小无法预测，需要频繁地进行空白储空间的大小无法预测，需要频繁地进行空白单元的回收，使空间、时间开销都较大，频繁单元的回收，使空间、时间开销都较大，频繁的函数应用和参数传递，加上自变量动态取值，的函数应用和参数

32、传递，加上自变量动态取值，同样的计算往往要重复多次。所以，必须针对同样的计算往往要重复多次。所以，必须针对函数程序设计语言的特点和问题来设计支持函函数程序设计语言的特点和问题来设计支持函数式程序运行的计算机，这就是数式程序运行的计算机，这就是归约机归约机。（1 1）归约机的一般特点）归约机的一般特点1 1、归约机应当是面向函数式语言，或以函数式归约机应当是面向函数式语言，或以函数式语言为机器语言的非语言为机器语言的非NeumannNeumann型机器。型机器。其内部其内部结构应不同于结构应不同于NeumannNeumann型机器。型机器。2 2、具有大容量物理存储器并采用大虚存容量的具有大容量

33、物理存储器并采用大虚存容量的虚拟存储器，虚拟存储器，具备高效的动态存储分配和管理具备高效的动态存储分配和管理的软硬件支持，满足归约机对动态存储分配及的软硬件支持，满足归约机对动态存储分配及所需存储空间大的要求。所需存储空间大的要求。3 3、处理部分应当是一种有多个处理器或多个处、处理部分应当是一种有多个处理器或多个处理机并行的结构形式，以发挥函数式程序并行理机并行的结构形式，以发挥函数式程序并行处理的特长。处理的特长。有多个处理机可高度并行。有多个处理机可高度并行。4 4、采用适合于函数式程序运行的多处理机互连的结构，、采用适合于函数式程序运行的多处理机互连的结构，最好采用树型方式的互连结构或

34、多层次复合的互连最好采用树型方式的互连结构或多层次复合的互连结构形式。结构形式。5 5、为减少进程调度及进程间通讯开销，尽量把运行进、为减少进程调度及进程间通讯开销，尽量把运行进程的结点机安排成紧靠该进程所需用的数据，并使程的结点机安排成紧靠该进程所需用的数据，并使运行时需相互通讯的进程所占用的处理机也靠近，运行时需相互通讯的进程所占用的处理机也靠近，并使各处理机的负荷平衡。并使各处理机的负荷平衡。（2 2）归约机的分类）归约机的分类 根据机器所用归约方式的不同，分为根据机器所用归约方式的不同，分为串归约机串归约机和和图归约机图归约机两类。两类。 串归约机可看成是一种特殊的符号串处理机，函串归

35、约机可看成是一种特殊的符号串处理机，函数定义、表达式和目标都以字符串的形式存储于机数定义、表达式和目标都以字符串的形式存储于机器中。函数式语言源程序可以不经翻译，直接在串器中。函数式语言源程序可以不经翻译，直接在串归约机上进行处理。归约机上进行处理。 串归约机存在的主要问题是不能共享子表达式，多次串归约机存在的主要问题是不能共享子表达式，多次应用就得多次复制和求值运算，所以时间和空间的辅应用就得多次复制和求值运算，所以时间和空间的辅助开销相对都比较大。助开销相对都比较大。 图归约机采取将函数定义、表达式和目标以图图归约机采取将函数定义、表达式和目标以图的形式存储于机器中，图是其处理对象。的形式

36、存储于机器中，图是其处理对象。最常用的图最常用的图是二叉数和是二叉数和N 叉数。采用给每个结点设置指针的方式叉数。采用给每个结点设置指针的方式来存储图。来存储图。 例：例：以表达式以表达式z=(y-1)*(y+x)为例来说明串归约和图为例来说明串归约和图归约的工作原理。（教材归约的工作原理。（教材219页图页图8.12) 总之，总之，归约方式体现了按需求驱动的思想，根据归约方式体现了按需求驱动的思想，根据对函数求值的需求来激活相应指令。对函数求值的需求来激活相应指令。而且，不论是采而且，不论是采用先内后外，或先外后内，或先右后左，还是先左后用先内后外，或先外后内，或先右后左，还是先左后右的顺序

37、归约，也不论是采用串行归约，还是并行归右的顺序归约，也不论是采用串行归约，还是并行归约，都不影响最终结果值。约，都不影响最终结果值。8.5 8.5 智智 能能 机机8.5.1 8.5.1 智能信息处理与智能机智能信息处理与智能机 智能机主要是一个知识信息处理系统，必须解决智能机主要是一个知识信息处理系统，必须解决好有关知识的获取、表示、存储、处理和应用等诸方好有关知识的获取、表示、存储、处理和应用等诸方面的问题，使计算机能更好地模拟人类大脑的思维活面的问题，使计算机能更好地模拟人类大脑的思维活动，提高学习、推理、判断和问题求解的能力。动，提高学习、推理、判断和问题求解的能力。 知识的表现形式可

38、以是自然语言、语音、图形、图知识的表现形式可以是自然语言、语音、图形、图象、文件等，有些很难规范和提取，有些很难在机器象、文件等，有些很难规范和提取，有些很难在机器中表示。不少知识是不完全、不确定和模糊的，有些中表示。不少知识是不完全、不确定和模糊的，有些可能属于直觉、联想、体验等非逻辑范畴。人工智能可能属于直觉、联想、体验等非逻辑范畴。人工智能问题的求解往往是一种非确定性的试探推理过程，往问题的求解往往是一种非确定性的试探推理过程，往往搜索的范围很广，也无确定的算法可循。往搜索的范围很广，也无确定的算法可循。 智能机是具有高智能的计算机，它是一智能机是具有高智能的计算机，它是一个知识信息的处

39、理系统。智能机能不断地学个知识信息的处理系统。智能机能不断地学习、积累、完善知识，利用知识进行推理、习、积累、完善知识，利用知识进行推理、判断和求解问题。判断和求解问题。 智能机是一种结构动态可变，易扩充的智能机是一种结构动态可变，易扩充的开放式系统。智能机应当提供良好的人开放式系统。智能机应当提供良好的人机机界面，带有自然语言、声音、文字、图形、界面，带有自然语言、声音、文字、图形、图象等多种智能接口。图象等多种智能接口。 智能机的智能机的3个重要组成部分是：知识库机、个重要组成部分是：知识库机、推理机和智能接口处理机推理机和智能接口处理机。8.5.2 8.5.2 智能机的结构和机器语言智能

40、机的结构和机器语言 智能机的结构框图如智能机的结构框图如221221页图页图8.138.13所示。所示。 知识库机相当于传统机器的主存、虚拟存储器和知识库机相当于传统机器的主存、虚拟存储器和文件存储器的结合。文件存储器的结合。由于要处理的信息由于要处理的信息90%90%以上都是以上都是非数值型的，其处理主要是代数运算。知识库的基非数值型的，其处理主要是代数运算。知识库的基础是关系数据库和相关代数机的集合。础是关系数据库和相关代数机的集合。 知识库以高效可用形式存放有各种知识、语义和知识库以高效可用形式存放有各种知识、语义和规则，通常又有通用知识库和专用知识库之分。通规则，通常又有通用知识库和专用知识库之分。通用知识库的知识由系统提供，用于存放用户要用到用