-数据流机和规约机课件

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