0 引言

现如今随着可编程逻辑器件的快速发展，可重构计算(Reconfigurable Computing, RC)成为了一种新的计算方式^[1]，这种方式可以通过软件配置结构可变的硬件，故其既具备了软件的通用性、灵活性，又兼具了专用集成电路(Application Specific Integrated Circuit, ASIC)的高性能低功耗的优点。可重构计算凭借其优越性在解决数字信号处理^[2]、多媒体处理^[3]、加解密算法^[4]等资源密集型计算上，成为了一种理想的选择。

在可重构计算的任务编译过程中，由核心循环转换来的数据流图(Data Flow Graph, DFG)如何被映射到可重构处理单元(Reconfigurable Processing Unit, RPU)是实现可重构系统高性能的关键所在^[5]。其中转换来的数据流图的节点表示计算任务，如加法、减法、乘法等，有向边表示节点之间的数据依赖关系^[6]。对于一个计算密集型应用而言，需要的硬件资源往往大于可重构处理单元所能提供的资源。此时需要对任务划分成若干个子任务，分时复用处理单元上提供的硬件资源，这个过程叫作任务的时域划分^[7]。

可重构计算硬件任务的时域划分问题实质就是图的分割问题，已经被证明是一个NP完全问题^[8-9]。目前的研究在并行度、块间通信量、划分块数等影响因素中，往往追求其中一个最优解，而忽略了其他因素的优化对系统的影响^[10]。文献[11]首次针对可重构计算提出了两种任务划分的方法，层划分和簇划分。基于层划分(Level Based Partitioning, LBP)是采用ASAP(As Soon As Possible)策略分层，根据贪心算法来提高各个划分块中节点的并行度，但忽略了操作节点之间的依赖关系，造成划分块之间的通信量增大，并且还产生大量硬件碎片。基于簇的划分(Cluster Based Partitioning, CBP)是基于列表的启发式算法，将数据依赖关系紧密的操作尽可能地划分到同一个块中，以减少划分块之间的通信量，复杂度较低，但是仍然会产生大量的碎片。这两种方法都是针对单一目标的算法，并没有统筹考虑多个因素的影响。文献[12]针对簇划分产生面积碎片问题改进，充分利用硬件面积资源减少了划分块数，但又忽略了块间的通信量。文献[13]提出了一种划分块数最小化的硬件任务划分算法，还考虑了执行总延迟、划分块之间边数等多个因素，有效地减少了可重构系统的配置时间，但随着RPU增大，划分块间的边数增加，延长了通信延迟。文献[14-15]利用基因算法虽然获得较好的划分结果，但是以牺牲执行延迟为代价，不能很好地满足可重构系统的快速划分要求。文献[16]提出了一种并行度最大化的贪婪算法，获得较大并行度，但此算法假设资源没有限制，并没有考虑实际存在的硬件碎片问题。

本文针对执行延迟最小化的任务划分需求，提出了一种基于并行度最大化的多目标优化(Parallelism Maximization with Multi-objective Optimization, PMMO)可重构任务划分算法。采用广度优先的遍历方式，在保证任务划分获得最大的块内并行度下，采取了多种划分策略，提高资源面积的利用率，综合优化了划分块数和块间通信量等因素的影响，在实现并行最大的同时达到一种多目标优化的效果。

1 模型的描述与定义

为了研究任务划分问题，这里给出数据流图和划分问题相关的形式化模型定义。

定义1 一个数据流图可以用G=(V, E, S, L)来表示。节点v_i∈V(1≤i≤n)表示某一具体的运算操作符，有向边e_ij=〈v_i, v_j〉, e_ij∈E表示节点v_i与v_j存在依赖关系，v_i是v_j先驱节点，v_j是v_i的后继节点。在操作符v_j运算之前，操作符v_i必须要先完成运算。当每一个运算符映射到可重构处理单元上时，都要有相应的所需资源面积和执行延迟。用s_i∈S来表示节点v_i的硬件资源面积，S_RPU表示一块可重构处理单元的面积。用l_i∈L来表示节点v_i的执行延迟。

