计算机系统结构(计算机类)第9章

，东第9章数据流计算机系统结构

第9章数据流计算机系统结构

9」程序流机制

9.2计算机模型分类

9・3数』;流程序图和数据流语言

9.4数据流机的基本结构

习题9

，东第9章数据流计算机系统结构

9.1程序流机制

9.1.1控制流和数据流

传统的VonNeumann计算机用程序计数器PC确定程

序中指令执行的顺序，PC由程序中的指令流来定序。

这种顺序运行方式，因程序流为程序员显式控制，故

被称为控制驱动。

，东第9章数据流计算机系统结构

控制流计算机用共享存储器来保存程序指令和数据

对象，共享存储器中的变量可被多条指令修改。由于

存储器是共享的，所以一条指令执行后可能会对其它

指令产生副作用。在很多情况下，副作用会妨碍并行

处理。

事实上，由于采用控制驱动机制，因此单处理机计

算机本质上是顺序的机器。但是控制流可以用并行语

言结构或并行编译器构成并行的控制流。

，东第9章数据流计算机系统结构

在数据流计算机中，指令的执行是由数据可用性来

驱动的，而不是由程序计数器控制。理论上讲，任何

指令只要操作数可用，应该说是做好了执行的准备。

数据驱动程序中的指令不用任何方式来排定次序。数

据直接保存在指令内，不是存在共享存储器中。

计算结果（数据令牌）直接在指令之间传送。一条

指令产生的数据可被复制成多份副本直接送给所有缺

乏数据的指令。数据令牌一旦被一条指令使用后，它

就不能再被其它指令重复使用。

，东第9章数据流计算机系统结构

这种数据驱动方式不需要共享存储器，不需要程序

计数器，也不需要控制定序器。但是它需要有专门的

机构来检测数据可用性，将数据令牌和缺乏数据的指

令进行匹配，同时使指令执行的异步链接作用得以实

现。没有存储共享就不会产生副作用。

，心第9章数据流计算机系统结构_________________

9.1.2数据流驱动的基本原理

与传统的冯・诺依曼计算机不同，数据流计算机是采

用数据驱动的计算模型，有利于并行性的开发。

数据驱动的数据流方式是指：只要一条或一组指

令所要求的操作数全部准备就绪，就可立即激发相应

的指令或指令组执行。执行结果的输出将送往等待这

一数据的下一条或下一组指令。也就是说，在数据流

计算机中，一条指令能否执行的主要依据是：它所需

要的操作数是否已经全部到达。

，心第9章数据流计算机系统结构_______________

因此在这种机器上不需要程序计数器。一条指令执行后

产生的结果并不送往存储器保存起来，以供其它指令

共享，而是直接流向所有需要该结果的指令，并作为

这些指令的操作数，驱动这些指令的执行。因此程序

执行时所需的数据是一次性生成和消费的，即时产生

即时使用，操作数直接以“令牌”(token)或唯“的记号传

递而不是作为“地址”变量加以访问的。指令的执行基

本上是无序的，完全受数据流的驱动，与指令在程序

中出现的先后顺序无关。显然在数据流计算机中，程

序中众多指令的执行是异步并行进行的，只要所需的

操作数均已到达，又有可使用的计算资源，它们便可

同时执行，因此最有利于计算并行性的开发。

，心第9章数据流计算机系统结构_________________

在数据流计算机中，信息项以操作包和数据“令牌”

形式出现。操作包由操作码、操作数和其后继指令所

在地组成。数据“令牌”则由结果值和其去向目的地组

成，实质上是一种表示某一操作数或参数已准备就绪的

标志。众多的操作包和数据“令牌”在各个资源部件间

传递，因而数据流计算机可视为一种信息分组通信系

统结构，具有分布式多处理机组成形式。如图9.1,给

出了数据流计算机中的操作包和数据“令牌”以及它在

系统中的传送情况。

，东第9章数据流计算机系统结构

