关键词: 可重构计算, 时域划分, 深度优先贪婪搜索, 通信成本, 资源约束, 硬件碎片

Abstract: This paper proposed a hardware task partitioning algorithm according to the problems of communication cost minimum in reconfigurable computing, called DFGSP (Depth First Greedy Search Partitioning). At first, the front task was taken from the ready queue, a Directed Acyclic Graph (DAG), which was transformed from a computing-intensive task, was scanned and partitioned by Depth First Search (DFS). Then, the number of outputting-edges (quantized to communication cost) of current partitioning module was computed when the task node did not meet the area constraints. Finally, the ready task node, which considered sufficiently partitioning module outputting-edges which were not increasing and made good use of reconfigurable resources hardware fragment as soon as possible, was scanned and partitioned, after skipping the task node which did not meet the area constraints. In comparison with the Cluster-Based Partitioning (CBP) algorithm and Level Sensitive Cluster-Based Partitioning (LSCBP) algorithm, the experimental results show that the proposed algorithm can obtain the least number of partitioning modules and the least average number of input-output edges crossing modules, and the practical results indicate the proposed algorithm gets a prominent improvement in hardware task partitioning performance over previous algorithms, while the run-time efficiency is preserved.

Key words: reconfigurable computing, temporal partitioning, depth first greedy search, communication cost, resource restraint, hardware fragment