InnovationQ will be updated on Sunday, Oct. 22, from 10am ET - noon. You may experience brief service interruptions during that time.
Browse Prior Art Database

A Method for Hierarchical Minimum-Perturbation VLSI Layout Optimization with Integer Constraints That Modifies Transform Locations and Contents

IP.com Disclosure Number: IPCOM000125493D
Original Publication Date: 2005-Jun-03
Included in the Prior Art Database: 2005-Jun-03
Document File: 4 page(s) / 41K

Publishing Venue



Presented is a technique for the hierarchical optimization of a VLSI layout using linear programming. A real-valued solution is obtained from the solver, and an integral solution is then derived using a sequence of selective re-optimizations.

This text was extracted from a PDF file.
At least one non-text object (such as an image or picture) has been suppressed.
This is the abbreviated version, containing approximately 41% of the total text.

Page 1 of 4

A Method for Hierarchical Minimum -Perturbation VLSI Layout Optimization with Integer Constraints That Modifies Transform Locations and Contents

Applications for optimizing VLSI layouts face the stringent restriction of producing an integer result: since downstream CAD tools require integer values for shape coordinates and positions, any modifications to a layout must result in an integral result. Moreover, feasibility--the obeying of all constraints--is an important requirement for these problems, since the constraints represent (among other things) the connectivity of the layout.

In certain situations, it is possible to guarantee an integer result by carefully constructing the optimization problem to be solved. Specifically, if a convex linear program is built in which all constraints and objectives are piecewise difference relationships of two variables or of a variable and a constant, then the optimal solution will be integral (see US Patent 6189132).

If the requirement for difference relationships is relaxed to allow both difference and sum relationship, then if an integral optimal solution exists, it can be efficiently obtained (see US Patent Application 20040230922A1).

The central structural requirement for these problems is that they have only pairwise relationships. In the setting of the optimization of a hierarchical design, this is accomplished in the following way. For each model (i.e., cell) used in the layout to be optimized: either freeze the definition of the model (i.e., its contents) and allow the placements of that model to change; or freeze all the placements of the model and allow its contents to change.

By doing this, all geometric relationships (which subsequently become constraints or objectives in the mathematical optimization problem) are encoded in the linear program as inequalities involving sums and differences of two variables or of a variable and a constant.

However, in many situations it is desirable to change the definition of a model AND the placements of that model in the design. To achieve this, inequalities involving up to four variables are required. In this case, the existing techniques for obtaining in integer solution from the corresponding optimization problem no longer apply. Conventional optimization techniques for producing integral solutions--such as branch and bound--are in general too slow for the large-scale problems we solve in layout optimization. And simple rounding of the non-integral solution components can in general produce an infeasible solution.

Presented is a technique for solving a general layout-optimization problem and efficiently obtaining an integral solution.


Page 2 of 4

Subcircuit must both move and change


* RX-to-RX spacing must increase
* CA-to-GATE spacing must increase
* The only way to achieve this is by: changing the placement of the cells changing the contents of the cells



Placement location of second model

Placement location of first model