+()2R/1一()()R/2

图9.1数据流计算机中的操作包和数据令牌

，心第9章数据流计算机系统结构_________________

例9.1数据流计算机和控制流计算机的比较。如图

9.2(a)的数据流图表示有24条指令要运行(8条除法、8

条乘法和8条加法)。假定每次加、乘和除分别需要1、

2和3个周期完成操作。

第9章数据流计算机系统结构

(a)示例程序及数据流图

，东第9章数据流计算机系统结构

Cl88

bib2C2bsC8

(b)单处理机用48个周期完成顺序串行执行

，东第9章数据流计算机系统结构

(c)4台处理机的数据流计算和用14个周期完成数据驱动执行

.

，东第9章数据流计算机系统结构

147911121314

aablb5S

l51s1=b1+b2

bb

a2a626S2s2=63+64t2=S[+s2

b

a3a7^37S3S3-^5+^6

=-

S4b-74bg二S3+S4二Co+t2

bb

a4a848S4C4C8

c8=c4+t4

(d)共享存储器的4台处理机系统用14个周期完成并执行

图9.2数据流计算机和控制流计算机之间的比较

第9章数据流计算机系统结构

inputd,e,f

。0二。

forifrom1to8do

begin

ai=di4-ei

b1=a1*f1

ci=bi+ci4

end

outputa,b,c

，心第9章数据流计算机系统结构_________________

图9.2(a)的数据流图表示有24条指令要运行(8条

除法、8条乘法和8条加法)。数据流图与相关图或程

序图很相似，唯一的区别是数据令牌是沿数据流图中

的边传送的。假定每次加、乘和除分别需要1、2和3个

周期完成操作。因此，在控制流单处理机上顺序执行

24条指令要用令个周期才能完成,如图9.2(b)所示。

，东第9章数据流计算机系统结构

但是，数据流多处理机完成上述操作只要用14个周

期，如图9.2(c)所示。假设所有外部输入(5中

%i=l,2…，8和c0)在进入do循环前都是可用的。

对于用4台处理机，则指令为，a2,23和在前三个周期

内已全部准备好执行。所得结果接着从第四周期开始

起动@5,3,26和a7的执行。数据驱动的链接作用如图

9.2(c)所示，由于输出Cg与所有前面的5有关，所以

它最后一个得到。

，东第9章数据流计算机系统结构

图9.2(d)描述是在传统多处理机上，利用共享存

储器保存中间结果(s，叫，i=l,2,3,4)时同一计算

集合的执行情况。注意，在数据流实现中没有使用共

享存储器，这个例子并不说明数据流执行比控制流执

行在时间上有什么优越性。

沿关键通路电卜卜卜?…Cg的理论上的最小时间是13个

周期。数据流中的链式作用控制是较难实现的，而与

图9.2(d)中所有处理机完成的均匀操作相比，它产生

的开销也许会更大。

，东第9章数据流计算机系统结构

给每个数据做标记的优点是不同现场的数据可在指

令执行流水线中随意调配。因此数据流图的指令级并

行性可吸收通信时延，使由于同步等待而产生的损失

减到最小。除令牌匹配和I-结构外，还需要编译器技

术，才能得出带标志令牌数据流计算机的数据流图。

数据流系统结构为大规模并行计算提供了一种理想的

模型，因为远程副作用全被消除了。所谓副作用指的

是一些无关的操作对共享变量的修改。

，心第9章数据流计算机系统结构_________________

9.1.3需求驱动方式

在归约机(reductionmachine)中，计算是由对一个操

作结果的需求而启动的。假设要计算一个嵌套算术表

达式a=((b+l)Xc-(d+e))。数据驱动计算选用自底向上

的方法，从最里面的运算(b+1)和(d+e)开始，然后进

行“X”运算，最后进行最外面的运算。这种计算已

被称为积极计算(eagerevaluation),因为运算是在其操

作数成为可用后立即进行的。

，东第9章数据流计算机系统结构

需求驱动计算则选用自顶向下的方法，首先需求a

值，a值去触发对计算下一级表达式(b+l)Xc和(d+e)的

需求，此表达式再依次触发计算最里层(b+1)的需求。

然后，所有结果在算出a之前以相反次序返回给嵌套需

求者。

需求驱动计算与惰性计算(lazyevaluation)相对应，

因为操作只有在另一条指令需要结果时才执行。需求

驱动方式与函数程序设计概念自然匹配。函数程序设

计中副作用消除后，程序也比较容易并行化。

，心第9章数据流计算机系统结构_________________

9.1.4归约机模型

归约机和数据流机一样，都是基于数据流的计算模

型，但其驱动方式是采用需求驱动。在这种模型中，

某条指令的执行，仅当其它指令需要用它时才会进行。

归约机是一种面向函数程序设计语言的计算机，指令

的执行顺序取决于这些指令产生结果数据的需求，而

这种需求又源于函数式程序设计语言对表达式的归约。

，东第9章数据流计算机系统结构

归约机模型有两种类型，即串归约模型和图归约模型。

两者的主要区分是对函数表达式所使用的存储方式不

同，前者以字符串形式存储而后者以图的形式存储。

在串归约(stringreduction)模型中，每个需求者可得到

它自己计算用的单独的表达式副本。一个长的串表达式

可以用递归方式归约为单值。每个归约步都有一个操作

符，后面紧跟一个对所需要的相应输入操作数的引用。

操作符在其输入变量正在计算时将被挂起。当全部变量

被实在的值替代时，表达式才算是归约完毕。

，东第9章数据流计算机系统结构

在图归约(graphreduction)模型中，表达式是用有向

图表示的。图用计算分支或子图进行归约，根据需要

可对图上的各个部分或子图进行并行归约或计算。每

个需求者都有一个指向归约结果的指针，需求者对图

的全部引用标记进行变换操作。

我们采用指针共享变量来实现图的变换，这种图的

遍历和颠倒引用一直要继续到遇到常量为止。在求出a

值以及副本返回原发出需求的指令之前，这个过程一

直在进行中。

在表9.1中我们对控制流、数据流和归约计算机的系

统结构进行了比较。

，东第9章数据流计算机系统结构

表9.1控制流、数据流和归约计算机

机器控制流数据流归约

模型（控制驱动）（数据驱动）（需求驱动）

惰性计算：语句只在其结

基本常规计算：令牌控制指明积极计算：当操作数全部

果被另一运算请求时才执

定义语句何时应执行可用时，语句才执行

行

全控制并行性潜力很大只执行被请求的指令

优点吞吐量大并行度高

容易实现复杂数据和控制

结构

无副作用容易变换数据结构

时间损失在等待非必需的不支持局部状态改变的对

效率较低

自变量上象共享

缺点程序设计困难控制开销大

传播需求令牌需要时间

难以避免运行时错误难以变换数据结构

r

彳Back

，东第9章数据流计算机系统结构

9.2计算模型分类

计算模型在不涉及硬件和软件细节的层次上，描述

计算是如何在计算机中完成的，即要描述一台计算机

能做什么（即能完成什么样的基本动作）、这些动作

何时可以完成以及用何种方式对数据进行读出或写入。

实质上，计算模型是给出了完成计算所需遵循的基本

规则。

，东第9章数据流计算机系统结构

前面提到的SIMD和MIMD代表了两种主要的并行计

算模型。就MIMD模型而言，每个PE（计算单元）从

自己的存储程序中读出指令，形成自己的指令流，而

不是从某一集中的广播源处获得统一的指令。此外，

它可进一步按存储器是为所有PE可直接访问的（共享）

还是为某一PE单独拥有的不同而分为共享和私有存储

器两种模型。上面提及的仅是有关数据机制方面的，

计算模型还必须考虑的另一方面是有关的控制机制。

Treleaven教授把它分为控制驱动、数据驱动、需求驱

动和模式匹配四种类型。这里主要介绍前三种。如表

9.2,给出了按两种数据机制和三种控制机制对并行系

统结构进行分类的情况。

，东第9章数据流计算机系统结构

表9.2计算模型按数据机制和控制机制的分类表

专有存储

共享存储

（消息传递）

控制驱动VonNeumann通信进程

需求驱动图归约串归约

数据驱动数据流I-结构数据流令牌

，东第9章数据流计算机系统结构

为加深对这些基本的计算模型的理解，下面通过一

个简单的计算表达式的例子：

a=(b+2)*(b-c)

来说明在这些基本模型中是如何进行计算的。

，东第9章数据流计算机系统结构

9.2.1控制驱动、共享存储器模型

在这种模型中，操作按事先指定的指令执行序列进

行，主要受PC控制。如图9.3所示的该表达式的求值过

程。

，心第9章数据流计算机系统结构_______________

9.2.2并行控制驱动、共享存储器模型

这是对一般控制驱动模型的改进。使用FORK语句

结构派生出并行任务，使用ii和i2两者并行执行，然后

用JOIN语句结构对它们进行同步。图9.4示出了这种模

型的计算过程。对存储器中的数据访问与图9.3中相同。

数据流计算机系统结构

图9.3串行控制驱动、共享存储器模型

数据流计算机系统结构

图9.4并行控制驱动、共享存储器模型

―东第9章数据流计算机系统结构

9.2.3数据驱动模型

12

图9.5数据驱动模型

，心第9章数据流计算机系统结构_________________

在这种模型中，操作按数据相关和资源可用性所确

定的序列来进行。当一条指令所需的操作数（数据令

牌）全部到达，且有可用的计算资源，便可进行计算。

如图9.5所示，当数据令牌4和2到达i］和i2后，i］和i2两条

指令便可异步并行执行，执行结果将分别传送到指令

i3,此后i3便可执行，执行结果送往a。

―东第9章数据流计算机系统结构_______________

9.2.4需求驱动模型

在这种模型中，计算的进行是由对该计算结果的需

求而被驱动的。如图9.6中所示，当某一指令(iK)中含

有函数a并试图执行时，指令卜便被挂起，直到所需要

的“葭被满足为止。定义在方框中的“葭以类似的步骤求

值。在串归约计算模型中，每个需求者将得到一个“葭

定义的拷贝，然后自己求值。在图归约模型中，求值只

在第一次需求时进行，由指针可直接获得“屋的值，而

不必每次再去求值“葭。

，东第9章数据流计算机系统结构

ik!(........a........)

串归约：每次拷贝定义

凰归约：指针指向求值结果T武12)

图9.6需求驱动模型

dBack

，心第9章数据流计算机系统结构_________________

9.3数据流程序图和数据流语言

9.3.1数据流程序图

通常用数据流程序图来表示指令级的数据流程

序，它是一种有向图，由多个结点和一些连接它们的

弧组成。这种有向图可以被看成是数据流机器的一种

代表性的机器语言。数据流程序图中的每一个结点用

圆圈表示，认为是一种处理部件，圆圈内的符号或字

母表示一种操作，所以也称操作符。

，东第9章数据流计算机系统结构

弧代表数据令牌在结点间的流向。在数据流机中，

根据这样的数据流程序图，通过一个分配器或分配程

序不断分配适当的处理部件来实现操作符的操作。常

用的结点种类有：

(1)常数产生结点：它没有输入端，只产生常数。如

图9.7(a)所示，激发后输出带常数的令牌。

(2)算逻运算结点：主要包括常用的+、-、*、/、乘

方、开方等算术运算及非、与、或、异或、或非等布

尔逻辑运算。激发后输出带相应操作结果的令牌。

，东第9章数据流计算机系统结构

(3)复制操作结点：如图9.7(b)所示，可以是数据

也可以是控制量的多个复制。数据端以实箭头表示，

控制端以空心箭头表示。如图9.7(c)所示。

