A Circuit Partitioning Method Based on the Structure of Cell Symmetric Matrix

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 addition and subtraction operations. Finally, it simplified the complex calculation of original FM algorithm and implemented 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.