[科普中国]-数据流计算机

数据流计算机是一种数据驱动方式系统结构的计算机，只有当一条或一组指令所需的操作数全部准备好时，才能激发相应指令的一次执行，执行结果又流向等待这一数据的下一条或一组指令，以驱动该条或该组指令的执行。因此，程序中各条指令的执行顺序仅仅是由指令间的数据依赖关系决定的。1

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

1．静态数据流机

静态数据流机的数据令牌没加标号。为正确工作，任意给定时刻，当结点操作时，其任何一条输入弧上只能有一个数据令牌。只有当结点的所有输入弧上都有数据令牌时，该结点才被激活，执行相应的操作。由于数据令牌没有加标号，如果给定时间里允许一条弧上同时出现两个以上的数据令牌的话，结点对于送达各输入端的一批数据就无法区分出它们中哪些是属于同一批的操作数。因此，在静态数据流机中，为了满足迭代要求，除要多次重复激活同一操作结点外，还必须另设控制令牌，以识别数据令牌由一个结点传送到另一个结点的时间关系，从而区分属于不同迭代层次的各批数据。所以，静态数据流机不支持递归的并发激活，只支持一般的循环。

2．动态数据流机

动态数据流机最主要的特点是让令牌带上标记，使得在任意给定时刻，数据流程序图任何一条弧上允许出现多个带不同标记的令牌。令牌的标记是令牌附带的一个能识别该令牌时间先后相对关系的标号，有的机器上也称其为颜色。所以，动态数据流机不需要像静态数据流机那样用控制令牌来对指令间数据令牌的传送加以认可。对于需要多组(次)数据令牌的指令，可以通过对令牌标记的配对来识别。为此，需要相应硬件将标记附加到数据令牌上，并完成对标记的匹配工作。2

原理数据流计算机结构中是以“数据驱动”方式启动指令的执行。按照这种方式，程序中任一条指令只要所需的操作数已经全部齐备，且有可使用的计算资源就可立即启动执行(称为点火)。指令的运算结果又可作为下一条指令的操作数驱动该指令的点火执行。这就是“数据驱动”的含义。

在数据流计算机模型中不存在共享数据，一条指令执行后结果数据不送存储器保存，而是直接流向需要该结果的指令，作为新的操作数供下一条指令使用，每个操作数经过指令的一次使用后便消失。如果若干条指令要求使用相同的数据，那么就需要事先复制该数据，分别供多条指令使用。

数据流计算机中也不存在指令计数器。指令得以启动执行的时机取决于操作数具备与否。程序中各条指令的执行顺序仅仅由指令间的数据依赖关系决定。因此，数据流计算机中指令的执行是异步并发进行的。在数据流程序中，由于“数据驱动”要求每条指令标明其运算结果的流向，也就是指向将本指令的运算结果作为操作数的那条目标指令。因此数据流程序中只有一条链路，即各条指令中指向目标指令的指针。

在数据流计算机中，没有变量的概念，也不设置状态，在指令间直接传送数据，操作数直接以“令牌”(token)或“数值”的记号传递而不是作为“地址”变量加以访问。因此操作结果不产生副作用，也不改变机器状态，从而具有纯函数的特点。所有数据流计算机通常与函数语言有密切的关系。3

指令组成数据流计算机的指令主要由数据令牌和操作包(operation packet)两部分组成。

1．数据令牌

数据令牌用以传送数据并激活指令，每个数据令牌由两部分组成：结果数据和目标地址。结果数据就是一条指令执行的结果，是数据令牌携带的内容。目标地址即使用该结果的数据。这是数据流计算机工作的一个重要特征：数据由数据令牌携带，在指令问直接传送。当一条指令的所有数据令牌均到达时，该指令即被激活，可开始执行。因此数据令牌中还应含有各种标志和特征等。

2．操作包

操作包由操作码(operation code)、一个或几个源操作数(source data)以及零个或多个后继指令地址(next address)组成。后继指令地址用于和结果数据组成使用结果数据的后继指令的数据令牌，如果一条指令的运算结果要送几个目的地址，则分别形成几个数据令牌。4

