In the very large scale integration (VLSI) physical design automation, circuit partitioning is a key stage and it is also an NP-hard combinatorial optimization problem. In this paper, we proposed a method for the circuit partitioning, which was on the base of Fiduccia-Mattheyses (FM) of the single-vertex-move algorithm and made use of a new symmetrical rectangle structure of cells. First, this algorithm stored the cells and nets by the new symmetrical rectangle structure of cells. And then it calculated the gains of the moving cells by the simple addi-tion and subtraction operations. Finally, it simplified the complex calculation of original FM algorithm and im-plemented the circuit partitioning. The experimental results show that the proposed new algorithm, which can guarantee the same results obtained by the original algorithm, not only significantly simplifies the implementation of the FM algorithm, but also maintains linear complexity. It can improve the partitioning results of cut edge by 95.89% for several circuit examples.%电路划分是超大规模集成电路自动化设计中的一个关键的阶段,同时也是NP-hard组合优化问题.文中基于结点移动的Fiduccia-Mattheyses(FM)算法提出新的cell对称矩阵数据结构,实现一种电路划分方法.首先使用对称矩阵数据结构存储结点和线网信息,然后利用简单的加减运算代替划分过程中结点增益的计算,最后简化原始算法中复杂的判断与计算完成对电路的划分.实验结果表明,与原始FM算法相比,在保证得到等价划分结果的情况下,该方法显著简化了实现过程,并且保持了线性复杂度;对电路实例进行划分,平均切边优化效果达到95.89%.
展开▼
