Gate matrix partitioning

A heuristic algorithm is presented that partitions a gate matrix into two matrices so that the total area and the aspect ratio of the circumscribing rectangle are improved. The algorithm is based on the min-cut algorithm, with the gain function and balance condition redefined for the gate matrix problem. The time complexity of the algorithm is O(t)+(n* mod G/sub L/ mod *LB), where t is the number of transistors, n the number of nets, mod G/sub L/ mod the number of long gates, and LB the maximum number of nets on a gate. Experimental results show significant improvement over the layout without partition. For three examples the area reduction ranges from 20% to 30%. The aspect ratio improves from 2.59, 2.63 and 4.00 to 1.11, 1.16, and 1.18, respectively.<>