Reduced Communication Costs via Network Flow and Scheduling for Partitions of Dynamically Reconfigurable FPGAs
This paper presents a dynamically reconfigurable FPGA partitioning algorithm for netlist-level circuits. The proposed algorithm combines traditional max-flow min-cut computing with a scheduling mechanism to improve maximum communication costs. Application of our previously published scheduling mechanism [19] to partitioning of sequential circuits can induce problems regarding the crossing of cuts, so in this paper we introduce an additional labeling mechanism to guarantee the removal of any crossed cuts. Experimental results on a number of standard benchmark circuits show the proposed algorithm achieves superior maximum communication costs compared to the published FBP-m, PAT and Hierarchical algorithms. Compared to the published ILP algorithm, which uses a very different methodology, our algorithm consistently produces superior runtime but approximately equal maximum communication costs.
fpga dynamically reconfigurable computing circuit partitioning temporal partitioning graph theory