Practical method for obtaining a feasible integer solution in hierarchical layout optimization

Layout optimization is a powerful technique for design migration, circuit performance tuning and design for manufacturing. In this paper, we study the problem of layout optimization for the hierarchical circuits in modern VLSI designs which essentially can be formulated as the integer linear programming (ILP) problem. Existing approaches are either unable to handle hierarchy, inefficient or failing to provide the feasible integer solutions for large scale hierarchical layouts. We present a practical method, IRLS algorithm (iteratively rounding and LP solving) which consists of a proper rounding strategy based on the careful analysis of hierarchical layout constraints, to obtain a feasible integer solution in the constraint-based layout modification process, thus enabling efficient optimization for large scale hierarchical layouts, and specifically avoiding the need to use the general ILP solvers. Experimental results demonstrate the efficiency and effectiveness of the IRLS algorithm. Compared with the general ILP/MILP solver, the IRLS algorithm can obtain decent results with much less runtime (speed-up ranging from 4.000X to 360.000X). Compared with the two-step approach(Allen et al., 2003) on legalizing a set of large scale industry circuit layouts, the IRLS algorithm can provide much better solution (satisfying all abutment/alignment constraints that the two-step approach fails to meet).