(4)判定操作结点：对输入数据(通常是一个或两个)

按某种关系进行判断和比较，如输入数据是否小于、

等于、大于0,两个输入数据的大小比较等。当条件满

足时，将在输出端产生T的控制令牌，否则便产生F的

控制令牌。数据流程序图中在空心箭头弧上流动的就

是这类控制信号。如图9.7(d)所示。

第9章数据流计算机系统结构

(d)判断操作结点

(C)连接操作结点

图9.7常用非控制类操作结点及其激发规则

，东第9章数据流计算机系统结构

(5)控制操作结点：这类结点的特点是其激发(或称

火点)条件中要加上布尔控制端。常用的控制结点有

四种。如图9.8所示。

，东第9章数据流计算机系统结构

(d)归并门控结点

图9.8常用控制类操作结点及其激发规则

，心第9章数据流计算机系统结构_________________

①T门结点：仅当布尔控制端为真、且输入端有数

据令牌时才能激发，然后在输出端产生数据令牌而输

入端的数据令牌消失。

②F门结点：与T门控结点相似，仅当布尔控制端为

假时，才能激发。

，东第9章数据流计算机系统结构

③开关门控结点（SW结点）：有一个数据输入端和

两个数据输出端，根据控制端值的真假确定T输出端或

F输出端带有输入端的数据令牌。

