第8章李学干,计算机系统结构南航课件
第 8 章 具有现代特色的计算机 第 8 章 具有现代特色的计算机 8.1 脉动阵列机 8.2 数据流机 8.3 归约机 8.4 智能机 8.5 大规模并行处理机MPP与机群系统 第 8 章 具有现代特色的计算机 8.2 数 据 流 机 8.2.1 数据驱动的概念 以计算一元二次方程ax2bxc0的根作为例子。假定b2- 4ac≥0,可以写出如下的FORTRAN程序 READ *, A, B, C X12*A DSQRTB*B-4*A*C DD/X1 X2-B/X1 X1X2D X2X2-D PRINT *, X1, X2 END 第 8 章 具有现代特色的计算机 图 8.8 求一元二次方程根的程序中的数据相关关系 第 8 章 具有现代特色的计算机 图 8.9 求一元二次方程根的数据流程序图 第 8 章 具有现代特色的计算机 8.2.2 数据流程序图和语言 1. 数据流程序图 图 8.10 计算zab*a-b的数据流程序图 第 8 章 具有现代特色的计算机 图 8.11 数据流程序图的执行过程 第 8 章 具有现代特色的计算机 图 8.12 常用非控制类操作结点及其激发规则 第 8 章 具有现代特色的计算机 图 8.13 常用控制类操作结点及其激发规则 第 8 章 具有现代特色的计算机 图 8.14 具有条件分支结构的数据流程序图例 第 8 章 具有现代特色的计算机 图 8.15 具有循环结构的数据流程序图例 第 8 章 具有现代特色的计算机 图 8.16 计算zab*a-b的活动模片表示法 第 8 章 具有现代特色的计算机 图 8.17 图 8.14 数据流程序图等效的活动模片表示 第 8 章 具有现代特色的计算机 2. 数据流语言 单赋值语言是指在程序中,每个变量均只赋值一次,即 同一变量名在不同赋值语句的左部最多只出现一次。因此, 实际上并没有传统计算机中的变量的概念,只是一种值名。 例如, 一个程序允许出现如下语句序列 CAB CC*D FC-D/E 第 8 章 具有现代特色的计算机 则所使用的语言就不是单赋值语言。 若这时只允许把 程序写成 CAB C1C*D FC1-D/E 其所用的语言就体现出单赋值的规则和要求了。单赋值语言 的语义清楚, 程序中的并行性易于被编译程序所开发。 第 8 章 具有现代特色的计算机 下面以这个语言列举其单赋值语言具备的基本特点。 1 遵循单赋值规则。 2 有丰富的数据类型。 3 具有很强的类型性。 4 具有模块化结构的程序设计思想。 5 没有全局存贮器和状态的概念。 6 程序不规定语句的执行顺序。 第 8 章 具有现代特色的计算机 8.2.3 数据流计算机的结构 1. 静态数据流机 图 8.18 静态数据流机的结构 第 8 章 具有现代特色的计算机 图 8.19 MIT静态数据流机主体结构 第 8 章 具有现代特色的计算机 图 8.20 27→8的仲裁网络示意图 第 8 章 具有现代特色的计算机 2. 动态数据流机 图 8.21 动态数据流机的结构框图 第 8 章 具有现代特色的计算机 图 8.22 MIT动态数据流机结构 第 8 章 具有现代特色的计算机 图 8.23 MIT动态数据流机典型指令的格式 第 8 章 具有现代特色的计算机 图 8.24 MIT动态数据流机每个PE的内部结构 第 8 章 具有现代特色的计算机 图 8.25 Manchester数据流机结构框图 第 8 章 具有现代特色的计算机 8.2.4 数据流机器存在的问题 1 数据流机主要目的是为了提高操作级并行的开发水平 ,但如果题目本身数据相关性很强,内含并行性成分不多时, 就会导致数据流机的效率反而不如传统的Von Neumann型机器 的高。 2 在数据流机器中为了给数据建立标记并识别和处理该 标记,需要花费较多的辅助开销和较大的存贮空间可能比 Neumann型的要大出 2 至 3 倍。 3 数据流机不保存数组。 第 8 章 具有现代特色的计算机 4 数据流语言的变量代表数值而不是存贮单元位置, 使程序员无法控制存贮分配。 为了能有效地回收不用的存贮 单元, 就增大了编译程序设计的难度。 5 专门适合于数据流机用的互连网络的设计较困难, 而且, 对数据流机的输入/输出尚待完善。 6 数据流机没有程序计数器, 给诊断和维护带来困难 。 第 8 章 具有现代特色的计算机 8.3 归 约 机 从函数程序设计的角度看,一个程序就是一个函数的表达 式。通过定义一组“程序形成算符”Program ing Operators, 可以用简单函数即简单程序构成任意复杂的程序 ,也就是, 构成任意复杂函数的表达式。反过来,如果给出了 一个属函数表达式集合中的复杂函数的表达式,利用提供的函 数集合中的子函数经过有限次归约代换之后,总可以得到所希 望的结果, 即由常量构成的目标。函数表达式指的是函数之间 的映射。 从语法上讲是按规定的语法规则构成的符号串,从语 义上讲是多个运算符的组合。 第 8 章 具有现代特色的计算机 函数集合中包括了所有的原函数和复合函数。原函数 Primitive Function指的是,由一个目标变换为另一个目标 的基本映射,是归约机建成时安装上的函数。 它们可以包 括有 从一个元素序列中选出某一个元素的函数, 加、 减 、 乘、 除等算术函数, 交叉置换函数, 比较、 测试函数 , 附加序列函数, 加 1/减 1 函数, 等等。 复合函数指的是 利用一组“程序形成算符”由已有的函数程序构成复杂的函 数程序。 使用的“程序形成算符”一般有组合、 构造、 条 件、 插入、 作用于全体等多种。 第 8 章 具有现代特色的计算机 从归约的角度来理解,函数是一种特殊的表达式, 即为有 局部变量的表达式。例如,经DEF fxxz定义后,使表达式 xz变成了函数,其中x为局部变量,z为全局变量。函数也可以 理解成是定义了一种子表达式的替换规则。例如,已定义了f函 数后,对表达式5*f3求值时,f3就可以用 3z代换,从 5*f3 转换成 5*3z 。 由目标、函数、函数表达式、定义DEF和作用算符就可以 构成函数程序。这里,定义Definition“DEF”就是指的从原有函 数定义一个新的函数。采用的作用算符一般是用冒号,例如 , 函数f作用于目标x,可以表示成f∶x 。 第 8 章 具有现代特色的计算机 以表达式zy-1*yx为例,可以理解成zfu, 而fu等 价于gv* hw, 其中gvy-1; hwyx, 也就是说,函数 zfu的求解可归约成求两个子函数gv和hw的积。gv和 hw又可以分别继续向下归约。 第 8 章 具有现代特色的计算机 有如下主要的优点 1程序的每一行语句可以表达出更多有关算法的信息。 2 没有状态和存贮单元的概念,函数自变量的值随函数 的应用动态获得, 因此不会产生一个过程的变量受到另一过 程影响的副作用,即被应用的函数改变不了函数定义时的约 束关系。 3 没有赋值语句,不会出现像命令式语言里的赋值语句 xx1 那样一种与数学里的变量不相符和违反数学中“相等 性”演绎推理规则的现象;同时,没有使用GO TO类控制语句 。 第 8 章 具有现代特色的计算机 4 指令执行的顺序只受操作数的需求所制约, 只要没有 数据依赖关系的函数,原则上都可以在不同处理器上并行处 理, 所以程序中的并行性较易检测和开发。 5 程序具有单一的递归结构,即函数又是由函数构成。 一个函数程序的功能只与组成该函数程序的各函数成分有关 。数据结构是目标的组成部分,不是程序的组成部分,因此 同一个函数程序可以处理结构、大小不同的目标,增强了程 序的通用性。 第 8 章 具有现代特色的计算机 8.3.2 面向函数程序设计的归约机 1. 归约机的基本结构特点 1 归约机应当面向函数式语言, 或以函数式语言为机器 语言的非Neumann型机器。 2 具有大容量的物理存贮器并采用有虚存容量很大的虚 拟存贮器系统, 具备高效的动态存贮分配和管理的软硬件支 持, 满足归约机对动态存贮分配及所需存贮空间较大的要求 。 3 处理部分应当是一种含有多个处理器或多个处理机并 行的结构形式,以发挥函数式程序并行处理的特长。 第 8 章 具有现代特色的计算机 4 采用适合于函数式程序运行的多处理器机互连的机 构。 尽管过去介绍过的各种机间互连结构原则上都是可用的 ,但最好采用树型方式的互连结构或多层次复合的互连结构 形式。 5 为了减少进程调度及进程间通信的开销,尽可能把运 行进程的结点机安排成紧靠该进程所需用的数据,并使运行 时需相互通信的进程所占用的处理机也靠近。此外还应尽可 能使各个处理机的负荷平衡。 第 8 章 具有现代特色的计算机 根据机器内部对函数表达式所采用的存贮方式不同,将 归约方式又分成了串归约String Reduction和图归约Graph Reduction两类。 为说明这两种归约方式的区别,仍以表达式 zy-1*yx为例。 假定x和y分别赋以 2 和 5。 串归约方式是当提出求函数zfu的请求后,立即转化成 执行由操作符*和两个子函数g与h的作用所组成的“指令”。 g 和h的作用又引起“指令”-y, 1和y, x的执行。于是,从存贮 单元中分别取出y和x的值,算出y-1和yx的结果,然后将返回 值再各自取代g和h,最后求*4, 7,得结果28。 第 8 章 具有现代特色的计算机 图 8.26 串归约和图归约 第 8 章 具有现代特色的计算机 2. 串归约机 串归约机可看成是一种特殊的符号串处理机, 函数定 义、 表达式和目标都以字符串的形式存贮于机器中。 函数 式语言源程序可以不经翻译, 直接在串归约机上进行处理 。 前面已经说过串归约机一个主要问题是不能共享子表达 式, 多次应用就得多次复制和求值运算,所以时间和空间 的辅助开销相对都比较大。 第 8 章 具有现代特色的计算机 图 8.27 表达式在细胞归约机中的存贮形式 第 8 章 具有现代特色的计算机 图 8.28 FFP机的结构 第 8 章 具有现代特色的计算机 图 8.29 FP程序在FFP子树上由a到d的执行过程举例 第 8 章 具有现代特色的计算机 3. 图归约机 图 8.30 Guzman并行LISP机的结构 第 8 章 具有现代特色的计算机 8.4 智 能 机 8.4.1 智能信息处理与智能机 具有智能的计算机主要应当是一个知识信息处理系统。 在这样的系统中,必须解决好有关知识的获取、 知识的表 示、 知识的存贮、知识的处理和知识的应用等诸方面的问 题, 使计算机能更好地模拟人类大脑的思维活动,提高学 习、 推理、 判断和问题求解的能力。 第 8 章 具有现代特色的计算机 8.4.2 智能机的结构及所用的机器语言 1. 智能机的结构 图 8.31 智能机的结构框图 第 8 章 具有现代特色的计算机 2. 逻辑程序设计语言 逻辑程序设计语言的典型代表是PROLOG语言。它是 1972 年法国马赛的A.Colmerauer首先开发的,是以一阶谓词 演算为基础的交互式语言。谓词逻辑Predicate Logic与人类 基于对客观世界的认识所形成的抽象概念进行思考、 推理的 方式十分吻合。PROLOG语言是一种完全面向问题的语言, 尽管它也带有过程性的成分, 但PROLOG程序完全不同于一 般着眼于算法描述的程序。PROLOG程序是关于问题的已知 事实及其关系的说明。其程序的执行大部分依赖于PROLOG 程序中语句所固有的逻辑关系和语言本身按产生式规则进行 演绎推理的能力。从已有事实推导出新的事实。 仅有一部分 依赖于由用户显式给出的控制信息。 第 8 章 具有现代特色的计算机 以X6、Y2, 求ZX1*X-Y的值为例, 若用PROLOG 语言描述,只需要一条产生式规则,即 assignZ, X, Y-P is plusX,1, Q is minusX,Y, Z is timesP, Q. 即可, 其中, “-”表示if, “,”表示逻辑与。 该规则的意思是,如果PX1第一子句与QX-Y第二子句 以及ZP*Q第三子句都满足,则总目标,即产生式左边的规 则头对变量Z、 X、 Y的赋值最终得到满足。 在给定X6、 Y2 时, 求解Z的问题可写成 -assignZ, 6, 2. 第 8 章 具有现代特色的计算机 3. 智能计算机的进展 日本经过 3 年的调查研究和准备,于 1981 年 10 月宣布了 从 1982 年至 1991 年的所谓“第五代计算机”的研究计划, 曾引 起国际上极大的反响。 之后, 美国、 英国以及西欧各国相继 在人工智能和智能机研究上取得不少阶段性成果。 1982年4 月日本正式成立了“新一代计算机技术研究所 ”Institute for New Generation Computer Technology, ICOT, 由多 家大公司、 研究所和大学派人参加。相应成立了核心语言、 自然语言处理、知识库子系统、推理子系统、应用子系统等 5 个研究室。 第 8 章 具有现代特色的计算机 8.5 大规模并行处理机MPP与机群系统 大规模并行处理需要有新的计算方法、新的存贮技术、新 的处理手段和新的结构组织方式。于是,将数百、数千乃至数 万个高性能、低成本的RISC微处理器用互连网络互连,组成大 规模并行处理机MPP就是自然的了。这种处理机可进行中粒度 和细粒度大规模并行处理,构成SIMD或MIMD的系统。它具有 性能价格比高和可扩展性好的优点。如果一个RISC微处理器的 性能为 100 MFLOPS,则 1 024 个这样的微处理器组搭成的 MPP系统,其最高性能就可达 100GFLOPS。这比用单一主处 理机构成的巨型机的性能要高出许多倍,而造价可能只是它的 1/5。 可扩展性好表现在能比较方便地增减节点处理器数,来 使系统的规模、 处理速度、 系统价格满足应用的需要。 第 8 章 具有现代特色的计算机 机群系统是将多个高性能的工作站或高档微型计算机通 过高速的通信网络加以互连而组成的系统。 在并行程序设计 和集成开发环境的支持下, 进行统一调度和协调处理,以对 中、粗粒度的并行进程实现高效并行处理。机群系统中的主 机和网络可以是同构的, 也可以是异构的。主机间的通信主 要采用消息传递。 从结构和结点间的通信来看, 是一种分布 式存贮方式, 而从用户来看, 表现出是一个完整的并行系统 。 第 8 章 具有现代特色的计算机 机群系统比起传统的并行处理系统,有如下几个明显的优点 1 系统有高的性能价格比。 2 系统的开发周期短。 3 系统的可扩展性好。 4 系统的资源利用率高。 5 用户投资风险小。 6 用户编程方便。