Abstract: Concerning the parallelism maximization of hardware task partitioning in reconfigurable system, a task partitioning algorithm based on parallelism maximization for multi-objective optimization was proposed. Firstly, the operating nodes to be partitioned were discovered according to the breadth first search under the constraints of hardware area resource and reasonable dependency relation. Then, considering the effect of execution delay on system completion time, the parallelism of intra-block operations was maximized. Finally, the new nodes were accepted under the principle of reducing the fragment area without increasing the number of connections between blocks. Otherwise, a block partitioning was ended. The experimental results show that the proposed algorithm achieves the maximum intra-block parallelism and reduces the number of blocks and connecting edges compared with the existing Level Based Partitioning (LBP) and Cluster Based Partitioning (CBP) algorithms.

Key words: reconfigurable system, task partitioning, parallelism maximization, multi-objective optimization, breadth first search

摘要： 针对可重构系统硬件任务划分并行度最大问题，提出一种基于并行度最大的多目标优化任务划分算法。首先，该算法在满足可重构硬件面积资源和合理依赖关系的约束下，按广度优先的遍历方式搜索待划分的操作节点；然后，着重考虑执行延迟对于系统完成时间的影响，将块内操作节点的并行度最大化；最后，在减少碎片面积和不增加块间连接边数的原则下接受新的节点，否则就结束一个块划分。实验结果表明，与现有的基于层划分（LBP）和基于簇划分（CBP）两种算法相比，提出的算法获得了最大的块内操作并行度，同时还减少了划分块数和块间的连接边数。

关键词: 可重构系统, 任务划分, 并行度最大化, 多目标优化, 广度优先搜索