定义2 采用某种划分方法可以得到一种具有k个模块的划分, 表示为P={p₁, p₂, …, p_k}。其中第i个划分块p_i由任务中的若干个节点组成。

定义3 一个任务节点v_i被划分到某一模块时，其所有前驱节点必须已经划分到已完成执行的模块中，否则就会产生不合理的依赖关系。当两个划分模块之间存在着不合理的依赖关系，就是一个不合理的划分。图 1给出了一种划分示例。假设每一个节点操作所需资源相同，即可以用节点数表示所需面积资源。设S_RPU=2，限定图 1(a)的每一个划分块的节点数不能超过2。图 1(b)中的划分块p₂中的有一个节点的前驱节点在p₃中，同时划分块p₃中的有一个节点的前驱节点也在p₂中。无论是按照p₁p₂p₃的顺序执行，还是按照p₁p₃p₂的顺序执行，p₂和p₃之间都产生了不合理的依赖关系，此划分是一个不合理的划分。而图 1(c)中的划分块之间都满足依赖关系，是一个合理的划分，可以按照p₁p₂p₃的顺序执行。

定义4 设B_i是可重构系统对划分模块p_i配置的时间，C_i是p_i与其他模块进行数据通信的时间，D_i是模块p_i内部节点的执行延迟。设划分成k个模块的一个任务在系统中执行所需的总时间记为：

$T = \sum\limits_{i = 1}^k {\left( {{B_i} + {C_i} + {D_i}} \right)} $

(1)

由式(1) 可知，为了使执行总时间最少，就要使模块的配置时间、模块间的通信时间、模块内的执行延迟最小，对应地就要减少划分的模块数、减少模块间的连接边数、增大模块内部节点的执行并行性。

定义5 一个可重构系统的时域划分模型可以描述如下。

输入：G=(V, E, S, L)，S_RPU。

输出：一种划分P={p₁, p₂, …, p_k}。

约束条件：

1) $\bigcap\limits_{i = 1}^k {{p_i}} = \emptyset ;$

2) $\bigcup\limits_{i = 1}^k {{p_i} = V} ;$

3) $\forall {p_i} \in P,1 \leqslant i \leqslant k,\sum\limits_{j = 1}^n {{s_j} \leqslant {S_{{\text{RPU}}}}} $，n为p_i内包含的节点数；

4) 待划分节点的所有前驱节点必须已经划分到已完成执行的模块中。

目标：1) 执行并行度最大化；2) 划分的块数较小化；3) 尽可能减少划分块之间的连接边数。

2 算法设计及分析 2.1 PMMO算法设计

为了保证一个DFG的任务划分获得最小的执行延迟，尽量减少划分块数与块之间的连接边数，PMMO算法在满足RPU硬件面积资源和合理依赖关系的约束下，按广度优先的遍历方式，着重考虑了执行延迟对于系统完成时间的影响，最大化划分块内的并行性，并且优化了资源面积的利用。PMMO算法采取以下策略来进行算法设计。

策略1 保证划分块内的操作并行度最大化。

在满足资源面积和依赖关系的前提下，采用广度优先的原则，优先选择当前层的操作节点进行划分。当遇到不能满足约束条件的节点时跳过，继续查找其后处于就绪状态的节点，当遍历搜索到了满足条件的节点时，还要考虑加入此节点之后的块内执行延迟不能大于当前的块内延迟，这样才能将节点添加到当前的划分块中。当本层的就绪节点搜索完毕时，接着优先考虑所属层号较小的就绪节点。此策略的目的就是使块内操作并行最大化，从而使整个任务的执行延迟最小化。

策略2 在保证策略1的情况下，充分利用可重构处理单元的面积资源。

