第9章 非冯 诺依曼计算机.ppt

数学计算机科学学院+2022-7-161计算机体系结构计算机体系结构主讲：陈付龙第第9章章 非冯非冯诺依曼计算机诺依曼计算机 1945年6月，冯诺伊曼与戈德斯坦、勃克斯等人，联名发表了一篇长达101页纸的报告，即计算机史上著名的“101页报告”，是现代计算机科学发展里程碑式的文献。明确规定用二进制替代十进制运算，并将计算机分成五大组件，这一卓越的思想为电子计算机的逻辑结构设计奠定了基础，已成为计算机设计的基本原则。1951年，EDVAC计算机宣告完成。由于他在计算机逻辑结构设计上的伟大贡献，他被誉为“计算机之计算机之父父”。出生1903年12月28日匈牙利布达佩斯逝世1957年2月8日美国华盛顿什么是冯冯诺伊曼计算机诺伊曼计算机？又名：存储程序计算机又名：存储程序计算机 最早是由著名数学家冯诺伊曼等人在1946年总结并明确提出来的。在体系结构上的主要特点：以运算单元为中心 采用存储程序原理 存储器是按地址访问、线性编址的空间 控制流由指令流产生 指令由操作码和地址码组成 数据以二进制编码“程序存储、顺序执程序存储、顺序执行、二进制、五大部行、二进制、五大部件组成、共享件组成、共享数据数据”Von Neumann architecture 冯冯诺伊曼结构，又名普林斯顿结构。诺伊曼结构，又名普林斯顿结构。出自约翰冯诺伊曼的论文：First Draft of a Report on the EDVAC冯诺伊曼瓶颈：访存 约翰巴科斯在1977年ACM图灵奖得奖致词时提出：“确实有一个变更储存装置的方法，比借由冯诺伊曼瓶颈流通大量资料更为先进。瓶颈这词不仅是对于问题本身资料流量的叙述，更重要地，也是个使我们的思考方法局限在一次一字符模式的智能瓶颈。它使我们怯于思考更广泛的概念。因此编程成为一种计划与详述通过冯诺伊曼瓶颈的字符资料流，且大部分的问题不在于资料的特征，而是如何找出资料。”BornDecember 3,1924Philadelphia,PennsylvaniaDiedMarch 17,2007(aged 82)Ashland,OregonFieldsComputer ScienceInstitutionsIBMAlma materColumbia UniversityKnown forSpeedcodingFORTRANALGOLBackus-Naur formFunction-level programmingNotable awardsACM Turing AwardDraper Prize冯诺伊曼瓶颈：访存 将CPU与内存分开并非十全十美，反而会导致所谓的冯诺伊曼瓶颈（von Neumann bottleneck）：在CPU与内存之间的流量（数据传输率）与内存的容量相比起来相当小，在现代电脑中，流量与CPU的工作效率相比之下非常小，在某些情况下（当CPU需要在巨大的数据集上执行一些简单指令时），数据流量就成了整体效率非常严重的限制。CPU将会在数据输入或输出内存时闲置。由于CPU速度远大于内存读写速率，因此瓶颈问题越来越严重。访存瓶颈的解决办法 Cache 分支预测 流水技术Harvard architecture 哈佛结构哈佛结构是一种将程序指令储存和数据储存分开的存储器结构。中央处理器首先到程序指令储存器中读取程序指令内容，解码后得到数据地址，再到相应的数据储存器中读取数据，并进行下一步的操作（通常是执行）。程序指令储存和数据储存分开，数据和指令的储存可以同时进行，可以使指令和数据有不同的数据宽度，如Microchip公司的PIC16芯片的程序指令是14位宽度，而数据是8位宽度。Harvard architecture(Cont.)哈佛结构的微处理器通常具有较高的执行效率。其程序指令和数据指令分开组织和储存的，执行时可以预先读取下一条指令。目前使用哈佛结构的中央处理器和微控制器有很多，除了上面提到的Microchip公司的PIC系列芯片，还有摩托罗拉公司的MC68系列、Zilog公司的Z8系列、ATMEL公司的AVR系列和安谋公司的ARM9、ARM10和ARM11。什么是非冯计算机？什么是非冯计算机？非指令驱动，非指令驱动，从传统的指令驱动型改变为数据驱动型，出现了数据流机计算机。从传统的指令驱动型改变为需求驱动型，出现各种图归约计算机。处理非数值化信息的智能计算机，自然语言、声音、图形和图象处理,虚拟现实处理等第五代计算机，由推理机和知识库机等组成。历经10年，召开过多次专题国际会议。神经网络计算机，仿生计算机，计算模型计算模型 P.C.Treleaven 按计算计算模型可分为控模型可分为控制驱动、数据驱动、需求驱动和模式匹配四制驱动、数据驱动、需求驱动和模式匹配四种类型。种类型。传统的系统结构是基于控制驱动和共享数据的传统的系统结构是基于控制驱动和共享数据的计算模型计算模型 冯冯诺依曼计算机诺依曼计算机 数据流系统结构是基于数据驱动和消息传送的数据流系统结构是基于数据驱动和消息传送的计算模型计算模型 数据流计算机数据流计算机 图归约系统结构是基于需求驱动和共享数据的图归约系统结构是基于需求驱动和共享数据的计算模型计算模型 归约机归约机 串归约系统结构是基于需求驱动和消息传送的串归约系统结构是基于需求驱动和消息传送的计算模型计算模型 归约机归约机控制驱动模型控制驱动模型 这是传统的冯诺依曼型结构 基本特征：命令式语言 程序顺序执行，指令的执行次序受指令计数器的控制，即由程序员指定序列操作 影响并行性主要因素:：控制驱动发展并行控制流模型 如Fork和Join结构，允许在同一时刻有几个控制流同时活动。并行控制流模型关键技术之一是采用同步手段（如Join操作符）来处理数据的相关性。存在问题：用程序计数器（PC）确定程序中指令执行的顺序，程序流由程序员显式控制控制流计算机用共享存储器来保存指令和数据对象，共享存储器中的变量可被多条指令修改。由于存储器是共享的，所以一条指令执行后可能会对其它指令产生副作用。副作用会妨碍并行处理。数据驱动模型数据驱动模型 程序中任意一条指令中所需的操作数（数据令牌）到齐，立即启动执行（称为“点火”）。一条指令的运算结果又流向下一条指令，作为下一条指令的操作数来驱动此指令的启动执行 能充分地利用程序中指令级并行性 不存在共享数据，也不存在指令计数器，指令启动执行的时机仅取决于操作数具备与否。只要有足够多的处理单元，凡是相互间不存在数据相关的指令都可以并行执行 数据驱动模型数据驱动模型需求驱动模型需求驱动模型 一个操作仅在需要用到其输出结果时才开始启动。如果这时该操作由于操作数未到而不能得到输出结果，则该操作再去启动能得到它的各个输入数的操作，也可能那些操作还要去启动另外一些操作，这样就把需求链一直延伸下去，直至遇到常数或外部输入的数据已经到达为止，然后再反方向地去执行运算。需求驱动模型需求驱动模型需求驱动的系统结构特点 需求驱动的系统结构也取消了共享数据和指令计数器，但其执行操作的次序与数据驱动方式不同。由于需求驱动方式只对需要用到其结果的操作进行求值，也即只执行最低限度的求值，免除了许多冗余的计算，从总体而言，它比数据驱动执行的计算量小。归约机就是基于需求驱动的计算机 模式匹配驱动模式匹配驱动 计算的运行是由谓词模式匹配加以驱动的，程序的执行主要适合于求解非数值的符号演算。面向智能的计算机就是基于“模式匹配驱动”的计算机。主要内容9.1 9.1 数据流计算机数据流计算机9.2 9.2 归约机归约机9.3 9.3 智能机智能机9.4 9.4 基于面向对象程序设计语言的计算机基于面向对象程序设计语言的计算机9.5 9.5 神经网络计算机神经网络计算机9.1 9.1 数据流计算机数据流计算机到底是鬼推磨还是磨推鬼？由数据驱动程序的执行；由数据驱动程序的执行；一条指令执行后不送存储器保存，以供其他指一条指令执行后不送存储器保存，以供其他指令共享，而是直接流向需要该结果的指令，作令共享，而是直接流向需要该结果的指令，作为新的操作数供下一条指令使用。为新的操作数供下一条指令使用。l每个操作数经过指令的一次使用后便消失。每个操作数经过指令的一次使用后便消失。l如果若干条指令要求使用相同的数据，那么如果若干条指令要求使用相同的数据，那么就需要事先复制该数据的若干个副本，分别就需要事先复制该数据的若干个副本，分别供多条指令使用。供多条指令使用。9.1.1 基本工作思路基本工作思路数据流驱动的特点数据流驱动的特点1.指令的执行是由数据可用性来驱动，而不是由程序计数器来控制。2.任何指令只要操作数可用，应该说是做好了执行的准备。3.数据驱动程序中的指令不用任何方式来排定次序。4.数据直接保存在指令内，不是存在共享存储器中。5.计算结果（数据令牌）直接在指令间传递。一条指令产生的数据可被复制成多份副本直接送给所有缺乏数据的指令。数据令牌一旦被一条指令使用后，它就不能再被其它指令重复使用。6.不需要共享存储器，不需要程序计数器，不需要控制定序器。7.需要专门的机构来检测数据可用性，将数据令牌和缺乏数据的指令进行匹配，同时使指令执行的异步链结作用得以实现。8.没有存储共享就不会产生副作用。9.异步性意味着需要握手信息或令牌匹配操作。10.纯数据流计算机可开发指令级细粒度并行性。可重入结构、可重入程序可重入结构、可重入程序要求可以被多个任务所调用，需要：程序模块本身在执行过程中不能被修改 调用它的各程序应自带参数工作区数据流计算机指令结构数据流计算机指令结构 指令指令主要由操作包操作包(Operation Packet)和数据令数据令牌牌(Data Token)两部分组成 操作包操作包由操作码(Operation Code)，一个或几个源操作数(Source Data)及后继指令地址(Next Address)等等组成 数据令牌数据令牌通常由结果数值和目标地址等组成。其中的结果值是上条指令的运算结果，而目标地址直接取自上条指令的后继指令地址，如果一条指令的运算结果要送往几个目的地，则分别形成几个数据令牌，多个数据令牌同时在各个操作部件之间传送，允许有多条指令并行执行。数据流机指令格式数据流机指令格式数据流计算机中指令的执行过程数据流计算机中指令的执行过程 函数函数x=(a+b)(a-b)在数据流计算机中的计算过在数据流计算机中的计算过其中符号其中符号()表示数据令牌所携带的操作数表示数据令牌所携带的操作数“.”表示数据令牌表示数据令牌 第一步，数据令牌()=a，()=b；第二步，指令K、K+1被激活并行执行，产生结果数据送下一条指令；第三步，指令K+2被激活，进行乘法运算产生结果X。例例1：数据流计算机和控制流计算机的比较：数据流计算机和控制流计算机的比较任务描述：解方程 ax2+bx+c=0，解的形式为：aacbbx2422,1l串行程序如下（它只能顺序执行）：begin input(a,b,c)a:=2*a;c:=b2-2*a*c;c:=sqrt(c);c:=c/a;b:=-b/a;a:=b+c;b:=b-c;output(a,b);endl并行控制驱动、共享存储模型的FORK-JOIN程序如下，它增加了控制流的复杂性，但还不能从根本上改变它的操作有序性。begin input(a,b,c)a:=2*a;c:=b2-2*a*c;FORK L1,L2;(控制程序并行执行)L1:beginc:=sqrt(c);c:=c/a;goto L3;endL2:beginb:=-b/a;goto L3;endL3:JOIN L1,L2;(等L1,L2完成）FORK L4,L5;(L4,L5并行执行)L4:begina:=b+c;goto L6;endL5:beginb:=b-c;goto L6;endL6:JOIN L4,L5;(等L4,L5完成）output(a,b);endl数据流相关图如下：input(a,b,c)(1)a:=2*a(2)c:=b2-2*a*c(4)c:=sqrt(c)(5)c:=c/a(6)a:=b+c(3)b:=-b/a(7)b:=b-coutput(a,b)l各计算步，只要输入数据到齐就可以计算。比如上图中的（2）与（3），（6）与（7）是可以同时操作的。例例2：数据流计算机和控制流计算机的比较：数据流计算机和控制流计算机的比较 程序描述：input d,e,fc0=0for i from 1 to 8 dobeginai=di eibi=ai fici=bi+ci-1endoutput a,b,cl数据流图：数据流图：+d1 e1a1f1b1c0+d2 e2a2f2b2c1+d3 e3a3f3b3c2+d4 e4a4f4b4c3+d5 e5a5f5b5c4+d6 e6a6f6b6c5+d7 e7a7f7b7c6+d8 e8a8f8b8c7c8其中：加法需要1个时钟周期，乘法需要2个周期，除法需要3个周期。l单处理机用48个周期完成计算：a1b1 c1 a2b2 c2a8b8 c8146 7101213434648l4台处理机的数据流计算机用14个周期完成：a1b1c1a5b2c2a2b8147 810911121314c3c4c5c6c7c8b4 b6b3 b5a3b7a6a4a7a8P1：P2：P3：P4：l共享存储的4台处理机系统用14个周期完成：a1b1c1a5b2a2b8147911121314c3c4c5c7c8b4b6b3b5a3b7a6a4a7a8P1：P2：P3：P4：s1t1c2c6s2t2s1t1s2t2448024344784437013373563436012212342455011131121,ctcctcsstbbsctcctcsbtbbscsccscsstbbscbccbcsbtbbs其中：数据流驱动四个性质：数据流驱动四个性质：1.异步异步(Asynchrony)只要本条指令所需要的数据令牌都到达，指令即可独立地执行，而不必关心其他指令及数据的情况如何。2.并行性并行性(Parallelism)可同时地并行执行多条指令，而且这种并行性通常是隐含的。3.函数性函数性(Functionalism)由于不使用共享的数据存储单元，所以数据流程序不会产生诸如改变存储字这样的副作用。也可以说，数据流运算是纯函数性的。4.局部性局部性(Locality)操作数不是作为“地址”变量，而是作为数据令牌直接传送，因此数据流运算没有产生长远影响的后果，运算效果具有局部性。数据流程序图有两种表示方法：活动片表示法(Activity Templete)；有向图(Directed Graph)法。活动片表示法活动片表示法的基本单元是活动片，每个活动片通常相当于一个或几个操作结点。一个活动片由一个操作码域，一个或几个操作数域，一个或几个后继指令地址域及有关标志等组成(与传统计算机指令系统相似）有向图法有向图法(Directed Graph)，通过特殊有向图描述数据流计算机的工作过程。由有限个结点(Node)集合以及把这些结点连接起来的单向分支线(Unidirectional Branch)组成。通过数据令牌沿有向分支线传送来表示数据在数据流程序图中的流动。用结点表示进行相应的操作，当一个结点的所有输入分支线上当一个结点的所有输入分支线上都出现数据令牌，且输出分支线上没有数据令都出现数据令牌，且输出分支线上没有数据令牌时，该结点的操作即可执行。牌时，该结点的操作即可执行。函数函数x=(a+b)(a-c)的数据流程序图的数据流程序图圆点圆点“.”表示数据令牌，三个算术运算结点，执行加、减、乘操作表示数据令牌，三个算术运算结点，执行加、减、乘操作 算逻运算结点：加()、减()、乘()、除()、与()、或()等。常数产生结点：它没有输入端，只产生常数复制操作结点：数据或控制量的多个复制。数据令牌d经过复制结点激发后，执行复制操作变成多个数据令牌d1，d2，d3控制复制操作类同。基本结点：基本结点：T门控结点：仅当布尔控制端为真、门控结点：仅当布尔控制端为真、且输入端有数据令牌，而输出端没且输入端有数据令牌，而输出端没有数据令牌时才能激发，有数据令牌时才能激发，F门控结点：与门控结点：与T门控结点类似，仅当布尔控制端为假时，才能激发门控结点类似，仅当布尔控制端为假时，才能激发开关门控结点开关门控结点(SW结点结点)：有一个数据输入端和两个数据输出端和一个控：有一个数据输入端和两个数据输出端和一个控制端，根据控制端令牌的真假确定制端，根据控制端令牌的真假确定T输出端或输出端或F输出端上带有输入端的数据输出端上带有输入端的数据令牌令牌合并门控结点合并门控结点(MG结点结点)：有两个数据输入端和一个数据输出端和一个控：有两个数据输入端和一个数据输出端和一个控制端，制端，并受控制端控制。激发后，并受控制端控制。激发后，根据控制端值真假在输出端上产生来根据控制端值真假在输出端上产生来自自T输入端还是输入端还是F输入端上的数据令牌。输入端上的数据令牌。判断操作结点：判断操作结点：当满足条件时（小于、等于、大于当满足条件时（小于、等于、大于0，两个数据的大小比较等）在，两个数据的大小比较等）在输出端产生输出端产生T的控制令牌，的控制令牌，否则便产生否则便产生F的控制令牌的控制令牌 复合类型结点复合类型结点 条件结构数据流图条件结构数据流图IF X=100 THEN (X+Y)/Y ELSE (X-Y)/Y循环结构的数据流程序图循环结构的数据流程序图 例：给定一个自然数x，求它的阶乘x!C语言程序描述语言程序描述计算计算X阶乘的数据流程序图阶乘的数据流程序图 数据流语言数据流语言 对应于数据流程图，最大限度地描述隐含的并行性，能方便地被编译成数据流程序，以便在数据流计算机上执行，并具有易读、易于理解和调试、维护方便 常用的数据流语言有美国的ID和VAL，法国的LAU以及英国曼彻斯特大学的SISAL 语言等1.单赋值规则。单赋值的含义是指在程序中每个变量只能赋值一次，即同一变量在赋值语句的左部只允许出现一次，不允许对同一变量进行多次赋值。遵循单赋值规则。这有利于运算并行性的开发，同时也可防止“副作用”。所谓“副作用”是指在程序执行过程中修改了某些参数的值2.指令的执行次序由数据依赖关系确定，指令执行规则简单地仅受数据相关性约束。3.控制变量的应用范围例：for(i=1;i=n;i+)xi=ai+1;yi=xi+2;zi=yi+3 需要需要3n周期周期x1=a1+1;y1=x1+2;x2=a2=1;for(i=1;i=n-1;i+)zi=yi+3;yi+1=xi+1+2;xi+2=ai+2+1 zn-1=yn-1+3;yn=xn+2;zn=yn+3 需要需要n2周期周期4.支持循环迭代展开 ID语言举例：procedure inner-product(a，b，n)initial s0for I from 1 to n donew ss+(ai*bj)return s 静态数据流计算机静态数据流计算机 基本点：数据令牌不带任何标号，每条有向分支线上在某一个时刻只能传送一个数据令牌，每个结点一次只能执行一个操作。执行规则：结点的每一条输入分支线上都有一个令牌出现（数据分支线上出现的数据令牌，控制分支线上出现携带结点操作所要求控制信号的控制令牌），而且输出分支线上没有令牌时，该结点的操作才能够被执行。具有数据令牌，还有控制令牌，由这两种令牌同时来决定结点的操作是否执行 静态数据流计算机模型静态数据流计算机模型Jack Dennis 1972年提出年提出 更新部件UU指令处理部件PU指令存储部件ISU取指部件RU可执行指令队列IQ（指令地址）指令存储部件ISU中存放要执行的数据流程序收到所需数据令牌的指令由取指令部件收到所需数据令牌的指令由取指令部件RU按更新部件按更新部件UU送来的指令地址逐个取出，送来的指令地址逐个取出，送到可执行指令队列送到可执行指令队列IQ中，此时若有空闲中，此时若有空闲的处理部件，分派程序将等待执行的指令按的处理部件，分派程序将等待执行的指令按次序分配给指令处理部件次序分配给指令处理部件PU，使它们并发，使它们并发执行。执行后的结果形成新的数据令牌执行。执行后的结果形成新的数据令牌数据令牌又被送到更新部件中，再按它们的数据令牌又被送到更新部件中，再按它们的目标地址送往指令存储部件内相应指令的有目标地址送往指令存储部件内相应指令的有关位置，当更新部件将所有已收到所需数据关位置，当更新部件将所有已收到所需数据令牌的指令地址传送给取指令部件，完成了令牌的指令地址传送给取指令部件，完成了一次循环流动一次循环流动 静态数据流计算机实例静态数据流计算机实例1 Dennis静态数据流计算机的结构框图静态数据流计算机的结构框图 用于存放指令。每条指令有一个唯一的地址，也称为指令单元标识符 主要由多个相同或不同的处理单元组成，主要完成数据的函数运算。其主要作用是把操作包从指令存储器传送到处理部件。把控制令牌从处理部件传送到指令存储器。把数据令牌从处理部件传送到指令存储器。静态数据流计算机实例静态数据流计算机实例2Mondala静态数据流机静态数据流机类型操作码8字数目标地址数确认地址数OPR(3)AKR(4)ES(7)操作数目标地址确认地址11个031OPR本指令所需操作数个数（数据令牌）AKR本指令所需收到的控制信号个数（控制令牌）ES计数器，分别对到达数据令牌和控制令牌计数指令格式指令格式两种实现可重入代码的并发调用方法两种实现可重入代码的并发调用方法1.重入代码复制当数据流程序需要调用一段可重入代码时，复制这段代码形成一个副本被调用执行。执行结束后把结果送到输出端保留，以备其它指令应用，副本随即消失。问题：复制过程开销大，程序副本占大量的存储空间。动态数据流计算机动态数据流计算机冯.诺依曼结构可重入代码的递归调用均是一次调用总是在上次调用之后进行。每时刻仅有一个可重入代码的副本在运行，从而保证了多次调用的顺序。数据流机的并行可能并发调用同一个可重入代码，即同一时刻有多个副本在运行，流动着不同次的操作数，流动路径的不同可能导致产生结果的时间不同，引发不同次操作数的混乱。2.带标志数据令牌带标志数据令牌对同一次调用的重入代码中的数据令牌加相同的标志 基本点：每个数据令牌都带有标号（令牌标号及其他特征信息），从而使数据流程图中的一条有向分支线上可同时传送（带不同标号）几个数据令牌 不需要用控制令牌来确认指令间数据令牌的传送。采用一个专门硬件（匹配部件）对数据令牌中的标号进行符合比较并加以识别。动态数据流计算机模型动态数据流计算机模型 匹配部件将各个处理部件送来的结果数据令牌赋予相应的标号，并将流向同一指令的数据令牌进行匹配成对或成组，然后将它们送往更新读出部件，当一条指令所要求的数据令牌都到齐后，就立即从指令存储器中取出这条指令，并把该指令与数据令牌中携带的操作数一起组成一个操作包形成一条可执行指令，送入可执行指令队列。如果指令所要求的数据令牌没有全部到齐（匹配失败），则把刚刚到达的数据令牌暂时存入匹配部件的缓冲存储器中，以供下次匹配时再使用。动态数据流计算机中间结果不返回存储器，减少了操作开销，能更加充分地开发程序中的并行性更新/读出部件URU可执行指令队列IQ指令存储部件ISU指令处理部件PU匹配部件FU数据令牌（配成组的令牌集）动态数据流计算机实例动态数据流计算机实例 Manchester动态数据流计算机结构动态数据流计算机结构处理部件由15个PE组成，可执行定点、浮点、数据转移及打标记等指令。每个PE都有输入缓冲器和输出缓冲器。88开关网络可同时提供多条通路与外部交换信息。令牌队列可存放64K个数据令牌。匹配部件按照令牌的特征值对令牌进行匹配，它内部有16K97位的缓冲存储器。当从令牌队列中送来的数据令牌与匹配部件中已经存在的令牌相匹配（有相应的特征值）时，表示令牌中目标地址字段指示的指令为可执行指令，于是97位数据令牌和36位匹配特征值合在一起组成 133位的令牌组包送往结点存储器。如果从令牌队列送来的数据令牌不能与匹配部件中已经存放的令牌相匹配时，则把新送来的令牌暂时存入匹配部件的缓冲存储器中。结点存储器按照匹配部件送来的令牌组包中给定的目标地址取出指令，并把令牌组包中携带的操作数代入指令中，形成167位的执行包送往处理部件。缓冲存储器有8组组相联存储器组成，采用硬件散列技术来减少相联比较器的位数。Manchester动态数据流计算机的指令与数据令牌格式动态数据流计算机的指令与数据令牌格式 数据流计算机的优点数据流计算机的优点 1.高度并行运算。高度并行运算。不仅能开发程序中有规则的并行性，还能开发程序中任意的并行性。从理论上讲，由于没有指令执行顺序的限制。只要硬件资源充分就能获得最大的并行性。2.流水线异步操作。流水线异步操作。在指令中直接使用数值本身，而不是使用存放数值的地址，从而能实现无副作用的纯函数型程序设计方法，可以在过程级及指令级充分开发异步并行性，可以把实际串行的问题用简单的办法展开成并行问题来计算。例如，把一个循环程序的几个相邻循环体同时展开，把体内、体间本来相关的操作数直接互相替代，形成一条异步流水线，使不同层次的循环体能并行执行。3.与与VLSI技术相适应。技术相适应。数据流计算机结构具有模块性和均匀性。指令存储器、数据令牌缓冲器及可执行指令队列缓冲器等存储部件，可以用VLSI存储阵列均匀地构成。处理部件及信息包开关网络也可以分别用模块化的标准单元有规则地连接而成。有可能研制出具有很高性能价格比的计算机系统。4.有利于提高软件生产能力。有利于提高软件生产能力。在传统语言如Fortran、Pascal等中，由于大量使用全局变量和同义名变量而产生副作用，给软件的生产和调试带来很多困难。而在数据流计算机中，执行的是纯函数操作，使用函数程序设计语言来编程，从含义上取消了“变量”，取消了变量赋值机制。因而消除了巴科斯所说的冯诺依曼赋值操作的瓶颈口。数据流计算机的缺点数据流计算机的缺点(1)操作开销过大 数据流计算机的每条指令都很长。占用较多的存储单元，存取指令过程复杂且费时间。数据流计算机中有大量中间结果形成的数据令牌在系统中流动，使信息的流动相当频繁，增加冲突。为减小冲突，要设置许多局部缓冲器，增加了开销和通信时延。数据流计算机操作开销大的根本原因是把并行性完全放在指令级上。在一个实际的计算机系统中，将高一级的并行性都依赖低级的并行性来实现，往往要付出过高的代价。操作开销大的另一个原因是完全采用异步操作，没有集中控制。为解决这些异步操作和随机调度引起的混乱，需要花费大量的操作开销。数据流计算机指令级的异步操作使得程序调试过程十分困难。(2)不能有效利用传统计算机的研究成果。数据流计算机完全放弃了传统计算机的结构，独树一帜，这样做一方面使它摆脱了传统结构的束缚，具有活跃的生命力。另一方面却使它不能吸取传统计算机已经证明行之有效的许多研究成果。数据流计算机提高了并行性，但并未解决如存储器按模块访问引起的冲突、复杂昂贵的互联网络、多进程之间的同步与通信等 问题。(3)数据流语言尚不完善 目前已经见到的数据流语言，如VAL及ID等都不完善，输入输出操作因为不是函数运算至今未被引到数据流语言中来。数据流语言以隐含的方式描述并行性，由编译器开发这种并行成分，并不十分有效。数据流程序中引入了大量隐含的并行性，使得程序的调试工作变得非常困难。需要解决的几个主要问题需要解决的几个主要问题 合理的划分并行性，减少开销合理的划分并行性，减少开销 研制易于使用，易于由硬件实现的高级研制易于使用，易于由硬件实现的高级数据流语言。数据流语言。设计出性能价格比高的信息包交换网络设计出性能价格比高的信息包交换网络，以支持资源仲裁和令牌分配等大量通，以支持资源仲裁和令牌分配等大量通信工作。信工作。对静态和动态数据流计算机，研制智能对静态和动态数据流计算机，研制智能式数据驱动机构。式数据驱动机构。如何在数据流环境中高效率地处理复杂如何在数据流环境中高效率地处理复杂的数据结构，如数组等。的数据结构，如数组等。研制支持数据流运算的存储层次和存储研制支持数据流运算的存储层次和存储分配方案。分配方案。在广泛的应用领域里，对数据流计算机在广泛的应用领域里，对数据流计算机的硬件和软件作出性能评价，估计各种的硬件和软件作出性能评价，估计各种系统开销，包括开发、运行及应用开销系统开销，包括开发、运行及应用开销。研究数据流计算机的操作系统。研究数据流计算机的操作系统。开发数据流语言的跟踪和调试工具开发数据流语言的跟踪和调试工具 扩展学习 Petri Net 是对离散并行系统的数学表示。Petri网是1960年代由卡尔A佩特里发明的，适合于描述异步的、并发的计算机系统模型。Petri网既有严格的数学表述方式，也有直观的图形表达方式，既有丰富的系统描述手段和系统行为分析技术，又为计算机科学提供坚实的概念基础。9.2 归约机归约机需求驱动需求驱动归约机（Reduction machine）中，计算是由对一个操作结果的需求而起动的。它所开发的都是有用的并行性。惰性计算（Lazy evaluation）：操作只有在另一条指令需要其结果时才执行。无副作用，容易并行化。懒人是怎样炼成的？懒人是怎样炼成的？例子：计算a=(b+1)c-(d e)数据驱动计算时情况：l先算（b+1）和（d e），然后进行 运算，最后进行-运算。运算在其操作数成为可用后立即进行。是一种自底向上的运算，称为积极计算（eager evaluation）。需求驱动情况：l首先计算a值，a值去触发对计算下一级表达式（b+1）c和 d e的需求，此表达式再依次触发计算最里层（b+1）的需求。然后，所有结果在算出a之前以相反次序返回给需求者。是惰性计算（Lazy evaluation）。程序与函数程序与函数 从函数程序设计的角度看，一个程序就是一个函数的表达式。通过定义一组“程序形成算符”(ProgramForming Operators),可以用简单函数(即简单程序)构成任意复杂的程序，也就是，构成任意复杂函数的表达式。反过来，如果给出了一个属函数表达式集合中的复杂函数的表达式，利用提供的函数集合中的子函数经过有限次归约代换之后，总可以得到所希望的结果，即由常量构成的目标。函数表达式指的是函数之间的映射。从语法上讲是按规定的语法规则构成的符号串，从语义上讲是多个运算符的组合。9.2.1 归约原函数和复合函数 函数集合中包括了所有的原函数和复合函数。原函数(Primitive Function)指的是，由一个目标变换为另一个目标的基本映射，是归约机建成时安装上的函数。它们可以包括有：从一个元素序列中选出某一个元素的函数，加、减、乘、除等算术函数，交叉置换函数，比较、测试函数，附加序列函数，加 1/减 1 函数，等等。复合函数指的是利用一组“程序形成算符”由已有的函数(程序)构成复杂的函数(程序)。使用的“程序形成算符”一般有组合、构造、条件、插入、作用于全体等多种。归约与函数 从归约的角度来理解，函数是一种特殊的表达式，即为有局部变量的表达式。例如，经DEF f(x)=x+z定义后，使表达式x+z变成了函数，其中x为局部变量，z为全局变量。函数也可以理解成是定义了一种子表达式的替换规则。例如，已定义了f函数后，对表达式5*f(3)求值时，f(3)就可以用 3+z代换，从 5*f(3)转换成 5*(3+z)。由目标、函数、函数表达式、定义(DEF)和作用算符就可以构成函数程序。这里，定义(Definition)“DEF”就是指的从原有函数定义一个新的函数。采用的作用算符一般是用冒号(：)，例如，函数f作用于目标x，可以表示成fx。以表达式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)又可以分别继续向下归约。有如下主要的优点：(1)程序的每一行语句可以表达出更多有关算法的信息。(2)没有状态和存贮单元的概念，函数自变量的值随函数的应用动态获得，因此不会产生一个过程的变量受到另一过程影响的副作用，即被应用的函数改变不了函数定义时的约束关系。(3)没有赋值语句，不会出现像命令式语言里的赋值语句x=x+1那样一种与数学里的变量不相符和违反数学中“相等性”演绎推理规则的现象；同时，没有使用GO TO类控制语句。(4)指令执行的顺序只受操作数的需求所制约，只要没有数据依赖关系的函数，原则上都可以在不同处理器上并行处理，所以程序中的并行性较易检测和开发。(5)程序具有单一的递归结构，即函数又是由函数构成。一个函数程序的功能只与组成该函数程序的各函数成分有关。数据结构是目标的组成部分，不是程序的组成部分，因此同一个函数程序可以处理结构、大小不同的目标，增强了程序的通用性。9.3.2 面向函数程序设计的归约机面向函数程序设计的归约机 1.归约机的基本结构特点归约机的基本结构特点 (1)归约机应当面向函数式语言，或以函数式语言为机器语言的非Neumann型机器。(2)具有大容量的物理存贮器并采用有虚存容量很大的虚拟存贮器系统，具备高效的动态存贮分配和管理的软硬件支持，满足归约机对动态存贮分配及所需存贮空间较大的要求。(3)处理部分应当是一种含有多个处理器或多个处理机并行的结构形式，以发挥函数式程序并行处理的特长。(4)采用适合于函数式程序运行的多处理器(机)互连的机构。尽管过去介绍过的各种机间互连结构原则上都是可用的，但最好采用树型方式的互连结构或多层次复合的互连结构形式。(5)为了减少进程调度及进程间通信的开销，尽可能把运行进程的结点机安排成紧靠该进程所需用的数据，并使运行时需相互通信的进程所占用的处理机也靠近。此外还应尽可能使各个处理机的负荷平衡。根据机器内部对函数表达式所采用的存贮方式不同，将归约方式又分成了串归约(String Reduction)和图归约(Graph Reduction)两类。在串归约(string reduction)模型中，每个需求者可得到它自己计算用的单独的表达式副本。一个长的串表达式可以用递归方式归约为单值。每个归约步都有一个操作符，后面紧跟一个对所需要的相应输入操作数的引用。操作符在其输入变量正在计算时将被挂起。当全部变量被实在的值替代时，表达式才算是归约完毕。在图归约(graph reduction）模型中，表达式是用有向图表示的。图用计算分支或子图进行归约，根据需要可对图上的各个部分或子图进行并行归约或计算。每个需求者都有一个指向归约结果的指针，需求者对图的全部引用标记进行变换操作。我们采用指针共享变量来实现图的变换，这种图的遍历和颠倒引用一直要继续到遇到常量为止。为说明这两种归约方式的区别，仍以表达式z=(y-1)*(y+x)为例。假定x和y分别赋以 2 和 5。串归约方式是当提出求函数z=f(u)的请求后，立即转化成执行由操作符*和两个子函数g与h的作用所组成的“指令”。g和h的作用又引起“指令”(-y,1)和(+y,x)的执行。于是，从存贮单元中分别取出y和x的值，算出y-1和y+x的结果，然后将返回值再各自取代g和h，最后求(*4,7)，得结果28。串归约和图归约 2.串归约机串归约机 串归约机可看成是一种特殊的符号串处理机，函数定义、表达式和目标都以字符串的形式存贮于机器中。函数式语言源程序可以不经翻译，直接在串归约机上进行处理。前面已经说过串归约机一个主要问题是不能共享子表达式，多次应用就得多次复制和求值运算，所以时间和空间的辅助开销相对都比较大。表达式在细胞归约机中的存贮形式 MAGO细胞归约机的结构 FP程序在FFP子树上由(a)到(d)的执行过程举例 3.图归约机图归约机 图 Guzman并行LISP机的结构 扩展学习 FP函数式编程是种编程典范，它将电脑运算视为函数的计算。函数编程语言最重要的基础是 演算（lambda calculus）。而且演算的函数可以接受函数当作输入（参数）和输出（返回值）。和指令式编程相比，函数式编程强调函数的计算比指令的执行重要。和过程化编程相比，函数式编程里，函数的计算可随时调用。LISP/OCAML总结：实例比较各种驱动模型总结：实例比较各种驱动模型l例子：各驱动模型的比较l任务：计算 a=(b+c)*(b-c)，其中，lb=4,c=2；+b c t1-b c t2*t1 t2 ai1:i2:i3:程序控制流存储器(b)(4)(t1)()(c)(2)(t2)()(a)()控制驱动，共享存储模型FORK i2+b c t1GOTO i3i1:i2:i3:并行控制驱动，共享存储模型JOIN 2-b c t2*t1 t2 a+()2 i3/1i1:i2:i3:数据驱动模型-()()i3/2*()()a/11242数据令牌需求驱动模型b:(4)需求结果c:(2)i1:(+b 2)i2:(-c 2)a:(*i1 i2)控制流、数据流和归约计算机比较机器模型控制流（控制驱动）数据流（数据驱动）归约（需求驱动）基本定义常规计算：令牌控制指明语句何时应执行积极计算：当操作数全部可用时，语句才执行惰性计算：语句只在其结果被另一运算请求时才执行优点全控制并行性潜力很大只执行被请求的指令容易实现复杂数据和控制结构吞吐量大并行度高无副作用容易变换数据结构缺点效率较低时间损失在等待非必需的自变量上不支持局部状态改变的对象共享程序设计困难控制开销大传播需求令牌需要时间难以避免运行时错误难以变换数据结构计算模型按数据机制和控制机制的分类表共享存储专有存储（消息传递）控制驱动Von Neumann通信进程需求驱动图归约串归约数据驱动数据流I-结构数据流令牌 为加深对这些基本的计算模型的理解，下面通过一个简单的计算表达式的例子：a=(b+2)*(b-c)来说明在这些基本模型中是如何进行计算的。控制驱动、共享存储器模型 在这种模型中，操作按事先指定的指令执行序列进行，主要受PC控制。如图所示的该表达式的求值过程。串行控制驱动、共享存储器模型 并行控制驱动、共享存储器模型 这是对一般控制驱动模型的改进。使用FORK语句结构派生出并行任务，使用i1和i2两者并行执行，然后用JOIN语句结构对它们进行同步。图示出了这种模型的计算过程。对存储器中的数据访问与串行控制驱动、共享存储器模型中相同。并行控制驱动、共享存储器模型 数据驱动模型 在这种模型中，操作按数据相关和资源可用性所确定的序列来进行。当一条指令所需的操作数（数据令牌）全部到达，且有可用的计算资源，便可进行计算。如图所示，当数据令牌4和2到达i1和i2后，i1和i2两条指令便可异步并行执行，执行结果将分别传送到指令i3，此后i3便可执行，执行结果送往a。需求驱动模型 在这种模型中，计算的进行是由对该计算结果的需求而被驱动的。如图9.6中所示，当某一指令（iK）中含有函数a并试图执行时，指令iK便被挂起，直到所需要的“a”被满足为止。定义在方框中的“a”以类似的步骤求值。在串归约计算模型中，每个需求者将得到一个“a”定义的拷贝，然后自己求值。在图归约模型中，求值只在第一次需求时进行，由指针可直接获得“a”的值，而不必每次再去求值“a”。需求驱动模型9.3 9.3 智能机智能机、神经计算机、神经计算机9.3.1 智能机智能机智能信息处理与智能机智能信息处理与智能机 具有智能的计算机主要应当是一个知识信息处理系统。在这样的系统中，必须解决好有关知识的获取、知识的表示、知识的存贮、知识的处理和知识的应用等诸方面的问题，使计算机能更好地模拟人类大脑的思维活动，提高学习、推理、判断和问题求解的能力。智能机的结构及所用的机器语言智能机的结构及所用的机器语言 1.智能机的结构智能机的结构 图 8.31 智能机的结构框图 2.逻辑程序设计语言逻辑程序设计语言 逻辑程序设计语言的典型代表是PROLOG语言。它是1972 年法国马赛的A.Colmerauer首先开发的，是以一阶谓词演算为基础的交互式语言。谓词逻辑(Predicate Logic)与人类基于对客观世界的认识所形成的抽象概念进行思考、推理的方式十分吻合。PROLOG语言是一种完全面向问题的语言，尽管它也带有过程性的成分，但PROLOG程序完全不同于一般着眼于算法描述的程序。PROLOG程序是关于问题的已知事实及其关系的说明。其程序的执行大部分依赖于PROLOG程序中语句所固有的逻辑关系和语言本身按产生式规则进行演绎推理的能力。从已有事实推导出新的事实。仅有一部分依赖于由用户显式给出的控制信息。以X=6、Y=2,求Z=(X+1)*(X-Y)的值为例，若用PROLOG语言描述，只需要一条产生式规则，即assign(Z,X,Y):-P is plus(X,1),Q is minus(X,Y),Z is times(P,Q).即可，其中，“:-”表示if,“,”表示逻辑与。该规则的意思是，如果P=X+1(第一子句)与Q=X-Y(第二子句)以及Z=P*Q(第三子句)都满足，则总目标，即产生式左边的规则头(对变量Z、X、Y的赋值)最终得到满足。在给定X=6、Y=2 时，求解Z的问题可写成?-assign(Z,6,2).3.智能计算机的进展智能计算机的进展 日本经过 3 年的调查研究和准备，于 1981 年 10 月宣布了从 1982 年至 1991 年的所谓“第五代计算机”的研究计划，曾引起国际上极大的反响。之后，美国、英国以及西欧各国相继在人工智能和智能机研究上取得不少阶段性成果。1982年4 月日本正式成立了“新一代计算机技术研究所”(Institute for New Generation Computer Technology,ICOT),由多家大公司、研究所和大学派人参加。相应成立了核心语言、自然语言处理、知识库子系统、推理子系统、应用子系统等 5 个研究室。9.3.2 9.3.2 神经网络计算机神经网络计算机u神经计算机是一种智能计算机，它在接受与处理命令时模拟人脑的思维功能，它将把人造神经元组装起来，形成智能“机器脑”。u它是与神经解剖学有着密切联系，并模拟人脑思维方法的一种计算结构。它是一种很有发展前景的未来计算机。u用硬件实现或用软件模拟的方法、按照人用硬件实现或用软件模拟的方法、按照人工神经网络的基本原理而研制的计算机系工神经网络的基本原理而研制的计算机系统。统。特点 可以实现分布式联想记忆并能在一定程度上模拟人和动物的学习功能。它是一种有知识、会学习、能推理的计算机，具有能理解自然语言、声音、文字和图像的能力，并且具有说话的能力，使人机能够用自然语言直接对话，它可以利用已有的和不断学习到的知识，进行思维、联想、推理，并得出结论，能解决复杂问题，具有汇集、记忆、检索有关知识的能力。“神经网络计算机神经网络计算机”概念概念 神经网络计算机神经网络计算机用许多微处理机模仿人脑用许多微处理机模仿人脑的神经元结构，采用大量的并行分布式网的神经元结构，采用大量的并行分布式网络就构成了神经电脑。络就构成了神经电脑。人脑有亿神经元及亿多神经键，人脑总体运行速度相当于每秒人脑有亿神经元及亿多神经键，人脑总体运行速度相当于每秒 万亿次的电脑功能。万亿次的电脑功能。神经电脑神经电脑组成组成 神经电脑除有许多处理器外，还有类似神神经电脑除有许多处理器外，还有类似神经的节点，每个节点与许多点相连。若把经的节点，每个节点与许多点相连。若把每一步运算分配给每台微处理器，它们同每一步运算分配给每台微处理器，它们同时运算，其信息处理速度和智能会大大提时运算，其信息处理速度和智能会大大提高。高。神经电子计算机的信息不是存在存储器中神经电子计算机的信息不是存在存储器中，而是存储在神经元之间的联络网中。若，而是存储在神经元之间的联络网中。若有节点断裂，电脑仍有重建资料的能力，有节点断裂，电脑仍有重建资料的能力，它还具有联想记忆、视觉和声音识别能力它还具有联想记忆、视觉和声音识别能力。神经电脑应用 识别文字、符号、图形、语言以及声纳和识别文字、符号、图形、语言以及声纳和雷达收到的信号，判读支票，对市场进行雷达收到的信号，判读支票，对市场进行估计，分析新产品，进行医学诊断，控制估计，分析新产品，进行医学诊断，控制智能机器人，实现汽车自动驾驶和飞行器智能机器人，实现汽车自动驾驶和飞行器的自动驾驶，发现、识别军事目标，进行的自动驾驶，发现、识别军事目标，进行智能决策和智能指挥等。智能决策和智能指挥等。研究进展 日本科学家开发的神经电子计算机用的大日本科学家开发的神经电子计算机用的大规模集成电路芯片，在厘米正方的规模集成电路芯片，在厘米正方的硅片上可设置个神经元和硅片上可设置个神经元和 个神经键，这种芯片能实现每秒亿次个神经键，这种芯片能实现每秒亿次的运算速度。的运算速度。美国研究出由左脑和右脑两个神经块连接美国研究出由左脑和右脑两个神经块连接而成的神经电子计算机。右脑为经验功能而成的神经电子计算机。右脑为经验功能部分，有万多个神经元，适于图像识别部分，有万多个神经元，适于图像识别；左脑为识别功能部分，含有万个；左脑为识别功能部分，含有万个神经元，用于存储单词和语法规则。神经元，用于存储单词和语法规则。9.4 9.4 基于面向对象程序设计语言的计算机基于面向对象程序设计语言的计算机 面向对象 从概念上讲，对象是一个把数据结构和对数据进从概念上讲，对象是一个把数据结构和对数据进行操作的过程融合为一体的逻辑实体。行操作的过程融合为一体的逻辑实体。从计算机的实现角度看，对象是占据一片存储空从计算机的实现角度看，对象是占据一片存储空间的、统一格式的数据结构。间的、统一格式的数据结构。各个对象将在程序的运行中动态地建立和消亡。各个对象将在程序的运行中动态地建立和消亡。各个对象之间只通过发送或接收消息互相作用。各个对象之间只通过发送或接收消息互相作用。基于面向对象程序设计语言的计基于面向对象程序设计语言的计算机体系结构算机体系结构 具有高效能的、面向对象的动态存储管理具有高效能的、面向对象的动态存储管理、存储保护和快速匹配、检索对象的机制、存储保护和快速匹配、检索对象的机制 提供实现对象之间高效通信的机制提供实现对象之间高效通信的机制 是一个多处理机系统，以便让各个对象或是一个多处理机系统，以便让各个对象或由多个对象组成的模块分别在各自分配到由多个对象组成的模块分别在各自分配到的处理机上执行，提高并行处理的能力。的处理机上执行，提高并行处理的能力。9.5 分子、生物计算机 人类有一门学科叫仿生学，即通过对自然界生物特性的研究与模仿，来达到为人类社会更好地服务的目的。生物计算机（biological computer）又称仿生计算机(bionic computer)。生物计算机原理生物计算机主要是以生物电子元件构建的计算机。它利用蛋白质有开关的特性，用蛋白质分子作元件从而制成的生物芯片。生物芯片存储点只有一个分子大小，所以它的存储容量可以达到普通计算机的十亿倍。蛋白质集成电路，大小只相当于硅片集成电路的十万分之一。运行速度10-11秒，大大超过人脑的思维速度。生物计算机的种类 超分子芯片超分子芯片自动机模型自动机模型仿生算法仿生算法 细胞计算机细胞计算机生物化学反应算法生物化学反应算法生物计算机的种类立足于传统计算机模式，从寻找高效、体微的电子信立足于传统计算机模式，从寻找高效、体微的电子信息载体及信息传递体入手，目前已对生物体内的小分息载体及信息传递体入手，目前已对生物体内的小分子、大分子、超分子生物芯片的结构与功能做了大量子、大分子、超分子生物芯片的结构与功能做了大量的研究与开发。的研究与开发。“生物化学电路生物化学电路”即属于此。即属于此。超分子芯片超分子芯片（生物分子）（生物分子）自动机模型自动机模型 仿生算法仿生算法以自动理论为基础，致力与寻找新的计算机模式，特别以自动理论为基础，致力与寻找新的计算机模式，特别是特殊用途的非数值计算机模式。目前研究的热点集中是特殊用途的非数值计算机模式。目前研究的热点集中在基本生物现象的类比，如神经网络、免疫