|
Abstract : |
The VLSI circuit partitioning problem with any given objective like mincut is inherently a constraint-driven one. Frequently encountered constraints range from specified balance-ratios on total cell sizes in subcircuits of a partition, upper bound on the deterioration of some metric when re-partitioning a pre-placed circuit, and even distributions of external nets and internal pins among subcircuits. Constraint satisfaction during partitioning and placement of VLSI circuits is an important problem, and effective techniques to address it lead to high-quality physical design solutions. This problem has, however, been cursorily treated in previous partitioning and placement research. Our work presented here addresses the balance-ratio constraint, and is a crucial first step to an effective solution to the general constraint-satisfaction problem. The balance-ratio is an important constraint that helps in obtaining a minimum-area balanced layout of the circuit, and efficient techniques for satisfying it without compromising the mincut objective is the focus of this paper. In current iterative-improvement mincut partitioners (e.g., FM [3], LA [4], PROP [1], GFM [5] and GMetis [6]), the "goodness " of moves is evaluated as the gain of the corresponding cells without consideration of their sizes, and the balance-ratio constraint is tackled by disallowing moves that violate it. These methods can lead to sub-optimal solutions since the process is biased against the movement of large cells and clusters, |
