Journal of Computer Applications ›› 2017, Vol. 37 ›› Issue (7): 1916-1920.DOI: 10.11772/j.issn.1001-9081.2017.07.1916

Previous Articles     Next Articles

Task partitioning algorithm based on parallelism maximization with multi-objective optimization

YUAN Kaijian, ZHANG Xingming, GAO Yanzhao   

  1. National Digital Switching System Engineering & Technological Research Center, Zhengzhou Henan 450002, China
  • Received:2017-01-24 Revised:2017-03-08 Online:2017-07-10 Published:2017-07-18
  • Supported by:
    This work is partially supported by the National Science and Technology Major Project (2016ZX01012101), the National Natural Science Foundation of China (61572520, 61521003).


袁开坚, 张兴明, 高彦钊   

  1. 国家数字交换系统工程技术研究中心, 郑州 450002
  • 通讯作者: 袁开坚
  • 作者简介:袁开坚(1993-),男,江苏淮安人,硕士研究生,主要研究方向:芯片系统设计、可重构计算;张兴明(1963-),男,河南新乡人,教授,硕士,主要研究方向:宽带信息网络、高性能计算;高彦钊(1984-),男,河北平山人,助理研究员,博士,主要研究方向:高性能计算。
  • 基金资助:

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)两种算法相比,提出的算法获得了最大的块内操作并行度,同时还减少了划分块数和块间的连接边数。

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

CLC Number: