[科普中国]-数据流结构

概述

数据流结构可以用由节点和连接节点的有向弧组成的数据流图来表示，节点代表执行的运算或功能，有向弧代表节点被执行的次序，通常，数据流结构用一个五元组(N，A，V，v0，f)来描述。其中:N={n1，n2，…，nM}是节点的集合，A={a1，a2，…，al}∈N×N是节点之间弧的集合;V={v1，v2…，vL}∈V1×V2×…×VL是弧所代表的数值的集合，vi∈Vi是弧ai代表的数值;v0∈V是弧的初始值;f=定义了各个节点ni∈N实现的功能，I(ni)和O(ni)分别是节点ni∈N上入弧和出弧代表的数值。

数据流结构直观地表达了数学公式，非常适用于描述计算密集的系统。在硬件实现时，为了提高系统的吞吐率往往运用流水线技术，相连的各个节点之间用寄存器或先入先出(FIFO)队列连接。在数字视频信号、数字电视信号以及高速无线传输码流处理器中，待处理的码流具有不同的速率和处理要求。为了适应不同速率和不同结构的码流，对应的数据流结构必须可以动态地改变结构，即处理节点间的连接关系必须是可变的。同时，由于各个节点完成的功能不同，其处理速度也有差异，必须用足够大的FIFO来衔接不同处理速度的节点。由于FIFO的大小会直接影响到最后硬件实现数据流结构的面积和功耗，在设计阶段需要对数据流结构的处理时序进行动态模拟，以此确定在保证处理性能前提下FIFO的最佳大小。1

数据流结构化设计其主要的目标是将软件设计为多个结构合理、功能单一的模块，从而形成系统的模块结构图。这主要是将分层次的结构图作为一种主要的表示方式。

数据流结构不需传统的程序记数器，也不要从存贮器取指令。这种结构的系统中流动着带有标记的数据，每个数据都包括了足够的信息，说明必须对它进行的处理内容。每项数据是个32位的令牌，其中有16位工作数据、4位控制区、7位识别标志(它还告诉处理机该数据的用途)、4位处理机字和1位冗余位。控制区含有区分16位工作数据类别的信息。这个数据可以是象素信息，也可以是控制功能，例如来自宿主机的程序指令。一旦这个32位令牌到达了指定的处理机，它的识别标志区域就不甩了，这个部分可作为另一个4位域使用。

随着数据在处理机内从一个结点流到另一个结点，该数据的拷贝在不同的结点上也在被并行地处理这样就缩短了对指令序列中后续处理步骤的硬件无效等待时间。数据在一个系统结点上完成一次运算后，就流到下一个结点；第一个结点就可以处理后面的数据项。

这种数据流结构的主要优点是省去了通用数据总线，传统结构中的这条总线一直被取指令和其他系统操作数据占用着。2

数据流结构类型将数据流图转化为软件的结构，就需要DFD（数据流图）类型的研究。而由于软件系统是复杂庞大的，就需要人工智能软件的加入。数据流类型主要可分为变换型和事务型。

变换型数据流图这主要是由输入、变换、输出组成。如图。变换型数据处理的工作其可以分为三个步骤，第一步是取得数据，第二步是变换数据，第三步是给出数据，这是DFD的基本思想。变换是系统的主加工，变换输入端的数据流是系统的逻辑输入，输出端为逻辑输出。3

事务型数据流图对输入流分离成许多发散的数据流，通过某个加工形成许多路径，并根据输入值来选择一条路径进行执行，这种特征的DFD是事务型的数据流图，这个加工可以称为事务处理中心，如图所示。3

PetriNets模型PetriNets是结构化、可视化的建模方法，是一个模型化的工具，它用于模型化某一类问题，即有并行事件的离散事件的系统的问题，特别是系统内事件和条件间的关系，有效地描述制造系统资源冲突、死锁、缓冲区容量等问题。目前，PetriNets在硬件设计中的运用研究主要集中于异步数字电路的设计综合，以及对系统的性能评估等领域。

