Vertical partitioning of row-based circuits with minimal net-crossings

An algorithm for the bipartitioning of circuits with minimal net-crossings is presented. It is applicable to a row-based circuit such as a gate array and a standard cell. This algorithm counts exactly the number of net-crossings when the row assignment of each cell is fixed, while the time complexity remains linear in the number of pins as Fiduccia´s min-cut algorithm. Results of several circuits show that the numbers of net-crossings were significantly reduced compared with the earlier min-cut algorithms. About 40% reductions in the number of net-crossings, which more closely reflects the routing demand than the conventional cut number compared to the earlier work, were achieved using this method on two benchmark circuits