第8章-其它计算机分析课件.ppt

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