PetriNets一般用来建立系统的控制模型，而数据流结构的PetriNets模型并不是系统的计算模型，不能用来验证数据流结构的功能。该模型只是数据流结构的时序模型，主要描述数据流结构中各模块的状态变化。通过数据流结构PetriNets模型的执行，数据流结构中各模块在实际运行中的状态可以得到模拟，以此来帮助优化数据流结构设计。数据流结构的硬件实现可以分为以下5种基本模块:

(1)2个节点通过寄存器连接。

(2)2个节点通过FIFO连接。

(3)节点具有流水线计算能力

(4)2个数据流汇聚到1个节点。

(5)1个节点分叉出2个数据流。

目前给出了对应着5种基本模块的PetriNets模型。在这些基本模块的PetriNets模型中，处理节点映射为PetriNets的变迁，连接寄存器或FIFO映射为PetriNets的位置，数据流映射为PetriNets的令牌。利用这5种基本模型可以构建任意复杂的具有固定组成的数据流结构。对于可变的数据流结构，提出了一种称为Prophid的结构。该结构由一个协处理器阵列、一个可编程切换矩阵和一个全局控制器组成。协处理器阵列中任意一个处理单元的输出FIFO通过可编程切换矩阵可以连接至协处理器阵列中其他各个处理单元的输入FIFO，全局控制器控制可编程切换矩阵，改变协处理器的连接关系，从而实现可变结构的数据流结构。实际上，这种数据流结构更像一种数据流结构和控制器的混合体。

Prophid结构比较规则，易于硬件实现，但是需要一个额外的控制器模型。在模拟阶段对于具有确定变化的可变数据流结构可以通过适当的激发延时来实现，大大简化了模型的建立过程，而模型的时序特征却基本保持不变。

图所示为一个可变的数据流结构，图a为在t0时刻节点A和节点B相连，在t1时刻节点C和节点B相连。图b所示为在Prophid结构中，节点A，节点B，节点C之间连接关系的改变是通过控制器控制一个2选1选择器来实现的.图c为在简化的PetriNets模型中，位置P0代表节点A的输出FIFO，位置P1代表节点C的输出FIFO，位置P2代表节点B的输入FIFO，迁移T0的延时为0，迁移T1的延时为(t1-t0)，在模拟时由于T1延时激发，令牌的迁移路径和时序与根据图b建立的PetriNets模型相同。1

软件数据流结构设计实例对于销售管理系统，其数据流图转化为软件结构。就其分层图来看可以清晰地表明其所具有的四个主要功能：订货处理、进货处理、缺货处理和销售统计，这四个都可以进行平行处理。所以从整体上分析根据事务类型数据流图进行设计，并利用功能来对四个处理选择。

“蓝牙”是近年来短距无线互连较为标准的一种方式，这主要是利用较为低端的数据通信及语音传输场合，Bluetooth这是在2.4GHz的开放频段来进行工作，这也较为容易受到其他的使用该频段的无线设备干扰。无线传输的数据往往会含有前向差错控制编码、循环冗余码编码等差错控制技术。蓝牙还采用了跳频技术。这也使得结构极其复杂。

通过建立人工智能软件，可以更好的对不同的数据包进行动态模拟的打包过程，来使得Bluetooth打包器在数据流结构设计上得到更好的优化。

数据流结构设计其在早期对软件进行精化，可以利用不同的软件结构导出实现，再通过评价和比较，从而得到较好的结果，这种优化，其是将软件结构设计和过程设计有效的分开。人工智能软件的使用，使得软件结构可以在没有时间的影响因素下更好的开发和精化；还可以在详细设计阶段将一些较为耗费时间的模块进行仔细的设计、处理，以求在效率上得到提高；利用高级程序设计语言来进行程序的编写；利用人工智能软件可以将大量的占用处理机资源孤立出来。3