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.