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 (C.M. Fiduccia and R.M. Mattheyses, 1982; B.W. Kernighan and S. Lin, 1978) are no longer applicable. All later approaches (S. Trimberger, 1998; D. Chang and M. Marek-Sadowska, 1998; 1997) used list scheduling heuristics. 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 outperforms list scheduling by a big margin, with an average improvement of over 50% for bipartitioning and 20% for multi way partitioning.