基于动态数据流的粗粒度可重构阵列设计

吴昊

（上海交通大学，上海200240）

0 引言

随着信息化社会的不断发展，涌现了大批以大量数据处理为主导的算法，例如机器学习和神经网络，这些算法对处理器的性能有非常高的需求，并要求且处理器能够提高较高程度的灵活型以适应不断变换的算法需求。通用处理器难以支持如此庞大的算力，专用处理器虽然能够实现很高的加速比但是针对特定的算法而设计，不具备灵活支持多种算法的能力，因此粗粒度可重构阵列[1]成为了当下研究的热点。

粗粒度可重构阵列由阵列控制器、大量的处理单元（Process Element，PE）及互联资源构成，处理单元的功能及处理单元之间的互联结构均可以根据算法的需求重构，在利用空间计算提升执行效率的同时还能够获得较高的灵活性。但是阵列中如此多的处理单元往往很难被充分的利用，受到长延迟操作、数据依赖关系等诸多因素的制约，因此提高处理单元的利用率是粗粒度可重构阵列研究中的重要问题，也是提升整体性能的关键。

现有粗粒度可重构阵大多基于配置流驱动[2]，虽然能够通过指令级并行的方式提升对处理单元的利用率，但是其控制代价也非常高的昂，在阵列运行中频繁的切换配置带来了很高的功耗，并且需要更多的片上存储保存指令，增加了阵列的面积。因此，本文基于动态数据流[3]的执行方式设计粗粒度可重构阵列，通过解决阵列中的长延迟操作以提升阵列中处理单元的利用率，从而提高阵列的流水频率，最终达到提升阵列整体性能的目的。

1 设计思路

动态数据流能够有效地隐藏长延迟操作带来的性能损失，其核心思想是让阵列在进行长延迟操作时优先处理后续的数据。例如当阵列运行中出现对片外存储器的访问时，可以继续从缓存中提取后续将要访问的数据并优先执行后续的操作。除此之外，一些虚拟流水化操作也可以用动态数据流的方式加速，例如虚拟流水化的除法器，实际上是通过多个除法单元并行工作的方式模拟流水化执行，因为除法操作的延迟与数据相关，所以当长延迟操作发生时，阵列可以优先处理后续的短延迟操作。

动态数据流的实现需要阵列中所有的数据都携带标记信息，理想情况下同一次循环迭代中的数据应该具有相同的标记，不同循环迭代的数据应该具有不同的标记。PE需要对操作数的标记进行匹配，如果所有操作数的标记相同则激活ALU执行运算，否则等待操作数的匹配。匹配过程如图1所示，第2批的数据由于先准备好所以先开始计算，不需要等待第1批的数据完成，有效地利用了处理器的闲置时间。

图1 动态数据流执行图

为了在可重构阵列上实现动态数据流，需要对以下问题进行设计。

（1）交叉匹配问题

由于标记的实现需要额外的布线资源和硬件逻辑，所以标记的数目是受到限制的，一般会通过循环的方式重复利用之前使用过的标记。在这种标记的使用策略下可能会发生交叉匹配的问题，即由于阵列中不同循环迭代间的数据具有了相同的标记，这些不同批次的数据就有可能交叉匹配从而导致阵列计算出错。为了解决这一问题，本设计采用的方案是对PE的输入buffer增加一些限制逻辑，不允许PE的输入buffer中同时存在多个有相同标记的数据。

（2）死锁问题

死锁问题发生在标记的数目大于输入buffer的规模时。如图2所示，由于输入1的buffer和输入2的buffer中均是不同的标记，所以该PE无法完成数据的匹配并激活运算，同时由于两个输入buffer都已经被填满，所以能够匹配的输入无法进入输入buffer，PE一直卡死在这一状态就发生了死锁。为了解决这一问题，需要对标记的数目进行更为严格的限制，当标记的数目等于输入buffer的规模时就可以避免死锁。

图2 死锁示意图

（3）PE间通信机制