④归并门控结点（MG结点）：有两个数据输入端和

一个数据输出端，根据控制端值的真假在输出端上产

生来自T输入端或F输入端上的数据令牌。

，东第9章数据流计算机系统结构

例9.2用数据流程序图描述如下功能：（具有条件

分支结构）

当x>0日寸，z=x+y；否则z=x-y

解：其数据流程序图如图9.9所示。

例9.3用数据流程序图描述如下功能：（具有循环

结构）

对x进行循环累加，直至超过1000时，z等于x的累加

值

解：其数据流程序图如图9.10所示。

第9章数据流计算机系统结构

图9.9具有条件分支结构的数据流程序图

数据流计算机系统结构

0

图9.10具有循环结构的数据流程序图

，心第9章数据流计算机系统结构_________________

例9.4用数据流程序图等效的活动模片表示如下功

能：(具有顺序结构)

z=(a+b)*(a-b)

解：其数据流程序图如图9.H所示。

第9章数据流计算机系统结构

图9.11计算z=(a+b)*(a-b)的活动模片表示法

，心第9章数据流计算机系统结构_________________

例9.5用数据流程序图等效的活动模片表示如下功

能：（具有条件分支结构）

当x>0时，z=x+y；否则z=x-y

解：数据流程序图等效的活动模片表示如图9.12所

示，对应的数据流程序图如图9.9所示。

第9章数据流计算机系统结构

图9.12图9.9数据流程序图等效的活动模片表示

，心第9章数据流计算机系统结构_______________

例9.6画出求一元二次方程两个实数根的数据流程

序图，基本的运算结点有+、-、*、/和。指出哪些基本

运算操作可以并行执行？如果每个操作结点的执行时

间均为一个时钟周期，则整个计算过程总共需要多少

个时钟周期？

解：可并行执行的基本运算操作如图9.13所示，其

中①与②、③与④、⑤与⑥均可并行工作，但相互之

间因为存在数据相关而不能并行。

其数据流程序图如图9.14所示。如果每个操作结点的

执行时间均为一个时钟周期，则整个计算过程总共需

要8个时钟周期。

，东第9章数据流计算机系统结构

图9.13求一元二次方程根的程序中的数据相关关系

第9章数据流计算机系统结构

图9.14求一元二次方程根的数据流程序图

，东第9章数据流计算机系统结构

9.3.2数据流语言

数据流程序图实际上是数据流机器语言，较直观易

懂，但编程效率低。所以通常流行的是数据流语言。

