Network flow based circuit partitioning for time-multiplexed FPGAs

Time-multiplexed FPGAs have the potential to dramatically improve logic density by time-sharing logic, and have become an active research for reconfigurable computing. The partitioning problem for time-multiplexed FPGAs is different from the traditional partitioning problem in that the nodes have precedence constraints among them, and the widely used iterative improvement partitioning methods such as K&L, FM are no longer applicable. All previous approaches used list scheduling heuristics. In this paper, we present a network flow based algorithm for multi-way precedence constrained partitioning, which can handle the precedence constraints while minimizing the net-cut size. The experimental results on the MCNC benchmark circuits show that our algorithm out-performs list scheduling by a big margin, with an average improvement of over 50% for bipartitioning and 20% for multi-way partitioning.