Reconfigurable hardware task partitioning algorithm based on depth first greedy search
Naijin Chen · Journal of Computer Applications · 2012
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.