在可重构阵列领域有两种基本的通信机制，一种是ACK机制，在这种机制下发送端先发送数据，再根据接收端的反馈信号选择是否清除。另一种是Credit机制[4]，此机制下接收端先提供Credit信号，发送端接收后再发送数据并且直接清除。两种通信机制如图3所示，Credit机制的正确运行基于接收端一定能够接收发送端所发出的每一个数据，但是由于要解决上述交叉匹配问题所以无法满足Credit机制的运行条件，PE必须检测输入数据的标记是否和输入buffer中的有效数据重复，如果发生重复则不能接收该数据。因此，本文采用ACK机制作为阵列内部的通信协议，如果PE检测完成后确认可以接收该数据则向其上级节点反馈ACK信号。

图3 两种通信机制

2 阵列结构设计

2.1 阵列整体结构

阵列的整体结构如图4所示，由阵列控制器、PE阵列和数据存储模块三部分构成。其中阵列控制器负责向PE阵列导入配置，启动阵列的执行并收集阵列的结束信息。PE阵列执行计算任务，阵列内部采取行互联和列互联的结构。数据存储模块中包含片上高速缓存和片外存储两部分，片上缓存的访问代价较低但是容量较小，片外存储容量大但是访存代价很高。阵列的执行过程如下：在任务开始执行前由阵列控制器导入配置并固化互联结构，导入完成后激活阵列执行，当阵列结束后向阵列控制器反馈结束信号，标志任务的结束。由于阵列基于数据流驱动，所以在阵列运行过程中PE的结构及互联均不发生改变，只依靠操作数的匹配激活PE进行运算。这种可重构阵列控制的代价非常低，并且具有更低的功耗。

图4 粗粒度可重构阵列整体结构图

2.2 PE结构设计

PE的内部结构如图5所示，输入输出均是两个数据线加一个控制线，数据线传递操作数而控制线传递布尔信号。PE内部可以划分成三个流水级，输入buf⁃fer对外部输入进行缓冲，ALU执行算术运算，输出buffer保存ALU的计算结果。其中输入buffer的层数和tag的数目相对应以解决死锁问题，并且有专门的匹配电路依据标记对输入buffer中的操作数进行匹配。所有的标记在输入buffer中都有相对应的唯一位置，从而有效的防止了携带相同标记的数据进入buffer。配置寄存器负责接收配置信息并根据配置信息对PE内部的数据通路以及ALU执行的功能进行配置，本地寄存器储存常量数据或者迭代数据。

图5 PE结构图

3 实验结果与分析

为了验证动态数据流对性能的影响，本文设计了C++仿真器对粗粒度可重构阵列进行功能验证和性能仿真。仿真器中包含了阵列模型和存储模型，能够模拟片上缓存的行为以及片外存储的延时。在进行仿真前需要设置一些硬件参数，本次实验采用的参数如表1所示。仿真器的应用过程如下：首先将应用转换成数据流图的表达形式，根据数据流图为阵列中的PE编写配置文件，然后将配置文件作为仿真器的输入并开始执行仿真。仿真的过程中逐周期的访问所有PE，并且按照硬件的时序顺序访问PE内部的每一级流水级。当仿真结束后能够得到阵列的执行周期数。

本文采用广度优先搜索算法进行仿真测试[5]，该算法较为随机的访存特征能够体现动态数据流的优势。输入的图中包含8192个节点以及491520条边，总的数据规模为516097，并且以稀疏化的存储方式组织数据。仿真的结果如图6所示，依据标记数目设置了多组测试以评估动态数据流的性能，仿真结果以标记数目为2时的性能作为基准进行归一化。从图中可以看出，随着标记数目的增加性能有显著的提升，并且随着标记数目增加性能提升的幅度也在不断降低，最终在标记数目等于64时达到了3.12的加速比。发生这一现象的原因是动态数据流对阵列实现加速的同时也对访存模块造成了更大的压力，因此访存模块成为了制约性能提升的瓶颈。

表1 硬件参数表

图6标记数目对性能的影响

4 结语

本文基于动态数据流技术对粗粒度可重构阵列进行设计，首先根据动态数据流的实现原理对PE的功能和PE间的通信方式进行设计，其次对可重构阵列整体结构和PE内部的微架构进行详细的设计。最后，本文设计了C++仿真器对上述架构进行建模，针对广度优先搜索算法进行仿真测试和性能评估，证明了动态数据流的执行机制能够有效的实现性能的提升，并且随着标记数目的增多性能也逐渐提升，直到达到访存的瓶颈。