FPGA Partitioning with Complex Resource Constraints

In this paper, we present an algorithm for circuit partitioning with complex resourceconstraints in large FPGAs. Traditional partitioning methods estimate the capacity ofan FPGA device by counting the number of logic blocks, however this is not accuratewith the increasing diverse resource types in the new FPGA architectures. We firstpropose a network flow based method to optimally check whether a circuit or a subcircuitis feasible for a set of available heterogeneous resources. Then the feasibilitychecking procedure is integrated in the FM-based algorithm for circuit partitioning.Incremental flow technique is employed for efficient implementation. Experimentalresults on the MCNC benchmark circuits show that our partitioning algorithm not onlyyields good results, but also is efficient. Our algorithm for partitioning with complexresource constraints is applicable for both multiple FPGA designs (e.g., logic emulationsystems) and partitioning-based placement algorithms for a single large hierarchicalFPGA (e.g., Actel's ES6500 FPGA family)