特点1、优点

数据流计算机在许多方面的性能优于传统的冯·诺依曼型计算机。下面就这个领域里的研究人员们提出的优点进行归纳总结，其中的一部分已得到模拟实验的验证。

1)高度并行运算

数据流方法本身就体现了操作的高度并行性。它不仅能开发程序中有规则的并行性，还能开发程序中任意的并行性。

在数据流方法中，由于没有指令执行顺序的限制。从理论上来讲，只要硬件资源充分就能获得最大的并行性。已经通过程序验证，许多问题的加速倍数随处理机数目的增加

而线性的增长。

2)流水线异步操作

由于在指令中直接使用数值本身，而不是使用存放数值的地址，从而能实现无副作用的纯函数型程序设计方法，可以在过程级及指令级充分开发异步并行性，可以把实际串行的问题用简单的办法展开成并行问题计算。例如，把一个循环程序的几个相邻循环体同时展开，把体内、体间本来相关的操作数直接互相替代，形成一条异步流水线，使不同次的循环体能并行执行。

数据流方法已广泛的应用于流水线处理、数组处理及多重循环处理中。

3)与VI。SI技术相适应

虽然数据流计算机的结构比较复杂，但是它的基本组成具有模块性和均匀性，其中的指令存储器、数据令牌缓冲器及可执行指令队列缓冲器等存储部件，可以用VLSI存储阵列均匀的构成。处理部件及信息包开关网络也可以分别用模块化的标准单元有规则的连接而成。因此，有可能研制出具有更高性能价格比的计算机系统。

4)有利于提高软件生产能力

在传统语言如FORTRAN，Pascal等语言中，由于大量使用全局变量和同义名变量而产生副作用，给软件的生产和调试带来很多困难。而在数据流计算机中，执行的是纯函数操作，使用函数程序设计语言来编程，从含义上取消了“变量”，取消了变量赋值机制。因而消除了巴科斯所说的冯·诺依曼赋值操作的瓶颈。

用函数语言编写的程序符合程序设计方法学的要求，易读易懂。它良好的程序结构为程序的调试和验证提供了很好的基础。总之，数据流技术改善了软件研制环境，有可能提高软件的生产能力和可靠性。

2、缺点

数据流技术的反对者们指出的数据流计算机在指令级并行性上有许多潜在问题。确切的来说，上述这些数据流技术的优点实际上只是理论化的数据流计算机模型才具备的。实际的数据流计算机为获得这些优点往往要付出巨大的代价，从而使得实际的数据流计算机具有许多明显的不足之处。

1)操作开销过大

与传统的计算机相比，数据流计算机中各种操作的开销要大得多，以至于使所获得的并行度在相当广泛的实际应用领域里得不到补偿。

数据流计算机中的每条指令除了包含操作码之外，还要提供两个操作数存储单元及存放多个后继指令地址的存储单元。所以，数据流计算机的每条指令都很长。这不仅要占用较多的存储单元，还使指令的存取复杂且费时间。

数据流计算机中有大量中间结果形成的数据令牌在系统中流动，使信息的流动相当频繁，冲突增加。为减小冲突，要设置许多局部缓冲器，这样不仅增加了开销，也延长了通信途径。

数据流计算机操作开销大的根本原因是把并行性完全放在指令级上。在一个实际的计算机系统中，并行可分为多级，如任务级、作业级、进程级、过程级、函数级和指令级等。

如果不适当地把高一级的并行性都依赖低级的并行性实现，往往要付出过高的代价。如已经相当成熟的数组运算就是一例。

操作开销大的另一个原因是完全采用异步操作，没有集中控制。为解决这些异步操作和随即调度引起的混乱，需要花费大量的操作开销。

2)不能有效利用传统计算机的研究成果

数据流计算机完全放弃了传统计算机的结构，独树一帜，这样做一方面摆脱了传统结构的束缚，具有活跃的生命力；另一方面它不能吸取传统计算机已经证明行之有效的许多研究成果。

