第八章 数据流机和规约机

,单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,第八章,数据流机和规约机,目录,数据流机,基于数据驱动的，使用数据流语言,规约机,基于需求驱动的，使用函数式语言,数据流计算机,数据驱动的概念,数据流程序图和语言,数据流计算机的结构,数据流机器存在的问题,数据驱动的概念,Von Neumann,型计算机的特点,在程序计数器集中控制下，顺序地执行指令,以控制流（,Control Flow,）方式工作,可以在系统结构、程序语言、编译技术等方面改进,很难最大限度地发掘出计算的并行性,任务描述：解方程,ax,2,+,bx,+c=0,，,解的形式为：,举例：解一元二次方程组,Fortran,程序,READ*,A,B,C,X1=2*A,D=SQRT(B*B-4*A*C),D=D/X1,X2=-B/X1,X1=X2+D,X2=X2-D,PRINT*,X1,X2,END,数据流方式,数据驱动方式（,Data Driven,）,只要一条或一组指令所要求的操作数全部准备就绪，就可立即激发相应的指令或指令组执行,不需要程序计数器,指令执行是无序的，完全受数据流的驱动,只要数据不相关和资源可以利用，就可以并行,数据相互关系,输入,a,b,c,-,*,*,*,2,4,*,-,aqrt,/,/,-,+,a,b,x1,x2,c,求一元二次方程根的数据流,程序图,控制驱动的控制流方式的特点,通过访问共享存储单元让数据在指令之间传递,指令执行的顺序隐含与控制流中，但却可以显示使用专门的控制操作符来实现并行处理,指令执行的顺序受程序计数器控制,受控制令牌所支配,数据驱动的数据流方式,只要一条或一组指令所要求的操作数全部准备就绪，就可立即激发相应的指令或指令组执行,执行结果的输出将送往等待这一数据的下一条或下一组指令,不需要程序计数器,指令的执行基本上是无序的，完全受数据流的驱动，与指令在程序中出现的先后次序无关,程序设计者完全摆脱了检查和定义程序中所有可能存在的并行性这一繁重工作，只要数据不相关且资源可以利用，就可以并行,数据驱动的数据流方式特点,没有共享变量的概念，即没有共享存储数据的概念,指令执行顺序只受指令中数据相关性的制约,数据是以数据令牌方式直接在指令之间传递,数据令牌：是一种表示操作数或参数已准备就绪的标志,数据流计算模型,数据驱动计算,是按输入数据可用性决定的次序进行,所要求的输入数据全部就绪，即可驱动操作执行,提前求值策略,需求驱动计算,是按数据需求决定的次序进行,按需求值，只有当某一函数需要用到某一自变量时，才驱动对该变量的求值操作,滞后求值策略,减少不必要的求值，辅助开销少，有利于提高系统的效率,数据流的语义,异步性（,Asynchriny,）：指一旦操作数到齐就开始操作,函数性（,Functionality,）：指每一数据流操作都是消耗一组输入值，产生一组输出值而不发生副作用（,Side Effect,），具有变量出现在赋值语句左边仅一次的单赋值特性，从而保证任何两个并发操作可以按任意次序执行，而不会发生相互干扰,数据流程序,用有向图表示指令级的数据流程序，数据流机器的机器语言,有多个结点（,Node,），并用一些弧（,Arc,）把它们连接而成,每一结点用圆圈或三角形或其他特殊符号表示，处理部件,结点内的符号或字母表示一种操作，操作符（,Actor,）,举例：计算,z=(,a+b,)*(a-b),+,-,*,a,b,a+b,a-b,z,数据流程序的执行过程,+,-,*,a,b,z,+,-,*,a,b,z,+,-,*,a,b,z,+,-,*,a,b,z,3,5,3,3,5,5,8,-2,-16,常数产生的结点（,Identity,）,T,T,激发后,没有输入端，只产生常数，激发后输出带常数的令牌,算逻运算操作结点（,Operator,）,主要包括常用的,+,、,-,、*、,/,、开方等算术运算及非、与、或、异或、或非等布尔逻辑运算，激发后输出带相应操作结果的令牌,复制操作结点（,Copy,）,a,激发后,a,a,a,是数据的多个复制，也可以是控制量的多个复制,复制操作结点（,Copy,）,激发后,激发后,d,d,d,d,c,c,c,c,数据连接,控制连接,判定操作结点（,Decider,）,0,a,激发后,0,T(a,0),=,a,激发后,b,b),对输入数据按某种关系进行判断和比较，激发后再输出控制端给出带逻辑值真或假的控制令牌,控制类操作结点,T,a,T,T,a,激发后,T,门控结点,F,a,F,F,a,激发后,F,门控结点,SW,T F,T,SW,T F,a,a,激发后,SW,T F,F,SW,T F,a,a,激发后,开关门控结点,T F,MG,T,a,激发后,T F,MG,a,T F,MG,T,a,激发后,T F,MG,a,归并门控结点,举例,1,：具有条件分支结构的数据流程序,0,SW,T F,+,SW,T F,-,y,x,z,If x0,z=,x+y,Else,z=,x-y,举例,2,：具有循环结构的数据流程序,(),(0),i2/2,x,i1,SW,(),(),i3/1,i2,(T),(F),+,(),(),i3,-,(),(),i4,y,i4/1,z,If x0,z=,x+y,Else,z=,x-y,活动模片就是结点在数据流机器内部具体实现时的存储映像，认为是数据流机的可执行的机器代码程序，有硬件直接解释执行,数据流机操作系统中的分派程序（,Allocator,），就是根据活动模片数据流程序图来调度各个活动模片，分配给多个处理器并行执行,数据流程序图实际上是数据流机的机器语言，直观易懂，但编程效率很低，难以接受,单赋值语言,在程序中，每个量均只赋值一次，即同一个量名在不同赋值语句的左部最多只出现一次。,美国的,ID(Irvine,Data Flow),语言、,VAL(Value,Oriented Algorithm Language),语言、法国的,LAU,语言，英国曼彻斯特大学的,SISAL,语言等,C=A+B,C=C*D,F=(C-D)/E,C=A+B,C1=C*D,F=(C-D)/E,单赋值语言的特点,遵循单赋值规则,有丰富的数据类型,具有很好的类型性,具有模块化结构的程序设计思想,没有全局存储器和状态的概念,程序中不规定语句的执行顺序,数据流计算机的结构,静态数据流机：数据令牌没有标号，不支持递归的并发激活,MIT,的,J.B.Dennis,提出的,MIT,静态数据流机,动态数据流机：令牌有标记,Arvind,研制的,Irvine,数据流机的改进机,英国曼彻斯特大学的,Manchester,数据流机,数据流机器存在的问题,目的是为了提高操作级并行的开发水平，如果项目本身数据相关性很强，内涵并行性成分不多时，效率低,在数据流机器中为给数据建立、识别、处理标记需要花费较多的开销和空间，如果不标记，则降低并行能力,不保存数组，对标量运算有利，而对数组、递归及其他高级操作难以管理,变量代表数值而不是存储单元位置，无法控制存储分配，增大编译难度,互联网络设计困难，输入,/,输出系统不够完善,没有程序计数器，给诊断和维护带来困难,数据流计算机的发展,采用提高并行度等级的数据流机,采用同步、异步结合的数据流机,采用控制流和数据流相结合的数据流机,规约机,与数据流机一样，基于数据流的计算模型,需求驱动，执行的操作序列取决于对数据的需求，对数据的需求又来源于函数式程序设计语言对表达式的规约（,Reduction,）,规约机的结构特点,面向函数式语言，或以函数式语言为机器语言的非,Von Neumann,型机器，其内部结构不同于,Von Neumann,型机器,具有大容量物理存储器并采用大圩村容量的虚拟存储器，具备高效的动态存储分配和管理的软、硬件支持，满足规约机对动态存储分配及所需存储空间大的要求,处理部分应当是一种有多个处理器或多处理机并行的结构形式，以发挥函数式结构并行处理的特长,采用适合于函数式程序运行的多处理器（机）互联的结构，最好采用树形方式的互连结构或多层次符合的互连结构形式,为减少进程调度及进程间通信开销，尽量把运行进程的结点及安排成紧靠该进程所需用的数据，并使运行时需相互通信的进程所占用的处理机也靠近，让各处理机的负荷平衡,规约方式,串规约：一种不断地定义表达式集合中去查找和赋值的过程,时间和空间开销比较大,*,-,+,1,5,2,z:28,g:4,h:7,y:5,y:5,x:2,y,x,z=(y-1)*(,y+x,),规约方式,图规约：,*,(4),z,(7),z,-,y,z/1,1,g,+,y,z/2,x,h,5,2,28,y,x,