超图平衡二划分是超大规模集成电路物理设计的重要一环。Kernighan-Lin算法和Fiduccia-Mattheyses算法等迭代优化算法是求解该NP-困难问题的常用方法。然而, 这些算法具有以下缺点: 一是对于较差的初始解, 算法容易陷入局部最优。二是由于平衡条件的约束, 顶点的移动受到诸多限制。针对上述问题, 本文将超图平衡二划分问题转化为0-1规划问题, 并设计了求解该问题的离散迭代算法, 在一定程度上克服了传统的迭代算法受平衡条件与初始解约束的缺点。在ISPD98电路划分测试样例上, 本文的算法取得了比Fiduccia-Mattheyses算法质量更高的解。在20次随机实验中, 本文的平均割边数比Fiduccia-Mattheyses算法少13.2%。将本文的结果作为Fiduccia-Mattheyses算法的初始解作进一步优化, 所产生的平均割边数比Fiduccia-Mattheyses算法少30.1%。不仅如此, 本文的算法还可以嵌入到多级划分算法框架中, 取得的平均割边数比multilevel partitioning (MLPart) 少3.6%。

The problem of hypergraph balanced bipartitioning has become a vital part of very large scale integration circuit physical design. Iterative methods such as Kernighan-Lin and Fiduccia-Mattheyses heuristics have been used to solve this NP-hard problem and perform well. However, these methods have some disadvantages as follows. First, an initial solution of poor quality will easily get trapped in bad local optima. Second, the movement of vertices is restricted to balanced partition. To resolve these issues, we transform the hypergraph bi-partitioning problem into a 0-1 programming. Then an iterative algorithm is designed to solve the problem, which overcomes the shortcomings of traditional iterative algorithms. Our algorithm performs better than Fiduccia-Mattheyses on the ISPD98 hypergraph partitioning benchmarks. Our results have an average improvement of 13.2% over Fiduccia-Mattheyses. If taking our results as initial solutions of the Fiduccia-Mattheyses heuristic, the average cut count is reduced by 30.1%. Moreover, our algorithm can be incorporated into a multilevel partitioning framework, and the partition result has an average improvement of 3.6%.