硬件算法之数据流机

1 数据流机简介

        冯诺依曼架构是当今主流的计算机架构，他从程序计数器所指向的指令存储器地址读取指令并执行，而数据流机是一租只要输入数据就能进行运算的非冯诺依曼架构。冯诺依曼架构计算机必须从指令存储器读取指令，这也是其本质上的性能瓶颈所在，而数据流机则不存在这个问题。相对于冯诺依曼架构一边从存储器读取指令和数据一边运算的形式，数据流机只需要将数据单方向流过硬件即可完成运算。

        数据流机将对象程序转化为数据流图后执行处理。下图列出了数据流图中使用的数据流节点类型：

        Fork为数据幅值；Primitive Operation按描述进行算术运算并输出结果；Branch根据条件信号的值（T或F）控制数据的流向分支；Merge则根据条件信号的值选择输入数据并输出。

        下图给出了数据流图：

        图中的“〇”表示运算中传递的数据，被称为“令牌”。这里令牌所包含的数字代表该处数据的数值。首先，当加法器的两个输入令牌都准备好时运算开始。其次，加法器运算的结果作为令牌输出。然后，乘法器和减法器的输入令牌都到位后运算开始。像这样，用数据流图表示程序就可以清晰地发现数据的并行性。

        和冯诺依曼架构计算机一样，数据流机也可以实现条件分支和循环。下图左边为分支示例。分支基于Branch节点和Merge节点实现。当令牌到来时，先执行Branch节点再将结果送入运算节点。Merge节点对条件进行判断，条件为真时输出令牌T，条件为假时输出令牌F。下图为右边循环示例：

        循环通过不断更新Merge节点的初始值，在退出循环条件满足前由Branch节点控制不断重复运算来实现。数据流机中的循环有两种实现方式：一种是将循环完全展开，全部以数据流的方式实现，成为静态数据流机；另一种是只实现循环体的数据流，之后的循环复用同一组硬件的动态数据流机。静态数据流机是比较直接的数据驱动处理方式，但多数情况下数据流图的规模会变得十分庞大，鉴于现实中数据流机有限的硬件资源，这个方式很难实现。而另一方面，动态数据流机为了复用循环体内的运算器，需要设置额外的控制电路，否则如果发生循环间令牌混乱的情况就难以保证计算结果的正确性。例如在以上两个图所示的循环中，如果y在x更新前改变的话就无法得到预期的运算结果。

        在动态数据流机中，为了区别各次循环中的令牌，可以为令牌加上标号，这被称为带标号令牌方式，也可以按颜色区分令牌，这被称为有色令牌方式。将令牌用标号区分后就可以对持有相同标号的令牌进行运算，从而保证结果的正确性。

2 静态数据流机

        静态数据流机经常用于节点的运算功能和运算数混合存在的场合。MIT的Dennis等人提出的数据流机中，数据流图的节点可通过运算种类，运算数以及存放结果的目的单元等信息进行定制，这些信息以令牌包的形式传入节点。不过因为令牌不带有标号，因此只能处理不包含循环的静态数据流图。下图展示了静态数据流机架构的硬件框图和各个命令单元的结构。其中，左边的指令单元用来保存上述节点信息，静态数据流机中含有有效信息的全部指令单元联合组成了所要实现的目标数据流图。

        下面对运算处理的过程进行说明。假设某个指令单元的运算数已准备好，指令单元会通过ANET发出操作包，其中包含了运算类型、运算数和存放结果的目的单元信息。运算结果以数据令牌的形式通过DNET传输到目的单元（指令单元图中的d1和d2），并写入指定指令单元内的运算数部分。然后继续重复这个过程就可以实现一连串的数据驱动运算。

2 动态数据流机

        动态数据流机经常用于节点的运算功能和运算数分离的场合。这种方式的优势是数据流图和实际的数据分离，可以采用带标号令牌实现循环处理。MIT的Arind等人所提出的动态数据流机如下图中的整体架构所示，由N个PE和一个N×N的连接网络组成。下图中的指令格式里，常数1和常数2代表常数的存储位置，存储位置的信息由s、p、nt、af四个参数决定。而实际的运算数据则由数据令牌表示，即程序（数据流图）和数据是完全分离的。数据令牌由存储位置的指令的状态编号、标号（颜色）、储存位置指令的输入端口编号，以及存储位置指令的运算数组成。在动态数据流机中，即便是相同的数据流图处理的数据，根据控制标号的编变化就可以实现循环处理。

        PE的结构如上图所示，其运算流程如下：

• 输入模块从连接网络或自身的输出接收数据令牌；
• 等待模块利用数据令牌中的状态编号和标号信息，在运算存储器中进行相连检索判断运算所需的全部运算数是否都已准备好，根据相连检索就可以知道运算所需的运算数是否都已到位；
• 如果运算所需的运算数全部准备就绪，接下来取指令的模块利用存储位置指令的状态编号，从指令存储器读取运算信息，同时将新输入的运算数和之前输入的运算数分别从等待模块和运算数存储器中读取出来，这样运算所需的全部信息就都准备好了；
• 在ALU中进行运算并将结果根据存储位置指令的信息以数据令牌的形式输出，这样就完成了PE运算的一连串动作。

        此外，I结构是一个位数组等简单数据结构提供等待功能的模块。在按数据驱动方式处理数组访问时，可能会有数组元素在生成之前就被请求读取的情况发生。为了保证数据再写入之后再被读取，需要对每个元素设置一个存在标志位（presence bit），标志位值为1时表示数据已写入，为0时表示数据还未写入。这样，在数据读取时如果标志位值为0.就会一直等待到该值被写入后再继续运算。这种做法可以在硬件层面保证数据访问的同步性。

3 Petri网

        数据流机是基于表示系统状态的图来实现的，此外还有一种表示信号输入/输出的图，成为Petri网。信号转换图（Signal Transition Graph，STG）是Petri网的一个子类，通常被用来描述并行系统和异步系统。

        Petri网由库所（Place）和变迁（transition）两类节点以及有向弧组成的二分图。此处我们用记号〇表示库所，用记号━表示变迁。使用Petri网描述系统时，系统的状态或条件用库所表示，系统状态迁移的发生和完成等事件用变迁表示。这样，库所→变迁的有向弧表示现象的发生及其前提条件，变迁→库所的有向弧表示事件发生后的状态以及和成立条件的关系。此外，可以在库所内使用记号●来描述令牌，并可按照Petri网的规则移动，以此来描述系统的行为。

        我们可以用Petri网来表示数据流机的行为，假设一个数据流图如下图所示：

        上图中的数据流图可以用下图所示的方式表示：

        首先将令牌放在输入数据所对应的库所处，用来表示数据的输入。代表运算的变迁发生（fire）的条件是连接在变迁的全部输入中至少存在一个令牌。变迁发生后，输出库所产生一个令牌。这样，我们就可以使用Petri网清晰的描述数据流机及其行为。

        告辞。