Gate matrix partitioning

An algorithm is presented which partitions a gate matrix into a number of matrices such that the total area and the aspect ratio of the circumscribing rectangle are improved. The algorithm is based on the min-cut algorithm. The gain function and the balance condition are redefined for the gate matrix problem. The time complexity of the algorithm is O(t)+O(|N_I|²), where t is the number of gate-net intersections, and N_I the subset of nets that intersect long gates. A novel gate-sequencing algorithm, designed for assigning gates in the partitioned gate matrices simultaneously, is introduced. By using the simultaneous-gate-sequencing algorithm, the partitioned gate matrices are connected by sharing gates. Since the same column is used for a gate shared by adjacent matrices, the layout does not require extra routing area. Experimental results show significant improvement over the layout without partition. For the three examples used in a previous paper, the area reduction ranges from 11-41%. The aspect ratio improves from 2.63, 4.00, and 2.59 to 1.04, 1.22, and 1.28, respectively