AUTOMATIC LAYOUT MODIFICATION TOOL WITH NON-UNIFORM GRIDS

摘要

A method (and system) of automatically legalizing a circuit layout with layout objects in a presence of a plurality of non-uniform grids is disclosed. The method comprises generating a set of layout constraints comprising design rule constraints and gridding requirements based on the plurality of non-uniform grids. In addition, the method comprises processing the set of layout constraints to a feasible form using Boolean variables by determining infeasibility of the set of layout constraints, identifying infeasible layout constraints from the set of layout constraints, and resolving the infeasibility by a constraint relaxation process. Additionally, the method comprises generating an output circuit layout, for display to a user, by solving the set of layout constraints in the feasible form with standard linear program solvers.

主权项

1. A computer implemented method of legalizing a circuit layout using a plurality of non-uniform grids, the circuit layout comprised of a layout object, the method comprising:
generating a set of layout constraints for the layout object based on the plurality of non-uniform grids, the set of layout constraints comprising design rule check constraints and gridding requirements, the gridding requirements being requisites for the layout object to align to one of the plurality of non-uniform grids, the layout object having layout variables to identify a position of the layout object; processing the set of layout constraints to a feasible form for the layout object to be modified to satisfy the set of layout constraints by:
assigning Boolean variables to the layout variables, each Boolean variable from the Boolean variables assigned to a corresponding layout variable from the layout variables,determining whether the set of layout constraints is infeasible using the Boolean variables assigned to the layout variables, andresponsive to the set of layout constraints determined to be infeasible, (i) identifying an infeasible layout constraint from the set of layout constraints, the infeasible layout constraint causing the set of layout constraints to be infeasible, and (ii) relaxing the identified infeasible layout constraint for the set of layout constraints to be in the feasible form; and generating an output circuit layout by solving the set of layout constraints in the feasible form with a linear program solver.