当有多个节点处于就绪状态且执行延迟相同时，在保证合理划分的要求下，优先选择占用硬件面积资源大的操作节点，使得剩余硬件碎片较小，提高资源的利用率。此外对于队首之后的节点，在满足剩余硬件资源碎片和不增加执行延迟的条件下，贪婪搜索可以将其加入到当前块中，进一步减少硬件碎片。此策略的目的是在块内操作并行性最大化下，充分利用处理单元面积资源，减少硬件碎片，尽可能减少划分的块数。

策略3 在保证策略1的情况下，尽量减少划分块之间的连接边数。

每次将一个节点划分到块中，都要更新当前划分块与就绪节点之间的连接边数，边数越多说明节点与划分块联系越紧密，在满足执行延迟的条件下，尽可能将其划入到块中。此外当有多个就绪节点都满足约束要求时且加入节点后块间的连接边数不大于当前的边数时，优先选择当前块内的后继节点，这样可以使紧密型的操作节点更多地处于同一划分块中。此策略的目的是在操作并行性最大化下，减少划分块之间的边数，降低块间的通信时间。

基于以上3个策略，PMMO算法描述如下。

输入：一个任务的DFG。

输出：一个划分后的DFG、所有划分块的执行延迟总和、划分块数、块间的连接边数总和。

约束：S_RPU、待划分节点的所有前驱节点必须已经划分到已完成执行的模块中。

init();      //初始化节点

level();      //计算每个节点所在层

ready_list();      //就绪节点列表

采用广度优先遍历；

while(rList!=NULL)

 if ((Area_Used+node[v_i].area)＜=S_RPU)

  更新使用面积；

  更新块间的边数；

  更新块内的延迟；

  quickSort();      //选择所属层号较小的节点

 End if;

 if ((area_used+node[v_i].area)>S_RPU)

  跳过该点，搜索后面满足条件的节点；

 End if;

End while;

while(pList!=NULL)

 if ((area_used+node[v_i].area)＜=S_RPU)

  quickSort();      //选择满足条件且所用面积最大的节点

  分别计算当前块和加入新节点之后的边数和延迟；

  if (edges_delt＜=0 & & delays_delt＜=0)

   将该点加入块中，优先选择当前块内的后继节点；

  End if;

 End if;

End while;

得出划分块数;

cal_edges();      //求出划分块间的连接边数

cal_delays();      //求出划分块执行延迟总和

2.2 算法时间复杂度分析

对于一个n个节点的DFG，已知每个运算节点的类型、执行延迟和所用资源数。时间复杂度主要分析算法中使用的函数，初始阶段的init()、level()、ready_list()，过程中的quickSort()，结束阶段的cal_edges()、cal_delays()，综合分析这些函数即可得到整个算法的时间复杂度。

初始化函数init()求得每个节点入度和出度个数、前驱与后继列表，该函数的时间复杂度为O(n²)。level()求得每个运算节点层数，时间复杂度为O(n²)。ready_list()就绪节点列表实现过程是对每个操作节点，考察它的所有前驱节点，如果所有的前驱都已经过划分被分配到相应模块中，就将此节点加入列表，时间复杂度为O(n)。

当节点未被划分完全时，要对待划分节点重新排序, 每次通过快速排序quickSort()求出所属层号较小的节点和可以划入当前块占用硬件资源最大的节点。大家知道快速排序算法最坏情况下的时间复杂度为O(n²)，又因为运用到快速排序是在节点未被划分完全时，所以是在一层循环下O(n)进行的，因此该处理过程的时间复杂度为O(n³)。

cal_edges()通过扫描n个运算节点及其后继列表来求出划分块间的连接边数总和, 其时间复杂度为O(n²)；假设一个任务DFG被划分为k块，函数cal_delays()用递归调用求得划分后所有块执行总延迟，时间复杂度为O(n·k)。综上，PMMO算法的时间复杂度约为O(n³)。

3 实验及结果分析 3.1 实验设计

