大D要说:这是《计算机系统结构》最后一篇读书笔记,这本书也看完了,但是。。基本就饭吃了,全部都忘掉的感觉。。。

果然是天书,又不好懂,又不好记。


 

第八章 数据流计算机和归约机

8.1 数据流计算机

8.1.1 数据驱动的概念

Von Neumann型计算机的基本特点是在程序计数器集中控制下,顺次地执行指令,是以控制流(Control Flow)方式工作的。虽然可以在系统结构、程序语言、编译技术等方式改进,发展流水线机、阵列机或多处理机,但本质上仍是指令在程序计数器控制下顺序执行,这就很难最大限度地发掘出计算的并行性。

数据驱动的数据流方式指:只要一条或一组指令所要求的操作数全部准备就绪,就可以立即激发响应的指令或指令组执行,执行结果的输出将送往等待这一数据的下一条或下一组指令。如果其中一些指令因此而使所需用到的数据全部准备就绪,就可以被激发执行。

在这种计算机上不需要程序计数器,指令的执行基本上是无序的,完全受数据流的驱动,与指令在程序中出现的先后顺序无关。操作收到数据相关所制约。

控制驱动的控制流方式是:通过访问共享存储单元让数据在指令之间传递;指令执行的顺序性隐含于控制流中,但却可以显式地使用专门的控制操作符来实现并行处理,指令执行的顺序受程序计数器控制。

数据驱动数据流的方式:它没有通常的共享变量的概念,即没有共享存储数据的概念,指令执行顺序只受指令中数据相关性的制约,数据是以数据令牌方式直接在指令之间传递的。

数据令牌是一种表示某一操作数或参数已准备就绪的标志。

一旦某一操作的所有操作数令牌都到齐,则标志着这一操作是什么操作,以及操作结果所得出的数据令牌应发送到那些的等待此数据令牌的操作的第几个操作数部件等有效信息。都讲作为一个消息包(Message Packet),传送到处理单元或操作部件并予以执行。

数据流是基于异步性和函数性的一种计算模型。

异步性:一旦操作数到齐就开始操作,这是数据流计算机开拓并行性的基础。

函数性:每一数据流操作都是消耗一组输入值,产生一组输出值而不发生副作用。具有变量出现在赋值语句左边近义词的单赋值特性。从而保证两个并发操作可以任意次序执行。不会互相干扰。

8.1.2 数据流程序图和语言

数据流程序图是一种有向图,它有多个结点(Node),并用一些弧(Arc)把它们连接而成。每一节结点用圆圈或三角形或其他特殊符号表示,认为是一种处理部件。结点内的符号或字母表示一种操作,所以也称操作符(Actor)。

弧代表数据令牌在结点间的流向。在数据流计算机中,根据这些数据流程序图,通过一个分配器或分配程序(Allocator),不断分配适当的处理部件来实现操作符的操作。

8-3 计算z=(a+b)*(a-b)的数据流程序图

8-3 计算z=(a+b)*(a-b)的数据流程序图

数据流程序图中程序的执行过程是一种数据不断进行激发(驱动)的过程,一个操作符的执行从每个输入端只吸收一个令牌,计算后,只在有效的输出端上产生一个输出令牌,这种单赋值规则使结点在生成和消灭时,可以有序地分配和回收值。

为满足需要,引入一些结点,如下:

1)常数产生结点(Identity):没有输入端,只产生常数。激发后产生常数

2)算逻预算操作结点(Operator):主要包括+、-、*、/、乘方、开放等算术运算以及与或非、异或、或非等布尔逻辑运算。激发后输出带相应操作结果的令牌。

3)复制操作结点(Copy):数据多个复制/控制量的多个复制,数据端以实箭头表示,控制端以空心箭头表示。

4)判定操作结点(Decider)对输入数据按某种关系进行判断和比较,激发后在输出控制端给出带逻辑值真(T)或假(F)的控制令牌。

5)控制类操作结点:控制类才做结点的激发条件需要加到布尔控制端。

数据流程序的临沂中表示方法更接近于机器语言,也更容易理解机器的工作原理,这就是活动模片(Activity Templete)表示法。数据流实际上可以被看成是一组活动模片组成的集合体。每一个活动模片相应于数据流程序图中的一个或多个结点,且由4个域组成:一个操作码域,两个操作数域以及一个目的域。

活动模片就是结点在数据流计算机内部具体实现时的存储器映像。

数据流计算机操作系统中的分配程序就是根据活动模片数据流程序图来调度各个活动模片,分配给多个处理器并行执行。

数据流程序图实际上是数据流计算机的机器语言,有点事直观易懂,但编程效率低。无法被一般用户接受。

适用于数据流计算机的设计语言有单赋值语言和函数程序设计语言。

单赋值语言是指在程序中,每个变量均只赋值一次,即同一变量名在不同赋值语句的左部最多只出现一次。因此,实际上并没有传统计算机中的变量的概念,只是一种值名。例如, 一个程序允许出现如下语句序列