以前，在数据流计算机上使用的是一种命令式程序设

计语言作为其高级语言的，此时必须研究出将命令式

高级语言程序转换成数据流程序图语言的编译程序。

但是，传统机器上广泛使用的面向过程的命令式语

言缺乏并行性描述，很难表达出数据流控制机制的并

行性。虽然有些语言也扩充了并行描述成分，如

FORTRAN的FORK和JOIN,以及并行PASCAL、Ada

语言等，但其编译过程也还是复杂、低效的。

，东第9章数据流计算机系统结构

目前研制出的比较适合于表述数据流程序的高级语

言主要有单赋值语言和函数程序设计语言。

所谓单赋值语言，是指在程序中每个变量只能赋值

一次，即同一变量在赋值语句的左部只出现一次，不

允许对同一变量进行多次赋值。因此，实际上并没有

传统计算机中的变量的概念，只是一种值名。例如，

一个程序允许出现如下语句序列：

，东第9章数据流计算机系统结构

C=A+B

C=C*D

F=(C-D)/E

则所使用的语言就不是单赋值语言。若这时只允

许把程序写成

C=A+B

C1=C*D

F=(C1-D)/E

―东第9章数据流计算机系统结构_________________

其所用的语言就体现出单赋值的规则和要求了。

单赋值语言的语义清楚，程序中的并行性易于被编译

程序所开发。

常用的数据流语言有美国的ID和VAL、法国的LAU

以及英国曼彻斯特大学的SISAL语言等，它们大都是

单赋值语言。

dBackJ

，东第9章数据流计算机系统结构

9.4数据流机的基本结构

9.4.1静态数据流机

这种数据流机的主要特点是数据令牌不带任何标

号，在任何一条弧上只允许存在一个数据令牌。数据

令牌沿数据流图的箭头方向流动，当到达某一结点

时，能否激发该结点进行相应的操作，要视该结点其

它输入弧上是否都已有数据令牌到达。仅当该结点的

所有输入弧上都出现有数据令牌且在它的任何输出弧

上没有令牌时，它才会被激发。

，东第9章数据流计算机系统结构

典型的静态数据流机的结构如图9.15所示。指令存

储部件中存放要执行的数据流程序，所有已收到全部

所需数据令牌的指令将由取指令部件按更新部件送来

的指令地址逐个取出，送到可执行的指令队列中。此

时若有空闲处理机，分派程序将按先后次序分配处理

机给等待执行的指令，使它们并发执行。执行后的结

果将形成新的数据令牌，它们被送到更新部件中，由

后者按它们的目的地址送往指令存储部件内相应指令

的有关位置。与此同时，更新部件将已收到所有必需

数据令牌的指令地址传送给取指令部件。如此反复。

，东第9章数据流计算机系统结构

图9.15静态数据流机的结构

，东第9章数据流计算机系统结构

由于静态数据流机只允许任何一条弧线上有一个数

据令牌，因此它只能处理一般循环操作。为了满足迭

代要求，它必须多次重复激活某些操作结点，此外还

必须设置控制令牌以识别属不同迭代层次的数据令

牌，当数据令牌从输出弧上取走时，这些控制令牌就

作为确认信号告诉所有输入弧上已到齐数据令牌的结

点可以开始执行操作。

MIT的J.B.Dennis等人是数据流计算机研究的开拓

者，是他们提出了MIT静态数据流计算机系统，图9.16

是MIT静态数据流机的主体结构框图。

第9章数据流计算机系统结构

处理部件PS

处金高J

数

据

令

牌

—

控

▼▼…1制

分配网络令

牌

DH

存贮部件MS

图9.16MIT静态数据流机的主体结构

―东第9章数据流计算机系统结构_______________

由图9.16可知，整个系统是由存贮部件、处理部件、

仲裁网络、控制网络、分配网络五大部分组成的一个

流水线环状结构。采用包传输方式异步通信。

