Methods to obtain a feasible integer solution in a hierarchical circuit layout optimization
US8302062B2 · kind B2 · utility
Assignee
Inventors
Key dates
| Filing date | Feb 25, 2010 |
| Grant date | Oct 30, 2012 |
| Priority date | — |
| Expiry date | Oct 31, 2030 |
Classification
- Technology area (CPC G)Physics
- CPC primaryG06F30/39
- WIPO fieldComputer technology
- WIPO sectorElectrical engineering
Abstract
An approach that obtains a feasible integer solution in a hierarchical circuit layout optimization is described. In one embodiment, a hierarchical circuit layout and ground rule files are received as input. Constraints in the hierarchical circuit layout are represented as an original integer linear programming problem. A relaxed linear programming problem is derived from the original integer linear programming problem by relaxing integer constraints and using relaxation variables on infeasible constraints. The relaxed linear programming problem is solved to obtain a linear programming solution. Variables are then clustered, and at least one variable from each cluster is rounded to an integer value according to the linear programming solution. Next, it is determined whether all the variables are rounded to integer values. Unrounded variables are iterated back through the deriving of the integer linear programming problem, solving of the relaxed linear programming problem, and rounding of a subset of variables. A modified hierarchical circuit layout is generated in response to a determination that all the variables are rounded to integer values.
Source: USPTO / EPO open patent data. Objective bibliographic and citation counts.