Fuzzy Bi- and multi-partitioning for circuits represented by hypergraphs

A new strategy for partitioning hypergraphs in complex LSI and VLSI circuits is presented. A new fuzzy net-cut model has been developed to treat multi-pin-nets without splitting into two-pin-nets. The combinatorial optimization algorithm is derived from statistical physics. The circuit graph is modeled as a highly coupled spin system and the mean field approximation is used to achieve linear time complexity. Fuzzy partitioning enables a qualitative and macroscopic approach by interpreting the mean values of the spin system as fuzzy membership degrees. The proposed strategy is tested with MCNC benchmark problems and compared to results achieved recently. The performance of the new algorithm is comparable with neural networks and simulated annealing, but much faster, because of its linear time complexity. Furthermore, the partitioning algorithm has been implemented in an industrial CAD design tool and results are given.