存贮部件MS(MemorySection)由若干指令单元组成。

每个指令单元保存数据流程序中的一条指令。它与数

据流程序图中的结点对应且由唯一的地址所指明。指

令单元由若干个存储器字组成，包括一个指令操作码、

相应的一个或两个操作数空位和目的的地址等几部

分，以及用于寄存指令操作数的3个寄存器。

，东第9章数据流计算机系统结构

处理部件PS(ProcessingSection)由对数据值进行基本

运算的多个处理单元PU组成，可以并发执行已被激活

的指令所要求的操作。

仲裁网络AN(ArbitrationNetwork)将可执行的操作包

(operationpackets)由存贮部件发送到处理部件。同时允

许有多个操作包在多个通路上传送。

控制网络CN(ControlNetwork)将控制令牌由处理部

件发送到存贮部件相应的指令单元中。

分配网络DN(DistributionNetwork)将处理部件产生

的多个结果数据令牌依据其各自的目的地址分别传送

到存贮部件相应的指令单元中去。

，东第9章数据流计算机系统结构

9.4.2动态数据流机

动态数据流机的主要特点是使数据令牌带有标号。

这样就可使数据流程序图中的任一条弧上同时存在带

有不同标号（或称颜色）的数据令牌。此时，不需要

像静态数据流机中那样依赖控制令牌来确认指令间数

据令牌的传送，而只要对令牌标号进行符合比较就可

加以识别。为此，需要有一个称为匹配部件的硬件结

构将标号附加到数据令牌上，并完成标号的匹配工作。

典型的动态数据流机的结构如图9.17所示。

第9章数据流计算机系统结构

匹配的令牌蛆

匹配部件

处理部件已

（多个处理器）Y

图9.17动态数据流机的结构框图

，心第9章数据流计算机系统结构_________________

匹配部件将处理部件中各处理单元送来的结果数据

令牌赋予相应的标号，并将流向同一指令的数据令牌

匹配成对或组，然后将它们送往更新/取指令部件，由

该部件将需要它们的指令从指令存储器中取出，然后

将已收到的数据令牌组和取出的指令合并成一条可执

行的指令，送入可执行指令队列。由于在动态数据流

机中给数据令牌赋予标号，从而可区分出不同层次的

迭代执行。因此动态数据流机可最大限度地开发数据

流程序图中并行性。

，心第9章数据流计算机系统结构_________________

动态数据流计算机可有网络型和环型等不同的组成

形式。网络型的典型代表是MIT动态数据流机。MIT的

动态数据流机研制的目的是寻求一种便于用VLSI电路

实现的、高效并发执行高级语言的多处理器系统。ID

程序设计语言就是专为这台机器研制的。

，东第9章数据流计算机系统结构

MIT动态数据流机由N个处理单元PE和一个用于实

现PE间通信的NXN的包交换开关网络组成，如图9.18

所示。每个PE基本上是一台完整的处理机。包括有自

己的程序/数据存储器、I—结构存储器、标记匹配部件、

算术逻辑部件、打标记和对标记特征控制的部件及其

它硬件。NXN的包交换开关网络为令牌提供从发出它

的PEj到吸收它的PEj通路。如果吸收令牌的PE就是发

出此令牌的PE,则不经开关网络传送。

，心第9章数据流计算机系统结构_________________

MIT动态数据流机指令的一般格式如图9.19所示。

其中，op是操作码，nc是存放在本指令中的常数个数

（最多不超过2个），nd指明操作结果送往目的地的个

数。每个目的地由s、p、nt、af等4个字段标识组成。

其中，s指明目的地地址，p指明用于目的地指令的第n

个输入端，nt指明激活目的地指令所需要的令牌数，

而af指明用于选择执行目的地指令的PE是哪一个的赋

值函数。cl、c2是依附于该指令的常数。

第9章数据流计算机系统结构

图9.18MIT动态数据流机结构

，心第9章数据流计算机系统结构_________________