计算机系统结构(第二版)尹朝庆主编-第7章_数据流计算机.ppt

第7章 数据流计算机 7.1 数据流计算机的基本原理 7.2 数据流程序图和数据流语言 7.3 数据流计算机结构 7.4 数据流计算机的性能评价及发展趋势 1 第7章 数据流计算机 传统的冯诺依曼(von neumann) 型计算机采用的是指 令驱动方式，即在程序计数器的集中控制下顺序地执行指 令以实现各种功能，因此属于控制流计算机。由于机器本 质上的串行顺序处理工作机制，使其并行性的提高受到限 制。为了设计高性能计算机的系统结构，其方法之一是突 破冯诺依曼型计算机的结构，采用数据驱动方式形成数据 流计算机，从而实现大规模的并行处理。 2 第7章 数据流计算机 7.1 数据流计算机的基本原理 7.1.1数据流计算机的驱动方式 数据流计算机是以数据驱动机制为基础，在数据可用 性控制下并行执行指令。所谓数据驱动的数据流方式， 指的是任何指令只要它所需要的数据准备就绪，这些指 令就可并行地执行。执行的结果并不送往存储器保存起 来，以供其他指令共享，而是直接流向所有需要该结果 的指令，并作为这些指令的操作数，驱动这些指令的执 行。 3 第7章 数据流计算机 数据以数据令牌方式直接在指令之间传递。所谓数据 令牌，是一种表示某一操作数或参数已准备就绪的标志 。由于操作结果不改变机器状态，从而具有纯函数的特 点。这种机器需要有专门的机构来检测数据可用性，将 数据令牌和缺乏数据的指令进行匹配，同时使指令执行 的异步链接作用得以实现。 4 第7章 数据流计算机 对于表达式 a(b2)(bc) 串行控制驱动方式的处理 过程如图7.1所示。操作按事 先指定的指令执行序列顺序进 行，主要受pc控制。 5 第7章 数据流计算机 图7.2所示为并行控制驱动 方式的处理过程。使用fork 语句结构派生出并行任务，使 i1和i2 两者并行执行，然后用 join语句结构对它们进行同步 。对存储器中的数据访问与图 7.1中相同。 6 第7章 数据流计算机 在数据驱动方式中，操作按数据相关和资源可用性所确定 的序列来进行。当一条指令所需的操作数(数据令牌)全部到达 ，且有可用的计算资源时，便可进行计算，过程如图7.3所示 。 7 第7章 数据流计算机 数据流计算机还有另一种以需求驱动机制为基 础的归约计算机。它的操作是由对一个操作结果 的需求而启动的。即当一些计算需要用到一种操 作的结果时，归约机制就启动这种操作。 8 第7章 数据流计算机 数据驱动具有以下特性。 异步性(asynchrony)。 并行性(parallelism)。 函数性(functionalism)。 局部性(locality)。 9 第7章 数据流计算机 7.1.2 数据流计算机的指令结构 数据流计算机的指令结构如图7.4所示 10 第7章 数据流计算机 数据流计算机不需要像传统计算机那样用程序计数器控 制指令的执行顺序，也不需要通过访问共享存储器来实现指 令之间的数据传送。它通过在需要数据的指令之间传送数据 令牌来实现指令之间传送数据和激活指令执行，程序的执行 过程主要受到指令之间数据相关性的限制。 另外，数据流计算机允许多个操作包和多个数据令牌同 时在各个操作部件之间传送，允许多条指令并行执行。为此 ，数据流计算机需要有一套能够并行执行多条指令的操作部 件和高效的操作包与数据令牌的传送机构。 11 第7章 数据流计算机 7.2 数据流程序图和数据流语言 7.2.1 数据流程序图 数据流程序图是一种用来表示数据流计算机指令级的数 据流程序的有向图，它是由多个结点和一些连接这些结点的 单向弧线组成。 数据流程序图中的每个结点是一个用圆圈 、三角形或其 他图形表示的处理部件。结点内的符号或字母表示某种操作 ，故称为操作符。单向弧线表示数据令牌在结点间的流向。 12 第7章 数据流计算机 1. 数据流程序图的操作结点 （1）常数产生结点 如图7.5(a)所示，它没有输 入端，只有一个输出端，其功能 是产生常数。结点操作激发执行 后输出携带指定常数的数据令牌 。 13 第7章 数据流计算机 （2）复制操作结点 如图7.5(b)所示，复制结 点分为两种，一种是数据复 制结点，实现数据的多个复 制，数据端以实箭头表示； 另一种是控制复制结点，实 现控制量的多个复制，控制 端以空心箭头表示。复制操 作结点有时也称连接操作结 点，图7.5(c)所示分别为数 据连接结点和控制连接结点 以及激发执行的结果。 14 第7章 数据流计算机 （3）运算操作结点 运算操作结点用圆圈表示，圈中有相应的操作符。主要 的运算操作包括加、减、乘、除、加1、减1、乘方、开方 等算术运算以及与、或、非、异或、或非等布尔逻辑运算。 激发执行后输出带有相应操作结果的令牌。 15 第7章 数据流计算机 （4）判断操作结点 如图7.5(d)所示，判断操作结点用一个菱形表示，它有 若干个数据输入端和一个控制输出端。结点对输入数据按某 种关系进行判断和比较，如果条件满足，将在输出端产生 t(ture)的控制令牌，否则便产生f(false)的控制令牌。 16 第7章 数据流计算机 （5）控制操作结点 控制操作结点的激发条件需要加入布尔控制端，用来控制数 据令牌的传送时刻。控制操作结点有四种，如图7.6所示。 lt门结点：仅当布尔控制端为真，且输入端有数据 令牌时才能激发执行，执行结果是将输入端的数据令牌 传送到输出端。 lf门结点：仅当布尔控制端为假，且输入端有数据 令牌时才能激发执行，执行结果仍是将输入端的数据令 牌传送到输出端。 l开关门控结点(sw结点)：开关门控结点用一个椭圆 形表示，它有一个数据输入端和两个数据输出端，并受 控制端控制。激发执行的结果是根据控制端值的真假， 确定t输出端或f输出端带有输入端的数据令牌。 l归并门控结点(mg结点)：归并门控结点也用一个椭 圆形表示，它有两个数据输入端和一个数据输出端，并 受控制端控制。激发执行的结果是根据控制端值的真假 ，在输出端上产生来自t输入端或f输入端的数据令牌。 17 第7章 数据流计算机 图7.6 控制操作结点 18 第7章 数据流计算机 2. 数据流程序图的活动模片表示法 活动模片表示法是数据流程序图的另一种更接近于机器语 言，也更容易理解机器的工作原理的表示方法。此方法将数据 流程序图中一个或多个操作结点与一个活动模片相对应，数据 流程序可以看成是一组活动模片的集合体。每一个活动模片由 4个域组成，包括一个操作码域，两个操作数域和一个目的域， 其结构如图7.7所示。 活动模片实际上是结点在数据流机器内部具体实现时的存 储器映像。可以将活动模片表示的数据流程序图作为数据流机 的可执行机器代码程序，能够由数据流机硬件直接解释执行。 数据流机操作系统中的分派程序可根据活动模片数据流程图来 调度各个活动模片，分配给多个处理器并行执行。 19 第7章 数据流计算机 3. 数据流程序图举例 例7.1用数据流程序图 和等效的活动模片表示如下 功能(具有顺序结构)： z(ab)(ab) 解：数据流程序图如图 7.8(a)所示 20 第7章 数据流计算机 z(ab)(ab) 等效的活动模片表示如图7.8(b)所示。 21 第7章 数据流计算机 例7.2用数据流程 序图描述功能(具有条件分 支结构)：当x0时，zx y；否则 zxy。 解：数据流程序图如图 7.9(a)所示。 22 第7章 数据流计算机 当x0时，zxy；否则zxy。等效的活动模片 表示如图7.9(b)所示。 23 第7章 数据流计算机 例7.3用数据流程序 图描述功能（具有循环结构 ）：对x进行循环累加，直 至超过1000时，z等于x的 累加值。 解：数据流程序图如图7.10 所示。 24 第7章 数据流计算机 例7.4画出求一元二次方 程两个实数根的数据流程序 图，基本的运算结点有、 、*、和。指出哪些基本 运算操作可以并行执行？如 果每个操作结点的执行时间 均为一个时钟周期，则整个 计算过程总共需要多少个时 钟周期？ 解：可并行执行的基本运算 操作如图7.11所示，其中 与、与、与均可 并行工作，但相互之间因为 存在数据相关而不能并行。 25 第7章 数据流计算机 求一元二次方程根 的数据流程序图如图 7.12所示，如果每个操 作结点的执行时间均为 一个时钟周期，则整个 计算过程总共需要8个时 钟周期。 26 第7章 数据流计算机 7.2.2 数据流语言 数据流程序图作为数据流机器语言，虽然直观易懂，但编 程效率低，故需要研究适合于数据流机使用的高级语言。 发展新型、适合于数据流控制机制的高级语言一直是数 据流计算机研究的重要内容。希望新的数据流语言能自然而充 分地表达出计算并行性，编程方便、高效。目前这方面的研究 还不成熟，没有形成像传统高级语言那样的完整性和规范性。 27 第7章 数据流计算机 1. 数据流语言的类型 （1）单赋值语言(single assignment language) （2）函数类语言(functional language) （3）命令类语言(command language) 28 第7章 数据流计算机 2. 数据流语言的特点 传统的程序设计语言是建立在冯诺依曼系统结构上的，这 种控制流语言不能充分表达程序中的并行性。数据流语言与传 统程序设计语言相比具有以下特点。 （1）并行性好 程序不规定语句的执行顺序，语句的执行顺序也不会影响 计算的最终结果。程序的执行过程仅受指令之间数据相关性的 约束，而与指令的存储位置无关。因此，数据流语言能够以很 自然的方式最大限度地表达程序中的并行性。 29 第7章 数据流计算机 （2）单赋值规则 所谓单赋值规则，是指在程序中每个变量只能赋值一次 ，即在所有语句的左边，同一个变量名只能出现一次。单赋 值语言没有传统计算机语言中的变量的概念，只是一种值名 。单赋值规则使程序中的语句语义清楚，且程序中的并行性 易于被编译程序识别和开发。 30 第7章 数据流计算机 （3）不产生副作用 在传统的程序设计语言中，允许使用全局变量或公共变量 ，使变量的使用范围扩大。任何一个过程在执行中都可以对全 局变量赋值，打破了操作结果的局部性；程序执行时还可能出 现对同名变量多处赋值；调用子程序时修改了调用程序中的变 量等情况。这将导致产生一个程序执行后由于改变了公共变量 ，从而影响其他程序的正确执行的副作用。 在数据流语言中，不使用全局变量和公共变量，严格控制 变量的使用范围。数据传送采用数据令牌直接在指令之间进行 ，使每一个操作产生的结果都具有局部性。另外，采用赋值调 用而不是传统语言中的引用调用，而赋值调用过程只复制变量 而不修改变量。因此，在子程序中决不会修改调用程序传送来 的变量。也就是说，数据流语言的各程序模块之间的i/o是完全 隔离的，可以避免产生不必要的副作用。 31 第7章 数据流计算机 7.3 数据流计算机结构 7.3.1静态数据流计算机 静态数据流计算机结构模型如图7.13所示。 32 第7章 数据流计算机 静态数据流计算机中的数据令牌是按反映程序要求的数据 流程序图来流动的。静态数据流计算机的主要特点是数据令 牌不带任何标记，在数据流程序图的任何一条弧上只允许存 在一个数据令牌。 mit静态数据流计算机结构框图如图7.14所示。 33 第7章 数据流计算机 图7.14 mit静态数据流计算机结构 框图 34 第7章 数据流计算机 系统主要由五个部分组成： l存储部件(ms)由若于指令单元组成。每个指 令单元保存数据流程序中的一条指令，它与数据流 程序图中的结点对应且由惟一的地址所指明。 l处理部件(ps)由对数据值进行基本运算的多 个处理单元(pu)组成，可以并发执行已被激活的指 令所要求的操作。 l仲裁网络(an)将可执行的操作包由存储部件 发送到处理部件，允许有多个操作包同时在多个通 路上传输。 l控制网络(cn)将控制令牌由处理部件发送到 存储部件相应的指令单元中。 l分配网络(dn)将处理部件产生的多个结果数 据令牌依其各自的目的地址分别传送至存储部件相 应的指令单元。 35 第7章 数据流计算机 7.3.2 动态数据流计算机 动态数据流计算机中的每个数据令牌都带有标记，从而 可以使数据流程序图中的任一条弧上同时出现多个带不同标记 的令牌。因令牌的标记中包含能识别该令牌时间先后相应关系 的标号，故无需像静态数据流机中那样依赖控制令牌来确认指 令间数据令牌的传送。动态数据流计算机的同步是由匹配部件 实现的，它将标记附加到数据令牌上，并对数据令牌中的标记 进行符合比较，完成标记的匹配工作。典型的动态数据流计算 机的基本结构如图7.15所示。 36 第7章 数据流计算机 图7.15 典型的动态数据流计算机的基本结构 37 第7章 数据流计算机 1. 网络型结构动态数据流计算机 mit动态数据流计算机是网络型的典型代表，其基本结构如 图7.16所示。 38 第7章 数据流计算机 mit动态数据流计算机由n个处 理单元(pe)和一个用于实现pe间通 信的nn的包交换开关网络组成。 每个pe基本上是一台完整的处理机 ，它包括有自己的程序/数据存储器 、i结构存储器、标记匹配部件、 算术逻辑部件、打标记和对标记特 征控制的部件及其他硬件。nn的 包交换开关网络为令牌提供从发出 它的pei到吸收它的pej的通路。如 果吸收令牌的pe就是发出此令牌的 pe，则不经开关网络传送。 mit动态数据流机指令的一般格 式如图7.17所示。 39 第7章 数据流计算机 pe的内部结构如图7.18所示 。 40 第7章 数据流计算机 2. 环型结构动态数据流计算机 manchester动态数据流计算机是环形结构的典型代表， 其结构如图7.19所示 。它的5个功能部件形成一个环状流水 线，采用令牌包通信。这种结构允许多个令牌以先进先出的 队列形式同时存在于数据流程序图的一个弧上，故属于动态 数据流机。 41 第7章 数据流计算机 7.4 数据流计算机的性能评价及发展趋势 7.4.1数据流计算机的优点 1. 高度的操作并行性 由于数据驱动方法没有指令执行顺序的限制，从理论上讲 ，只要有充分的硬件资源，就能获得最大的并行性。已经得 到验证，数据流计算机在处理许多应用问题时的加速比随使 用处理机数目的增加而线性地增长。 数据流计算机显示了操作的高度并行性，它不仅可用来开 发程序中有规则的并行性，而且也能够开发程序中隐含的并 行性。 42 第7章 数据流计算机 2. 便于开发过程和指令级的异步并行 数据流计算机的指令直接使用操作数，而不是使用存放 操作数的地址，因此能实现无副作用的纯函数型程序设计方 法。便于在过程级和指令级充分开发程序中的异步并行性， 可以把串行计算的问题用简单的方法展开成并行计算问题进 行并行处理。如通过同时展开一个循环程序中的多个相邻循 环体，将循环体内和循环体间本来相关的操作数直接互相迭 代而形成一条异步流水线，从而使一个循环程序内的不同层 次的循环体能够并行执行。 43 第7章 数据流计算机 3. 机器结构与vlsi技术发展相适应 数据流计算机结构的基本组成具有模块性和均匀性，与 vlsi技术相适应。其指令存储器、数据令牌缓冲器和可执 行指令队列缓冲器等存储部件均可采用vlsi技术制造的存 储阵列均匀地构成，处理部件和信息包开关网络也可用模块 化的标准单元有规则地连接实现。vlsi技术的进一步发展 ，必然为研制高性能价格比的数据流计算机提供更好的支持 。 44 第7章 数据流计算机 4. 有利于提高程序设计效率 在数据流计算机中，采用函数程序设计语言。这种纯函 数操作取消了变量和变量赋值机制，从根本上消除了传统编 程语言中因大量使用全局变量和同名变量而产生的副作用。 函数程序设计语言的自动向量识别能力大为提高，便于 对数据流的分析和处理。基于这种语言编写的程序符合程序 设计方法学的要求，良好的程序结构不仅降低了程序编制的 难度，而且为程序的调试和验证提供了很好的基础。从而可 以提高程序设计的生产能力、效率及可靠性。 45 第7章 数据流计算机 7.4.2 数据流计算机存在的主要问题 1. 系统开销大 数据流计算机的指令格式与传统计算机不同，它包含一 个操作码、两个源操作数以及一个或多个后继指令地址，某 些动态数据流计算机的指令中还有许多标记位，所以其指令 长度一般较长。与传统计算机相比，需要占用更多的系统存 储器资源来保存用这种指令编写的程序，而用于完成其指令 的存取所花费的时间更长。 46 第7章 数据流计算机 2不能有效利用传统计算机的研究成果 数据流计算机独特的解题方法使它具有与传统计算机完 全不同的结构，令其可以摆脱传统计算机系统结构的束缚， 但同时意味着它无法吸收利用许多经证明在传统计算机中行 之有效的研究成果。 另外，数据流计算机采用的基于数据流程序图的机器语 言，使得在传统计算机上长期积累的大量软件成果无法实现 软件继承。这将导致数据流计算机在市场上与传统计算机竟 争中的不利。 47 第7章 数据流计算机 3数据流语言尚不完善 目前提出的数据流语言都不够完善，仍需要进一步改进 。例如，计算机的输入输出操作至今还未引入到数据流语言 中来。数据流语言是以隐含的方式描述并行性，并由编译器 来开发其中的并行