1、计算机系统结构计算机系统结构王若成王若成 教研室：教研室：B-40282022年12月16日星期五计算机系统结构2第第1章章 计算机系统结构基本概念计算机系统结构基本概念 第第2章章 数据表示与指令系统数据表示与指令系统 第第3章章 总线、中断与输入输出系统总线、中断与输入输出系统 第第4章章 存储体系存储体系 第第5章章 重叠、流水和向量处理机重叠、流水和向量处理机 第第6章章 阵列处理机阵列处理机 第第7章章 多处理机多处理机 第第8章章 其它计算机结构其它计算机结构 目 录2022年12月16日星期五计算机系统结构38.1 8.1 脉动阵列机脉动阵列机 8.2 8.2 大规模并行处理机与
2、机群系统大规模并行处理机与机群系统 8.3 8.3 数据流机数据流机 8.4 8.4 归约机归约机8.5 8.5 智能机智能机 2022年12月16日星期五计算机系统结构48.1 8.1 脉动阵列处理机脉动阵列处理机 脉动阵列结构是由一组处理单元脉动阵列结构是由一组处理单元PE构成构成的阵列。每个的阵列。每个PE的内部结构相同，一般由一的内部结构相同，一般由一个加法个加法/逻辑运算部件或加法逻辑运算部件或加法/乘法运算部件乘法运算部件再加上若干个锁存器构成，可完成少数基本再加上若干个锁存器构成，可完成少数基本的算术逻辑运算操作。阵列内所有处理单元的算术逻辑运算操作。阵列内所有处理单元的数据锁存
3、器都受同一个时钟控制。运算时的数据锁存器都受同一个时钟控制。运算时数据在阵列结构的各个处理单元间沿各自的数据在阵列结构的各个处理单元间沿各自的方向同步向前推进。称其为脉动阵列结构。方向同步向前推进。称其为脉动阵列结构。2022年12月16日星期五计算机系统结构5 为了执行多种计算，脉动型系统内的输为了执行多种计算，脉动型系统内的输入数据流和结果数据流可以在多个不同方向入数据流和结果数据流可以在多个不同方向上以不同速度向前搏动。上以不同速度向前搏动。阵列内部的各个单元只接收前一组处理阵列内部的各个单元只接收前一组处理单元传来的数据，并向后一组处理单元发送单元传来的数据，并向后一组处理单元发送数据
4、。数据。只有位于阵列边缘的处理单元，才与存储只有位于阵列边缘的处理单元，才与存储器或器或I/OI/O端口进行数据通信。端口进行数据通信。2022年12月16日星期五计算机系统结构6 主要适用于计算量很大的信号主要适用于计算量很大的信号/图像处理，图像处理，以及某些特定计算类算法题目的求解，特别以及某些特定计算类算法题目的求解，特别是需要对大量数据执行重复计算的运算受限是需要对大量数据执行重复计算的运算受限类问题的求解。类问题的求解。2022年12月16日星期五计算机系统结构72022年12月16日星期五计算机系统结构8例如给出了在一个脉动式二维阵列结构上进例如给出了在一个脉动式二维阵列结构上进
5、行两个行两个3 33 3矩阵矩阵A A、B B相乘的例子。每个处理相乘的例子。每个处理单元单元PEPE内含一个乘法器和一个加法器，可完内含一个乘法器和一个加法器，可完成一个内积步运算。每经一拍，处理单元可成一个内积步运算。每经一拍，处理单元可把把3 3个输入端送来的信息沿三个不同方向，即个输入端送来的信息沿三个不同方向，即由左向右的水平方向、由下向上的垂直方向由左向右的水平方向、由下向上的垂直方向和由左下角到右上角的斜和由左下角到右上角的斜4545方向，同时将方向，同时将结果传送到对应的结果传送到对应的3 3个输出端，使个输出端，使aa aa，bb bb，dadab+cb+c。2022年12月
6、16日星期五计算机系统结构92022年12月16日星期五计算机系统结构102022年12月16日星期五计算机系统结构112022年12月16日星期五计算机系统结构12给出了给出了t t1 1、t t2 2、t t3 3时刻送入阵列中的数据时刻送入阵列中的数据情况，到情况，到t t6 6时，从斜时，从斜4545向右上角将同向右上角将同时输出时输出c c1313、c c1212、c c1111、c c2121、c c3131的值的值,t,t7 7时时输出输出c c2323、c c2222、c c3232的值的值,t,t8 8时输出时输出c c3333的值。的值。可以看出，总共只需要可以看出，总共只
7、需要8 8拍就可以完成两拍就可以完成两个个3 33 3的矩阵相乘，比单处理机上循环的矩阵相乘，比单处理机上循环执行所需的执行所需的2727拍，速度提高了两倍多。拍，速度提高了两倍多。2022年12月16日星期五计算机系统结构13 两个两个n nn n矩阵的相乘，用矩阵的相乘，用3n3n2 2-3n+1-3n+1个个PEPE构成的脉动阵列上只需构成的脉动阵列上只需3n-13n-1步运算步运算即可全部完成，运算所需要的时间只是即可全部完成，运算所需要的时间只是以近似以近似3n3n的线性关系增加，比用单处理的线性关系增加，比用单处理机的近似机的近似n n3 3的关系增加要小得多。当的关系增加要小得多
8、。当n n较较大时，采用脉动阵列进行运算的速度提大时，采用脉动阵列进行运算的速度提高尤为显著。高尤为显著。2022年12月16日星期五计算机系统结构14脉动阵列结构具有如下一些特点：脉动阵列结构具有如下一些特点：(1)(1)结构简单、规整，模块化强，可扩充好，非常结构简单、规整，模块化强，可扩充好，非常适合用超大规模集成电路实现。适合用超大规模集成电路实现。(2)PE(2)PE间数据通信距离短、规则，使数据流和控制间数据通信距离短、规则，使数据流和控制流的设计、同步控制等均简单规整。流的设计、同步控制等均简单规整。(3)(3)脉动阵列中所有脉动阵列中所有PEPE能同时运算，具有极高的计能同时运
9、算，具有极高的计算并行性，可通过流水获得很高的运算效率和吞吐算并行性，可通过流水获得很高的运算效率和吞吐率。率。(4)(4)脉动阵列结构的构形与特定计算任务和算法密脉动阵列结构的构形与特定计算任务和算法密切相关，具有某种专用性，限制了应用范围，这对切相关，具有某种专用性，限制了应用范围，这对VLSIVLSI是不利的。是不利的。2022年12月16日星期五计算机系统结构158.1.2 8.1.2 通用脉动阵列结构通用脉动阵列结构 受阵列结构的通用性及受阵列结构的通用性及I/OI/O带宽约束所限带宽约束所限制的阵列结构的规模大小的限制，脉动阵列制的阵列结构的规模大小的限制，脉动阵列机应用范围是有限
10、的。不同的算法往往要求机应用范围是有限的。不同的算法往往要求能有不同的阵列结构，以及大小不同的阵列。能有不同的阵列结构，以及大小不同的阵列。为了克服脉动阵列结构通用性差的弱点，研为了克服脉动阵列结构通用性差的弱点，研究和发展了一些可有效执行多种算法的较为究和发展了一些可有效执行多种算法的较为通用的脉动阵列结构。通用的脉动阵列结构。2022年12月16日星期五计算机系统结构16发展通用脉动阵列结构的途径有三种。发展通用脉动阵列结构的途径有三种。第一种途径是通过增设附加的硬件，第一种途径是通过增设附加的硬件，对阵列的拓扑结构和互连方式用可编程对阵列的拓扑结构和互连方式用可编程开关进行重构，即经程序
11、重新配置阵列开关进行重构，即经程序重新配置阵列的结构。的结构。美国美国PurduePurdue大学的可重构高度并行大学的可重构高度并行计算机计算机CHiPCHiP就是典型的例子。就是典型的例子。2022年12月16日星期五计算机系统结构172022年12月16日星期五计算机系统结构18 第二种途径是用软件把不同的算法映第二种途径是用软件把不同的算法映像到固定的阵列结构上。像到固定的阵列结构上。这一方法依赖于面向并行运算所采用的这一方法依赖于面向并行运算所采用的程序语言、操作系统、编译程序和软件开发程序语言、操作系统、编译程序和软件开发工具的设计。工具的设计。美国卡内基美国卡内基-梅隆大学用于信
12、号、图像和梅隆大学用于信号、图像和计算机视觉处理的计算机视觉处理的WARPWARP机是一台由机是一台由1010个以上个以上处理单元组成的线形脉动阵列机。处理单元组成的线形脉动阵列机。2022年12月16日星期五计算机系统结构19 第三种途径是探寻与问题大小无关第三种途径是探寻与问题大小无关的脉动处理方法，以及的脉动处理方法，以及VLSIVLSI运算系统的运算系统的分割矩阵算法，使它们可以克服阵列只分割矩阵算法，使它们可以克服阵列只能求解固定大小题目的缺陷，同时探寻能求解固定大小题目的缺陷，同时探寻发展适合一类计算问题的通用算法和相发展适合一类计算问题的通用算法和相应的设置方案。应的设置方案。2
13、022年12月16日星期五计算机系统结构208.28.2大规模并行处理机与机群系统大规模并行处理机与机群系统发展背景：发展背景：由于由于VLSIVLSI和微处理技术的发展，以及高科和微处理技术的发展，以及高科技应用领域对计算机和通信网络在计算、处技应用领域对计算机和通信网络在计算、处理和通信性能上不断提出理和通信性能上不断提出更高的要求更高的要求(极大的极大的处理数据量、异常复杂的运算、很不规则的处理数据量、异常复杂的运算、很不规则的数据结构、极高的处理速度数据结构、极高的处理速度),),使发展大规模使发展大规模的并行处理成了的并行处理成了2020世纪世纪8080年代中期计算机发年代中期计算机
14、发展的热点。展的热点。2022年12月16日星期五计算机系统结构21大规模并行处理机：大规模并行处理机：通过新的计算方法、存储技术、处理手通过新的计算方法、存储技术、处理手段和结构组织方式，将数百至数万个高性能、段和结构组织方式，将数百至数万个高性能、低成本的低成本的RISCRISC微处理器用专门的互连网络互微处理器用专门的互连网络互连，组成大规模并行处理机连，组成大规模并行处理机MPPMPP。这种处理机。这种处理机可进行中粒度和细粒度大规模并行处理，构可进行中粒度和细粒度大规模并行处理，构成成SIMDSIMD或或MIMDMIMD系统。系统。2022年12月16日星期五计算机系统结构22优点：
15、它具有性能价格比高和可扩展性好的优点。优点：它具有性能价格比高和可扩展性好的优点。如果一个如果一个RISCRISC微处理器的性能为微处理器的性能为100MFLOPS100MFLOPS，则，则10241024个这样的微处理器组搭成的个这样的微处理器组搭成的MPPMPP系统，其最高系统，其最高性能就可达性能就可达100GFLOPS100GFLOPS。这比用单一主处理机构成。这比用单一主处理机构成的巨型机的性能要高出许多倍，而造价可能只是它的巨型机的性能要高出许多倍，而造价可能只是它的的1/51/5。可扩展性好表现在能比较方便地增减结点。可扩展性好表现在能比较方便地增减结点处理器数，来使系统的规模、
16、处理速度、系统价格处理器数，来使系统的规模、处理速度、系统价格满足应用的需要。采用分布式存储器来减少访存冲满足应用的需要。采用分布式存储器来减少访存冲突。突。2022年12月16日星期五计算机系统结构23MPPMPP的系统软件：操作系统采用微内核和大外壳。的系统软件：操作系统采用微内核和大外壳。内核只提供中断处理、进程调度、进程间简单内核只提供中断处理、进程调度、进程间简单通信及其他最基本的功能，将大量的服务功能搬移通信及其他最基本的功能，将大量的服务功能搬移到内核之外。内核基本功能是同构的，对不同用户到内核之外。内核基本功能是同构的，对不同用户的不同服务需要，允许进行异构服务。的不同服务需要
17、，允许进行异构服务。为适应系统的开放性，采用客户为适应系统的开放性，采用客户/服务器模式。服务器模式。在进程通信上，由内核提供基本的通信，由服务层在进程通信上，由内核提供基本的通信，由服务层提供网络的通信。负荷平衡调度可有分配型、调整提供网络的通信。负荷平衡调度可有分配型、调整型和复合型等多种。型和复合型等多种。2022年12月16日星期五计算机系统结构248.2.2 8.2.2 机群系统机群系统 将多个高性能的工作站或高档微型计算机，使将多个高性能的工作站或高档微型计算机，使用高速的通信网络加以互连组成的系统。在并行程用高速的通信网络加以互连组成的系统。在并行程序设计和集成开发环境的支持下，
18、进行统一调度和序设计和集成开发环境的支持下，进行统一调度和协调处理，以实现对中、粗粒度并行进程的高效并协调处理，以实现对中、粗粒度并行进程的高效并行处理。行处理。机群系统中的主机和网络可以是同构的，也可机群系统中的主机和网络可以是同构的，也可以是异构的。主机间的通信主要采用消息传递。从以是异构的。主机间的通信主要采用消息传递。从结构和结点间的通信来看，是一种分布式存储方式，结构和结点间的通信来看，是一种分布式存储方式，而从用户来看，表示出的是一个完整的并行系统。而从用户来看，表示出的是一个完整的并行系统。2022年12月16日星期五计算机系统结构25机群系统比起传统的并行处理系统有几个明机群系
19、统比起传统的并行处理系统有几个明显优点。显优点。(1)(1)系统有高的性能价格比。系统有高的性能价格比。(2)(2)系统的开发周期短。系统的开发周期短。(3)(3)系统的可扩展性好。系统的可扩展性好。(4)(4)系统的资源利用率高。系统的资源利用率高。(5)(5)用户投资风险小。用户投资风险小。(6)(6)用户编程方便。用户编程方便。2022年12月16日星期五计算机系统结构268.3 8.3 数据流计算机数据流计算机8.3.18.3.1数据驱动的概念数据驱动的概念计数器控制驱动的控制流方式：计数器控制驱动的控制流方式：VonNeumann VonNeumann型计算机的基本特型计算机的基本特
20、点是在程序计数器集中控制下，顺次点是在程序计数器集中控制下，顺次地执行指令，因此，它是以控制流方地执行指令，因此，它是以控制流方式工作的。式工作的。2022年12月16日星期五计算机系统结构27特点：通过访问共享存储单元让数据在指令特点：通过访问共享存储单元让数据在指令之间传递；指令执行的顺序性隐含于控制流之间传递；指令执行的顺序性隐含于控制流中，但却可以显示使用专门的控制操作符来中，但却可以显示使用专门的控制操作符来实现并行处理；指令执行的顺序受程序计数实现并行处理；指令执行的顺序受程序计数器控制，即是受控制令牌所支配。器控制，即是受控制令牌所支配。2022年12月16日星期五计算机系统结构
21、28数据驱动的数据流方式：数据驱动的数据流方式：指的是只要一条或一组指令所要求的操作数全指的是只要一条或一组指令所要求的操作数全部准备就绪，就可立即激发相应的指令或指令组部准备就绪，就可立即激发相应的指令或指令组执行。执行结果的输出将送往等待这一数据的下执行。执行结果的输出将送往等待这一数据的下一条或下一组指令。如果其中一些指令因此而使一条或下一组指令。如果其中一些指令因此而使所需用到的数据全部准备就绪，就可被激发执行。所需用到的数据全部准备就绪，就可被激发执行。在这种机器上不需要程序计数器，指令的执行基在这种机器上不需要程序计数器，指令的执行基本上是无序的，完全受数据流的驱动，与指令在本上是
22、无序的，完全受数据流的驱动，与指令在程序中出现的先后顺序无关。程序中出现的先后顺序无关。2022年12月16日星期五计算机系统结构29特点：数据驱动的数据流方式没有通常的特点：数据驱动的数据流方式没有通常的共享变量的概念，即没有共享存储数据的共享变量的概念，即没有共享存储数据的概念；指令执行顺序只受指令中数据相关概念；指令执行顺序只受指令中数据相关性的制约；数据是以数据令牌方式直接在性的制约；数据是以数据令牌方式直接在指令之间传递的。指令之间传递的。2022年12月16日星期五计算机系统结构30数据令牌：实质上是一种表示某一操作数或数据令牌：实质上是一种表示某一操作数或参数已准备就绪的标志。一
23、旦执行某一操作参数已准备就绪的标志。一旦执行某一操作的所有操作数令牌都到齐，则标志着这一操的所有操作数令牌都到齐，则标志着这一操作是什么操作，以及操作结果所得出的数据作是什么操作，以及操作结果所得出的数据令牌应发送到哪些等待此数据令牌的操作的令牌应发送到哪些等待此数据令牌的操作的第几个操作数部件等有关信息，都将作为一第几个操作数部件等有关信息，都将作为一个消息包，传送到处理单元或操作部件并予个消息包，传送到处理单元或操作部件并予以执行。以执行。2022年12月16日星期五计算机系统结构31需求驱动的数据流方式：而需求驱动是按需求值，需求驱动的数据流方式：而需求驱动是按需求值，只有当某一函数需要
24、用到某一自变量时，才驱动对只有当某一函数需要用到某一自变量时，才驱动对该自变量的求值操作，是一种滞后求值的策略。需该自变量的求值操作，是一种滞后求值的策略。需求驱动计算，其操作则按数据需求所决定的次序进求驱动计算，其操作则按数据需求所决定的次序进行。行。数据驱动计算，其操作是按输入数据可用性决数据驱动计算，其操作是按输入数据可用性决定的次序进行；数据驱动计算只要所要求的输入数定的次序进行；数据驱动计算只要所要求的输入数据全部就绪，即可驱动操作执行，是一种提前求值据全部就绪，即可驱动操作执行，是一种提前求值的策略；的策略；2022年12月16日星期五计算机系统结构32 显然后者较之前者可以减少许
25、多不必显然后者较之前者可以减少许多不必要的求值，辅助开销少，有助于提高系统要的求值，辅助开销少，有助于提高系统的效率。作为本节讨论的数据流机来说，的效率。作为本节讨论的数据流机来说，一般是指数据驱动计算，需求驱动更适合一般是指数据驱动计算，需求驱动更适合面向函数程序设计的计算机。面向函数程序设计的计算机。2022年12月16日星期五计算机系统结构338.1.28.1.2数据流程序图和语言数据流程序图和语言 有向图来表示指令级的数据流程序，它可看成有向图来表示指令级的数据流程序，它可看成是数据流机器的机器语言。它有多个结点，并用一是数据流机器的机器语言。它有多个结点，并用一些弧把它们连接而成。每
26、一个结点用圆圈或三角形些弧把它们连接而成。每一个结点用圆圈或三角形或其他特殊符号表示，认为是一种处理部件，结点或其他特殊符号表示，认为是一种处理部件，结点内的符号或字母表示一种操作。弧代表数据令牌在内的符号或字母表示一种操作。弧代表数据令牌在结点间的流向。在数据流机中，根据这样的数据流结点间的流向。在数据流机中，根据这样的数据流程序图，通过一个分配器或分配程序，不断分配适程序图，通过一个分配器或分配程序，不断分配适当的处理部件来实现操作符的操作。当的处理部件来实现操作符的操作。2022年12月16日星期五计算机系统结构34计算计算z z=(=(a a+b b)*(a a-b b)数据流程序图数
27、据流程序图 2022年12月16日星期五计算机系统结构352022年12月16日星期五计算机系统结构362022年12月16日星期五计算机系统结构372022年12月16日星期五计算机系统结构38例如：是具有条件分支结构的数据流程序例如：是具有条件分支结构的数据流程序图的例子，以实现当图的例子，以实现当x x0 0时，让时，让x x加加y y，否，否则，就让则，就让x x减减y y的功能。为具有循环结构的的功能。为具有循环结构的数据流程序图的例子，以实现对数据流程序图的例子，以实现对x x循环累加，循环累加，直到直到x x的值超过的值超过10001000为止，所得结果为为止，所得结果为z z的
28、的功能。功能。2022年12月16日星期五计算机系统结构392022年12月16日星期五计算机系统结构402022年12月16日星期五计算机系统结构41 活动模片表示法活动模片表示法 数据流实际上可以被看成是一组活动数据流实际上可以被看成是一组活动模片组成的集合体。每一个活动模片相应于模片组成的集合体。每一个活动模片相应于数据流程序图中一个或多个操作结点，且由数据流程序图中一个或多个操作结点，且由4 4个域组成。它们是一个操作码域，两个操作个域组成。它们是一个操作码域，两个操作数域和一个目的域。数域和一个目的域。2022年12月16日星期五计算机系统结构42计算计算z=(a+b)z=(a+b)
29、*(a-b)(a-b)活动模片活动模片2022年12月16日星期五计算机系统结构432022年12月16日星期五计算机系统结构44 活动模片就是结点在数据流机器内部具活动模片就是结点在数据流机器内部具体实现时的存储器映像。所以，活动模片表体实现时的存储器映像。所以，活动模片表示的数据流程序图也可认为就是数据流机的示的数据流程序图也可认为就是数据流机的可执行的机器代码程序，可由数据流机硬件可执行的机器代码程序，可由数据流机硬件直接解释执行。直接解释执行。优点直观易懂，但编程效率低，难以为优点直观易懂，但编程效率低，难以为一般用户所接受。一般用户所接受。2022年12月16日星期五计算机系统结构4
30、5 目前数据流控制机的高级语言主要目前数据流控制机的高级语言主要有单赋值语言和函数程序设计语言。另有单赋值语言和函数程序设计语言。另外，逻辑程序设计语言外，逻辑程序设计语言PROLOGPROLOG这样一类这样一类的描述式语言，也可作为数据流机的高的描述式语言，也可作为数据流机的高级语言。级语言。2022年12月16日星期五计算机系统结构468.3.38.3.3数据流计算机的结构数据流计算机的结构 根据对数据令牌处理的方式不同，可以把数根据对数据令牌处理的方式不同，可以把数据流计算机的结构分成静态和动态两类。据流计算机的结构分成静态和动态两类。静态数据流机：静态数据流机的数据令静态数据流机：静态
31、数据流机的数据令牌没加标号。为正确工作，任意给定时刻，牌没加标号。为正确工作，任意给定时刻，当结点操作时，其任何一条输入弧上只能有当结点操作时，其任何一条输入弧上只能有一个数据令牌。只有当结点的所有输入弧上一个数据令牌。只有当结点的所有输入弧上都有数据令牌时，该结点才被激活执行相应都有数据令牌时，该结点才被激活执行相应的操作。的操作。2022年12月16日星期五计算机系统结构47由于数据令牌没有加标号，如果给定时间里允许一由于数据令牌没有加标号，如果给定时间里允许一条弧上同时出现两个以上的数据令牌的话，结点对条弧上同时出现两个以上的数据令牌的话，结点对于送达各输入端的一批数据就无法区分出它们中
32、哪于送达各输入端的一批数据就无法区分出它们中哪些是属于同一批的操作数。因此，为了满足迭代要些是属于同一批的操作数。因此，为了满足迭代要求，除要多次重复激活同一操作结点外，还必须另求，除要多次重复激活同一操作结点外，还必须另设控制令牌，以识别数据令牌由一个结点传送到另设控制令牌，以识别数据令牌由一个结点传送到另一个结点的时间关系，从而区分属于不同迭代层次一个结点的时间关系，从而区分属于不同迭代层次的各批数据。所以，静态数据流机不支持递归的并的各批数据。所以，静态数据流机不支持递归的并发激活，只支持一般的循环。发激活，只支持一般的循环。2022年12月16日星期五计算机系统结构48 动态数据流机：
33、最主要的特点是让令牌带上动态数据流机：最主要的特点是让令牌带上标记，使得在任意给定时刻，数据流程序图任何一标记，使得在任意给定时刻，数据流程序图任何一条弧上允许出现多个带不同标记的令牌。令牌的标条弧上允许出现多个带不同标记的令牌。令牌的标记是令牌附带的一个能识别该令牌时间先后相对关记是令牌附带的一个能识别该令牌时间先后相对关系的标号。对于需要多组系的标号。对于需要多组(次次)数据令牌的指令，则数据令牌的指令，则是通过对令牌标记的配对来识别。为此，需要相应是通过对令牌标记的配对来识别。为此，需要相应硬件将标记附加到数据令牌上，并完成对标记的匹硬件将标记附加到数据令牌上，并完成对标记的匹配工作。配
34、工作。2022年12月16日星期五计算机系统结构498.3.4 8.3.4 数据流机器存在的问题数据流机器存在的问题 (1)(1)数据流机主要目的是为了提高操作级并行的开数据流机主要目的是为了提高操作级并行的开发水平，但如果题目本身数据相关性很强，内涵并发水平，但如果题目本身数据相关性很强，内涵并行性成分不多时，就会使效率反而比传统的行性成分不多时，就会使效率反而比传统的VonNeumannVonNeumann型机的还要低。型机的还要低。(2)(2)在数据流机器中为给数据建立、识别、处理标在数据流机器中为给数据建立、识别、处理标记，需要花费较多的辅助开销和较大的存储空间。记，需要花费较多的辅助
35、开销和较大的存储空间。(3)(3)数据流机不保存数组。数据流机器对标量运算数据流机不保存数组。数据流机器对标量运算有利，而对数组、递归及其他高级操作较难管理。有利，而对数组、递归及其他高级操作较难管理。2022年12月16日星期五计算机系统结构50(4)(4)数据流语言的变量代表数值而不是存储单数据流语言的变量代表数值而不是存储单元位置，使程序员无法控制存储分配。元位置，使程序员无法控制存储分配。(5)(5)数据流机互连网络设计困难，输入数据流机互连网络设计困难，输入/输出输出系统仍不够完善。系统仍不够完善。(6)(6)数据流机没有程序计数器，给诊断和维护数据流机没有程序计数器，给诊断和维护带
36、来了困难。带来了困难。2022年12月16日星期五计算机系统结构518.4 8.4 归约机归约机 归约机和数据流机，都是基于数据流的归约机和数据流机，都是基于数据流的计算模型，只是其采用的驱动方式不同。数计算模型，只是其采用的驱动方式不同。数据流机是采用数据驱动，执行的操作序列取据流机是采用数据驱动，执行的操作序列取决于输入数据的可用性；归约机则是需求驱决于输入数据的可用性；归约机则是需求驱动，执行的操作序列取决于对数据的需求，动，执行的操作序列取决于对数据的需求，对数据的需求又来源于函数式程序设计语言对数据的需求又来源于函数式程序设计语言对表达式的归约。对表达式的归约。2022年12月16日
37、星期五计算机系统结构52 函数式语言：是由所有函数表达式的集合、函数式语言：是由所有函数表达式的集合、所有目标所有目标(也是表达式也是表达式)的集合及所有由函数的集合及所有由函数表达式到目标的函数集合三部分组成的。表达式到目标的函数集合三部分组成的。函数是其基本成分，是从一批目标到另一函数是其基本成分，是从一批目标到另一批目标的映射。批目标的映射。2022年12月16日星期五计算机系统结构53 从函数程序设计的角度看，一个程序就是一个从函数程序设计的角度看，一个程序就是一个函数的表达式。通过定义一组函数的表达式。通过定义一组“程序形成算符程序形成算符”，可以用简单函数可以用简单函数(即简单程序
38、即简单程序)构成任意复杂的程序，构成任意复杂的程序，也就是构成任意复杂函数的表达式。反过来，如果也就是构成任意复杂函数的表达式。反过来，如果给出了一个属函数表达式集合中的复杂函数的表达给出了一个属函数表达式集合中的复杂函数的表达式，利用提供的函数集合中的子函数经过有限次归式，利用提供的函数集合中的子函数经过有限次归约代换之后，总可以得到所希望的结果，即由常量约代换之后，总可以得到所希望的结果，即由常量构成的目标。函数表达式的每一次归约，就是一次构成的目标。函数表达式的每一次归约，就是一次函数的应用，或是一个子表达式函数的应用，或是一个子表达式(子函数式子函数式)的代换的代换(还原还原)。202
39、2年12月16日星期五计算机系统结构54 例如：表达式例如：表达式z=(y-1)z=(y-1)*(y+x)(y+x)，可以理，可以理解成解成z=f(u),z=f(u),而而f(u)f(u)等价于等价于g(v)g(v)*h(w)h(w)，其，其中中g(v)=y-1,h(w)=y+x,g(v)=y-1,h(w)=y+x,也就是说，函数也就是说，函数z=f(u)z=f(u)的求解可归约成求两个子函数的求解可归约成求两个子函数g(v)g(v)和和h(w)h(w)的积，而的积，而g(v)g(v)和和h(w)h(w)又可以分别继又可以分别继续向下归约。续向下归约。2022年12月16日星期五计算机系统结构
40、55归约机归约机 函数式程序本质上是属于解释执行方式，从函数函数式程序本质上是属于解释执行方式，从函数式程序的归约来看，机器内部通常采用链表的存储式程序的归约来看，机器内部通常采用链表的存储结构，且依赖于动态存储分配，存储空间的大小无结构，且依赖于动态存储分配，存储空间的大小无法预测，需要频繁地进行空白单元的回收，使空间、法预测，需要频繁地进行空白单元的回收，使空间、时间开销都较大，频繁的函数应用和参数传递，加时间开销都较大，频繁的函数应用和参数传递，加上自变量动态取值，同样的计算往往要重复多次。上自变量动态取值，同样的计算往往要重复多次。所以，必须针对函数程序设计语言的特点和问题来所以，必须
41、针对函数程序设计语言的特点和问题来设计支持函数式程序运行的新计算机（归约机）。设计支持函数式程序运行的新计算机（归约机）。2022年12月16日星期五计算机系统结构56 归约机一般有如下一些结构特点：归约机一般有如下一些结构特点：(1)(1)归约机应当是面向函数式语言，或以函数式语归约机应当是面向函数式语言，或以函数式语言为机器语言的非言为机器语言的非NeumannNeumann型机器。型机器。(2)(2)具有大容量物理存储器并采用大虚存容量的虚具有大容量物理存储器并采用大虚存容量的虚拟存储器，具备高效的动态存储分配和管理的软、拟存储器，具备高效的动态存储分配和管理的软、硬件支持，满足归约机对
42、动态存储分配及所需存储硬件支持，满足归约机对动态存储分配及所需存储空间大的要求。空间大的要求。(3)(3)处理部分应当是一种有多个处理器或多个处理处理部分应当是一种有多个处理器或多个处理机并行的结构形式，以发挥函数式程序并行处理特机并行的结构形式，以发挥函数式程序并行处理特长长.2022年12月16日星期五计算机系统结构57(4)(4)采用适合于函数式程序运行的多处理器采用适合于函数式程序运行的多处理器(机机)互连的结构，最好采用树形方式的互连互连的结构，最好采用树形方式的互连结构或多层次复合的互连结构形式。结构或多层次复合的互连结构形式。(5)(5)为减少进程调度及进程间通信开销，尽量为减少
43、进程调度及进程间通信开销，尽量把运行进程的结点机安排成紧靠该进程所需把运行进程的结点机安排成紧靠该进程所需用的数据，并使运行时需相互通信的进程所用的数据，并使运行时需相互通信的进程所占用的处理机也靠近，让各处理机的负荷平占用的处理机也靠近，让各处理机的负荷平衡。衡。2022年12月16日星期五计算机系统结构58根据机器内部对函数表达式所用存储方式的根据机器内部对函数表达式所用存储方式的不同，将归约方式分成串归约和图归约两类。不同，将归约方式分成串归约和图归约两类。以表达式以表达式z=(y-1)z=(y-1)*(y+x)(y+x)为例，假定为例，假定x x和和y y分别分别赋予赋予2 2和和5
44、5。2022年12月16日星期五计算机系统结构59串归约方式串归约方式 当提出求函数当提出求函数z=f(u)的请求后，立即转的请求后，立即转化成执行由操作符化成执行由操作符*和两个子函数和两个子函数g和和h的作的作用所组成的用所组成的“指令指令”。g和和h的作用又引起的作用又引起“指令指令”(-y,1)和和(+y,x)的执行。于是，从的执行。于是，从存储单元中分别取出存储单元中分别取出y和和x的值，算出的值，算出y-1和和y+x的结果，然后将返回值再各自取代的结果，然后将返回值再各自取代g和和h，最后求最后求(*4,7)，得结果，得结果28。2022年12月16日星期五计算机系统结构60 串归
45、约方式是一种不断地在定义表达串归约方式是一种不断地在定义表达式集合中去查找和复制的过程，而且对每式集合中去查找和复制的过程，而且对每次函数作用都要重复执行，因而时间和空次函数作用都要重复执行，因而时间和空间的辅助开销都比较大。间的辅助开销都比较大。2022年12月16日星期五计算机系统结构61图归约方式图归约方式 定义表达式时，设置了定义表达式时，设置了Z/1Z/1、Z/2Z/2等指针。等指针。这样，下一层作用的返回结果直接取代上一这样，下一层作用的返回结果直接取代上一层作用的自变量，省去了归约的复制开销；层作用的自变量，省去了归约的复制开销；同时实现了自变量返回值的共享，不用对同同时实现了自
46、变量返回值的共享，不用对同一函数作用重复执行，就可以直接引用此函一函数作用重复执行，就可以直接引用此函数的求值的结果。数的求值的结果。2022年12月16日星期五计算机系统结构62 总之，归约方式体现了按需求驱动的思想，总之，归约方式体现了按需求驱动的思想，根据对函数求值的需求来激活相应指令。而根据对函数求值的需求来激活相应指令。而且，不论是采用先内后外，或先外后内，或且，不论是采用先内后外，或先外后内，或先右后左，还是先左后右的顺序归约，也不先右后左，还是先左后右的顺序归约，也不论是采用串行归约，还是并行归约，都不影论是采用串行归约，还是并行归约，都不影响最终结果值。响最终结果值。2022年
47、12月16日星期五计算机系统结构632022年12月16日星期五计算机系统结构64根据机器所用归约方式的不同，相应就有根据机器所用归约方式的不同，相应就有串归约机和图归约机两类。串归约机和图归约机两类。串归约机：可看成是一种特殊的符号串处串归约机：可看成是一种特殊的符号串处理机，函数定义、表达式和目标都以字符理机，函数定义、表达式和目标都以字符串的形式存储于机器中。串的形式存储于机器中。优点：函数式语言源程序可以不经翻译，优点：函数式语言源程序可以不经翻译，直接在串归约机上进行处理。直接在串归约机上进行处理。2022年12月16日星期五计算机系统结构65缺点：是不能共享子表达式，多次应用就缺点
48、：是不能共享子表达式，多次应用就得多次复制和求值运算，所以时间和空间得多次复制和求值运算，所以时间和空间的辅助开销相对都比较大。的辅助开销相对都比较大。19791979年，美国的年，美国的MagoMago教授提出的细胞归约教授提出的细胞归约机机FFPFFP就是一种串归约机。就是一种串归约机。2022年12月16日星期五计算机系统结构66图归约机：采取将函数定义、表达式和目标以图的图归约机：采取将函数定义、表达式和目标以图的形式存储于机器中，图是其处理对象。最常用的图形式存储于机器中，图是其处理对象。最常用的图是二叉树和是二叉树和N N叉树。采用给每个结点设置指针的方叉树。采用给每个结点设置指针
49、的方式来存储图。式来存储图。优点：图的处理通过指针进行。实现了子表达式的优点：图的处理通过指针进行。实现了子表达式的共享，免去了复制。而且链表中的各结点可分散存共享，免去了复制。而且链表中的各结点可分散存储于不同空间，不必强调串归约机要求的邻接性。储于不同空间，不必强调串归约机要求的邻接性。结点的插删只需修改指针，利于无用存储单元的回结点的插删只需修改指针，利于无用存储单元的回收，从而图归约机存储空间利用率高。收，从而图归约机存储空间利用率高。2022年12月16日星期五计算机系统结构67缺点：一旦某个结点出错，会使与此结点缺点：一旦某个结点出错，会使与此结点有关的全部信息丢失，所以可靠性不如串有关的全部信息丢失，所以可靠性不如串归约机。归约机。墨西哥国立大学的墨西哥国立大学的GuzmanGuzman等人提出的并行等人提出的并行LISPLISP机，就是图归约机。机，就是图归约机。2022年12月16日星期五计算机系统结构68第第 1 1 章章 结结 束束The End谢谢！谢谢！
