Generic ILP-based approaches for time-multiplexed FPGA partitioning

Due to the precedence constraints among vertices, the partitioning problem for time-multiplexed field-programmable gate arrays (TMFPGAs) is different from the traditional one. In this paper, we first derive logic formulations for the precedence-constrained partitioning problems and then transform th e formulations into integer linear programs (ILPs). The ILPs can handle the precedence constraints and minimize cut sizes simultaneously. To enhance p erformance, we also propose a clustering method to reduce the problem size. Experimental results based on the Xilinx TMFPGA architecture show that our approach outperforms the list-scheduling (List), the network-flow-based (F BB-m) (Liu and Wong, 1998), and the probability-based (PAT) (Chao, 1999) me thods by respective average improvements of 46.6%, 32.3%, and 21.5% in cut sizes. Our approach is practical and scales well to larger problems; the em pirical runtime grows close to linearly in the circuit size. More important ly, our approach is very flexible and can readily extend to the partitionin g problems with various objectives and constraints, which makes the ILP for mulations superior alternatives to the TMFPGA partitioning problems.