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 satis fy the constraints on the number of constituent elements and external nets. To solve the problem, the Optimal Circuit Reduction Method, suggested by R . Bazylevych is being used. The optimal reduction tree to reflect the hiera rchical entrance of smaller clusters into bigger ones is being built for th e first step. At the second step we select one or more tree vertices which better meet the given constraints and are the first partitions generated fr om. After creating every new partition we eliminate its elements from the c ircuit and repeat the procedure to complete all partitions. During the last stage optimization strategies to exchange some elements between the partit ions are being used. Better or equivalent results among known tests confirm the effectiveness of this method.