Methods to obtain a feasible integer solution in a hierarchical circuit layout optimization

A computer-readable storage medium storing computer instructions, which when executed, enables a computer system to obtain a feasible integer solution in a hierarchical circuit layout optimization, the computer instructions comprising:

• program code for receiving a hierarchical circuit layout and ground rule files;
• program code for representing constraints in the hierarchical circuit layout as an original integer linear programming problem;
• program code for deriving a relaxed linear programming problem from the original integer linear programming problem by relaxing integer constraints and using relaxation variables on infeasible constraints;
• program coded for 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;
• program code for solving the relaxed linear programming problem to obtain a linear programming solution;
• program code for rounding 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;
• program code for iterating unrounded variables back through the program code for deriving, solving, and rounding until all unrounded variables are rounded to integer values:
• and
• program code for generating a modified hierarchical circuit layout in response to a determination that all the variables are rounded to integer values.

A system for obtaining a feasible integer solution in a hierarchical circuit layout optimization, comprising:

• at least one computer processor;
• and
• at least one memory device operatively coupled to the at least one computer processor, the system comprising:
• a module for receiving a hierarchical circuit layout and ground rule files;
• a module for representing constraints in the hierarchical circuit layout as an original integer linear programming problem;
• a module for deriving a relaxed linear programming problem from the original integer linear programming problem by relaxing integer constraints and using relaxation variables on infeasible constraints;
• a module for 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;
• a module for solving the relaxed linear programming problem to obtain a linear programming solution;
• a module for rounding 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;
• a module for iterating unrounded variables back through the deriving, solving, partitioning and rounding modules until all unrounded variables are rounded to integer values;
• and
• a module for generating a modified hierarchical circuit layout in response to a determination that all the variables are rounded to integer values.