采用C语言实现算法，并且与两种效果较好的单一目标算法LBP、CBP作对比。为了便于实验对比，本文采用了文献[13]相同的几类操作运算所占用的硬件资源数(单位用可配置逻辑模块(Configurable Logic Block，CLB)个数表示)和时钟周期数，即加法、减法、乘法所占的硬件面积资源分别为5 CLB、13 CLB、27 CLB，时钟周期分别为1，1，2。

本文从数字信号处理领域选取了6种常用的标准程序集用来验证划分算法，分别是基-4、基-8、基-16快速傅里叶变换，8×8离散余弦变换，4阶矩阵乘法，6×6快速离散余弦变换，所用操作单元数量如表 1所示，操作单元总数依次增加。实验硬件环境为Intel Core i3 CPU, 2.53 GHz, RAM 4 GB的笔记本电脑，程序运行环境为Windows 7。S_RPU随机选取54 CLB、67 CLB、78 CLB。

3.2 算法比较 3.2.1 PMMO算法与LBP算法比较

PMMO算法与LBP算法的划分结果对比数据见表 2，其中：D代表执行延迟时钟周期数，B代表划分块数，E代表块间的连接边数。相比LBP算法，在S_RPU为54 CLB时PMMO算法对于执行延迟平均减少10.3%，对于划分块数平均减少12.1%，对于块间连接边数平均减少4.6%。在S_RPU为67 CLB时PMMO算法对于执行延迟平均减少13.1%，对于划分块数平均减少13.7%，对于块间连接边数平均减少7.5%。在S_RPU为78 CLB时PMMO算法对于执行延迟平均减少17.4%，对于划分块数平均减少15.3%，对于块间连接边数平均减少10.8%。将以上说明的在不同可重构硬件资源下各参数的平均减少率整合在图 2中。LBP算法是减少执行延迟较为有效的算法，而提出的PMMO算法在执行延迟方面进一步改进，获得了较大的操作并行度，并且对于划分块数和连接边数也有明显的减少，具有较好的划分性能。

3.2.2 PMMO算法与CBP算法比较

PMMO算法与CBP算法的划分结果对比数据见表 3。相比CBP算法，在S_RPU为54 CLB时PMMO算法对于执行延迟平均减少25.3%，对于划分块数平均减少14.1%，对于连接边数平均减少1.2%。在S_RPU为67 CLB时PMMO算法对于执行延迟平均减少26.5%，对于划分块数平均减少10.8%，对于连接边数平均减少1.7%。在S_RPU为78 CLB时PMMO算法对于执行延迟平均减少28.2%，对于划分块数平均减少13.1%，对于连接边数平均减少2.5%。将以上说明的在不同可重构硬件资源下各参数的平均减少量整合在图 3中。在执行延迟和划分块数方面相比CBP算法，提出的算法均有显著改善，但由于CBP是减少块间通信量的较好的算法，所以对于连接边数的改进不是非常明显。

通过以上实验对比结果可以看出，PMMO算法相比LBP、CBP算法，对于减少执行延迟有显著的效果，对于减少划分块数也有明显的效果，因为LBP、CBP算法一遇到不满足的节点就结束一个块的划分，而PMMO则采用贪婪策略，搜索到更多的节点划分到块中，尽可能地减少划分块数。然而在保证块内并行度最大和较少的划分块数的情况下，再降低块间通信量的空间就较为有限，因而算法的块间通信量的降低幅度小于其他两种目标参数的改进幅度。并且通过图 2~3可以看出，相比LBP、CBP，提出的算法在总的可重构硬件资源数增加时，执行延迟、划分块数和连接边数的平均减少率都有所提高，这说明PMMO算法在硬件资源较大时，表现出的划分性能更好，所以更适用于大数据量应用的任务划分场景。

4 结语

本文针对可重构任务划分问题，提出了一种PMMO算法。该算法采用广度优先的遍历方式，综合考虑多种影响因素，采取了多种划分策略，利用数字信号处理领域标准程序集转化来的DFG进行实验，与LBP、CBP算法比较，获得了最大的块内操作并行度，同时还能减少划分块数和块间连接边数，得到的划分结果具有明显改善。