另外，数据流计算机企图摆脱困扰多机系统的许多问题，如存储器按模块访问引起的冲突、复杂昂贵的互连网络、多进程之间的同步与通信等，但是在实际中往往又以新的形式回到这些老问题上。所以在数据流计算机的设计中认真吸取传统计算机的研究成果是非常有益的。

在软件方面，由于采用全新的函数语言，人类已经长期积累的大量软件成果不能继承。这一基本问题如果不解决，数据流计算机将无法进入市场，无法与传统的计算机竞争。

3)数据流语言尚不完善

已经见到的数据流语言，如VAL及ID等都不完善，输入输出操作因为不是函数运算至今未被引入到数据流语言中来。另外，数据流语言以隐含的方式描述并行性，而由编译器开发这种并行成分，但这种方式并非总是有效。因此，数据流语言还需要进一步不断地改进和完善。

在数据流程序中由于引入了大量隐含的并行性，使得程序的调试工作变得非常困难。还没有一种好的解决办法。另外，对数据流计算机操作系统的研究还很少，在这一方面的研究还很不成熟。3

存在问题数据流计算机在提高并行处理效能上有着非常显著的长处，但也存在一些问题。

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

(2)在数据流机中为给数据建立、识别、处理标记，需要花费较多的辅助开销和较大的存储空间(可能比Neumann型的要大出2～3倍)，但如果不用标记则无法递归并会降低并行能力。

(3)数据流机不保存数组。在处理大型数组时，数据流机会因复制数组造成存储空间的大量浪费，增加额外数据传输开销。数据流机对标量运算有利，而对数组、递归及其他高级操作较难管理。

(4)数据流语言的变量代表数值而不是存储单元位置，使程序员无法控制存储分配。为有效回收不用的存储单元，编译程序的难度将增大。

(5)数据流机互连网络设计困难，输入/输出系统仍不够完善。

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

因此，数据流机尚难批量生产，仍需进一步改进。就发展来看，数据流机是有很大潜力的，在并行度低的小型机及需要高度并行的超级机上有潜在的发展余地，但在中型的并行机上可能较难使用。2

进展随着数据流机研制的深人开展，已提出若干新的数据流机器，它们既继承了传统计算机采用的并行处理技术，又弥补了经典数据流机的一些缺陷。

1．采用提高并行度等级的数据流机

由于经典的数据流机将数据流级的并行性放在指令级上，致使机器的操作开销大；现在将并行性级别提高到函数或复合函数一级上，用数据来直接驱动函数或复合函数，就可以较大地减少总的操作开销。1981年Motooka等人及1982年Gajks等人提出复合函数级驱动方式，在全操作循环、流水线循环、赋值语句、复合条件语句、数组向量运算及线性递归计算上采用复合函数级的并行。这样，就可以用传统高级语言来编写程序，只是需要研制专门的程序转换软件，实现将传统高级语言编制的程序转换成复合函数级的数据流程图，并生成相应的机器码。

2．采用同步、异步结合的数据流机

由于数据流机采用完全的异步操作，尤其是指令级的异步会造成系统操作开销的增大。所以，在指令级上适当采用同步操作，而在函数级及函数级之上采用异步操作，就可以减少机器的操作开销。

指令级同步操作可以使中间结果不必存回存储器，直接被下一操作所用，指令中就不需要目标地址了，这样可缩短指令字长。指令级同步操作不需要回答信号，减少了系统的通信量，系统采用总线互连即可，简化了结构。虽然函数级并行异步的开销较大，例如取函数标题、取程序要多花费些时间，互连标题也还要多占用存储空间，但这些开销分摊到函数中的每条指令就少得多了。

3．采用控制流与数据流相结合的数据流机

控制流与数据流相结合，可以继承传统控制流计算机的优点。例如，Cedar数据流机就实现了函数级宏流水线，其指令级上仍采用控制流方式，如控制流计算机中的向量处理技术，用FORTRAN语言，经编译开发程序的并行性技术，照样可以使用。2

本词条内容贡献者为:

王沛 - 副教授、副研究员 - 中国科学院工程热物理研究所