Circuit Partitioning for FPGAs by the Optimal Circuit Reduction Method

[摘要] Mathematically the most difficult partitioning problem–packaging–is being considered.Its purpose is to minimize a number of partitions and to satisfy the constraints onthe number of constituent elements and external nets. To solve the problem, the OptimalCircuit Reduction Method, suggested by R. Bazylevych is being used. The optimalreduction tree to reflect the hierarchical entrance of smaller clusters into bigger ones isbeing built for the first step. At the second step we select one or more tree vertices whichbetter meet the given constraints and are the first partitions generated from. Aftercreating every new partition we eliminate its elements from the circuit and repeat theprocedure to complete all partitions. During the last stage optimization strategies toexchange some elements between the partitions are being used. Better or equivalentresults among known tests confirm the effectiveness of this method.

[学科分类] 电子、光学、磁材料