Patent ID: 8302062
Filing Date: 2012-10-30
Classification: G06F

Abstract:
1. A method for obtaining a feasible integer solution in a hierarchical circuit layout optimization, comprising: receiving, using a computer device, a hierarchical circuit layout and ground rule files; representing, using the computer device, constraints in the hierarchical circuit layout as an original integer linear programming problem; deriving, using the computer device, a relaxed linear programming problem from the original integer linear programming problem by relaxing integer constraints and using relaxation variables on infeasible constraints; partitioning the relaxation variables into three groups including a first group of relaxation variables, a second group of relaxation variables, and a third group of relaxation variables, wherein the first group of relaxation variables comprises any self-mirrored-abutted edge variable, the second group of relaxation variables comprises any transformation variable, and the third group of relaxation variables comprises any edge variable that is not a self-mirrored-abutted edge variable; solving, using the computer device, the relaxed linear programming problem to obtain a linear programming solution; rounding, using the computer device, at least one relaxation variable in each of the three groups to an integer value according to the linear programming solution using a clustering approach, wherein the relaxation variables of each of the three groups are rounded in an order unique to each of the three groups; iterating, using the computer device, unrounded variables back through the deriving, solving, and rounding processes until all unrounded variables are rounded to integer values; and generating, using the computer device, a modified hierarchical circuit layout in response to a determination that all the variables are rounded to integer values.