中文摘要：

电路划分是超大规模集成电路自动化设计中的一个关键的阶段,同时也是NP-hard组合优化问题.文中基于结点移动的Fiduccia-Mattheyses（FM）算法提出新的cell对称矩阵数据结构,实现一种电路划分方法.首先使用对称矩阵数据结构存储结点和线网信息,然后利用简单的加减运算代替划分过程中结点增益的计算,最后简化原始算法中复杂的判断与计算完成对电路的划分.实验结果表明,与原始FM算法相比,在保证得到等价划分结果的情况下,该方法显著简化了实现过程,并且保持了线性复杂度;对电路实例进行划分,平均切边优化效果达到95.89%.

英文摘要：

In the very large scale integration （VLSI） physical design automation, circuit partitioning is a key stageand it is also an NP-hard combinatorial optimization problem. In this paper, we proposed a method for the circuitpartitioning, which was on the base of Fiduccia-Mattheyses （FM） of the single-vertex-move algorithm and madeuse of a new symmetrical rectangle structure of cells. First, this algorithm stored the cells and nets by the newsymmetrical rectangle structure of cells. And then it calculated the gains of the moving cells by the simple additionand subtraction operations. Finally, it simplified the complex calculation of original FM algorithm and implementedthe circuit partitioning. The experimental results show that the proposed new algorithm, which canguarantee the same results obtained by the original algorithm, not only significantly simplifies the implementationof the FM algorithm, but also maintains linear complexity. It can improve the partitioning results of cut edge by95.89% for several circuit examples.