著名的单赋值语言有ID语言、VAL语言等。

VAL语言的特点:

1)遵循单赋值规则

2)丰富的数据类型

3)很强的类型性

4)具有模块化结构的程序设计思想

5)没有全局寄存器和状态的概念

6)程序不规定语句的执行顺序

8.1.3 数据流计算机的结构

根据对数据令牌处理方式的不同,可以吧数据流计算机的结构分成静态和动态两类

1.静态数据流计算机

静态数据流计算机的数据令牌没加标号。同时出现两个数据令牌的话,会无法区分,必须另设控制令牌(Control Token),以识别数据令牌由一个结点传送到另一个结点的时间关系。从而区分属于不同迭代层次的各批数据。

静态数据流计算机不支持递归的并发激活,只支持一般的循环。

2.动态数据流计算机

所有令牌均有标记,需要设置硬件标记来完成标记匹配工作。

8.1.4 数据流计算机存在的问题

(1) 数据流机主要目的是为了提高操作级并行的开发水平,但如果题目本身数据相关性很强,内含并行性成分不多时,就会导致数据流机的效率反而不如传统的Von Neumann型机器的高。

(2) 在数据流机器中为了给数据建立标记并识别和处理该标记,需要花费较多的辅助开销和较大的存贮空间(可能比Neumann型的要大出 2 至  3 倍)。

(3) 数据流机不保存数组。

(4) 数据流语言的变量代表数值而不是存贮单元位置, 使程序员无法控制存贮分配。 为了能有效地回收不用的存贮单元, 就增大了编译程序设计的难度。

(5) 专门适合于数据流机用的互连网络的设计较困难, 而且, 对数据流机的输入/输出尚待完善。

(6) 数据流机没有程序计数器, 给诊断和维护带来困难。

8.1.5 数据流计算机的发展

1.采用提高并行度等级的数据流计算机

并行性级别提高到函数或复合函数一级上,用数据来直接驱动函数或符合函数。就可以明显减少总的开销。在全操作循环、流水线循环、赋值语句、符合条件语句、数组向量晕眩及线性递归计算机上采用复合函数级的并行。这样就可以用传统高级语言来编写问程序。

2.采用同、异步结合的数据流计算机‘

在函数级及函数级智商采用一步操作。减少计算机的操作开销。

3.采用控制流与数据流相结合的计算机

控制流与数据流结合,可以继承传统控制流计算机的优点。

8.2 归约机

从函数程序设计的角度看,一个程序就是一个函数的表达式。通过定义一组“程序形成算符”(Program Forming Operators), 可以用简单函数(即简单程序)构成任意复杂的程序,也就是, 构成任意复杂函数的表达式。反过来,如果给出了一个属函数表达式集合中的复杂函数的表达式,利用提供的函数集合中的子函数经过有限次归约代换之后,总可以得到所希望的结果, 即由常量构成的目标。函数表达式指的是函数之间的映射。 从语法上讲是按规定的语法规则构成的符号串,从语义上讲是多个运算符的组合。

函数集合中包括了所有的原函数和复合函数。原函数(Primitive Function)指的是,由一个目标变换为另一个目标的基本映射,是归约机建成时安装上的函数。 它们可以包括有: 从一个元素序列中选出某一个元素的函数, 加、 减、 乘、 除等算术函数, 交叉置换函数, 比较、 测试函数, 附加序列函数, 加 1/减 1 函数, 等等。 复合函数指的是利用一组“程序形成算符”由已有的函数(程序)构成复杂的函数(程序)。 使用的“程序形成算符”一般有组合、 构造、 条件、 插入、 作用于全体等多种。

有如下主要的优点:

(1)程序的每一行语句可以表达出更多有关算法的信息。

(2) 没有状态和存贮单元的概念,函数自变量的值随函数的应用动态获得, 因此不会产生一个过程的变量受到另一过程影响的副作用,即被应用的函数改变不了函数定义时的约束关系。

(3) 没有赋值语句,不会出现像命令式语言里的赋值语句x=x+1那样一种与数学里的变量不相符和违反数学中“相等性”演绎推理规则的现象;同时,没有使用GO TO类控制语句。

(4) 指令执行的顺序只受操作数的需求所制约, 只要没有数据依赖关系的函数,原则上都可以在不同处理器上并行处理, 所以程序中的并行性较易检测和开发。

(5) 程序具有单一的递归结构,即函数又是由函数构成。一个函数程序的功能只与组成该函数程序的各函数成分有关。数据结构是目标的组成部分,不是程序的组成部分,因此同一个函数程序可以处理结构、大小不同的目标,增强了程序

与本文相关的文章
版权声明
转载保留版权: 大D综合研究院 | 《《计算机系统结构》读书笔记(二十)》
本文链接地址:https://www.dadclab.com/archives/3251.jiecao
转载须知:如果您需要转载本文,请将版权信息,版权授权方式,以及本文的链接地址注明,谢谢合作。
本文被贴上了: , , , , 标签