Temporal Partitioning Data Flow Graphs for Dynamically Reconfigurable Computing

FPGA-based configurable computing machines are evolving rapidly in large signal processing applications due to flexibility and high performance. In this paper, given a reconfigurable processing unit (RPU) with a logic capacity of A_RPU and a computational task represented by a data flow graph G = (V, E, W), we propose a network flow-based multiway task partitioning algorithm to minimize communication costs for temporal partitioning. The proposed algorithm obtains an optimal solution with minimum interconnection under area constraints. The optimal solution is a cut set. In our approach, two techniques are applied. In the initial partition, any feasible min-cut is produced by the proposed network flow-based algorithm, so a set of feasible min-cuts is obtained. From the feasible solutions, the scheduling technique selects an optimal global solution.