Obtaining a feasible integer solution in a hierarchical circuit layout optimization
US7761818B2 · kind B2 · utility
Assignee
Inventors
Key dates
| Filing date | Jul 25, 2007 |
| Grant date | Jul 20, 2010 |
| Priority date | — |
| Expiry date | Jan 30, 2028 |
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. A subset of variables from the relaxed linear programming problem is rounded to integer values 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.