Xiaoping Ping Tang

US Patent:

7305641, Dec 4, 2007

Filed:

Jan 12, 2005

Appl. No.:

11/034098

Inventors:

Xiaoping Tang - Elmsford NY, US

Assignee:

International Business Machines Corporation - Armonk NY

International Classification:

G06F 9/45
G06F 17/50

US Classification:

716 10, 716 9, 716 11

Abstract:

Disclosed are a method and a system for redistributing white space on an integrated circuit. The method comprises the steps of providing a series of circuit blocks for the integrated circuit, and placing the blocks on the integrated circuit to obtain a predefined optimal wire length. In accordance with the preferred embodiment of the invention, we first show that the problem of placing the blocks to obtain an optimal wire length, can be formulated as linear programming. Then, we find it can be solved by efficient min-cost flow implementation instead of general and slow linear programming. The approach guarantees to obtain the minimum total wire length for a given floorplan topology. We also show that the approach is capable of handling various constraints such as fixed-frame (fixed area), IO pins, pre-placed blocks, boundary blocks, range placement, alignment and abutment, rectilinear blocks, cluster placement, and bounded net delay, without loss of optimality.

US Patent:

7437691, Oct 14, 2008

Filed:

Apr 11, 2006

Appl. No.:

11/279283

Inventors:

Xiaoping Tang - Elmsford NY, US
Xin Yuan - Williston VT, US

Assignee:

International Business Machines Corporation - Armonk NY

International Classification:

G06F 17/50

US Classification:

716 2, 716 7, 716 10, 703 2, 703 6, 703 16

Abstract:

A system and method are disclosed for legalizing a flat or hierarchical VLSI layout to meet multiple grid constraints and conventional ground rules. Given a set of ground rules with multiple grid constraints and a VLSI layout (either hierarchical or flat) which is layout-versus-schematic (LVS) correct but may not be ground rule correct, the system and method provide a legalized layout which meets the multiple grid constraints while maintaining LVS correctness and fixing the ground rule errors as much as possible with minimum layout perturbation from the input design. The system and method support multiple grid pitch constraints for hierarchical design, and provide for LVS correctness to be maintained while an on-grid solution possibly with some spacing violations.

US Patent:

7761818, Jul 20, 2010

Filed:

Jul 25, 2007

Appl. No.:

11/782706

Inventors:

Michael S. Gray - Fairfax VT, US
Xiaoping Tang - Elmsford NY, US
Xin Yuan - Williston VT, US

Assignee:

International Business Machines Corporation - Armonk NY

International Classification:

G06F 17/50

US Classification:

716 2, 716 5, 716 7, 716 10, 716 11

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.

US Patent:

7895562, Feb 22, 2011

Filed:

Dec 18, 2007

Appl. No.:

11/958606

Inventors:

Michael S. Gray - Fairfax VT, US
Matthew T. Guzowski - Essex VT, US
Kevin W. McCullen - Essex Junction VT, US
Xiaoping Tang - Elmsford NY, US
Robert F. Walker - St. Geroge VT, US
Xin Yuan - Williston VT, US

Assignee:

International Business Machines Corporation - Armonk NY

International Classification:

G06F 17/50

US Classification:

716132, 716133, 716134, 716135

Abstract:

An adaptive weighting method for layout optimization differentiates different priorities by assigning the weight of a higher priority (p) to be multiple of the weight of a lower priority (p) where W(p)=m% W(p. To avoid numerical imprecision, this method keeps the total cost in the objective function within a trustable range by scaling the initial weights in the objectives, while maintaining relativity, to produce the scaled weights.

US Patent:

7904840, Mar 8, 2011

Filed:

Oct 26, 2007

Appl. No.:

11/925238

Inventors:

Xiaoping Tang - Elmsford NY, US

Assignee:

International Business Machines Corporation - Armonk NY

International Classification:

G06F 17/50

US Classification:

716 2, 716 1, 716 3, 716 8, 716 9, 716 10, 716 11, 716 14

Abstract:

Disclosed are a method and a system for redistributing white space on an integrated circuit. The method comprises the steps of providing a series of circuit blocks for the integrated circuit, and placing the blocks on the integrated circuit to obtain a predefined optimal wire length. In accordance with the preferred embodiment of the invention, we first show that the problem of placing the blocks to obtain an optimal wire length, can be formulated as linear programming. Then, we find it can be solved by efficient min-cost flow implementation instead of general and slow linear programming. The approach guarantees to obtain the minimum total wire length for a given floorplan topology. We also show that the approach is capable of handling various constraints such as fixed-frame (fixed area), IO pins, pre-placed blocks, boundary blocks, range placement, alignment and abutment, rectilinear blocks, cluster placement, and bounded net delay, without loss of optimality.

US Patent:

7962879, Jun 14, 2011

Filed:

Jul 31, 2008

Appl. No.:

12/183578

Inventors:

Xiaoping Tang - Elmsford NY, US
Xin Yuan - Williston VT, US

Assignee:

International Business Machines Corporation - Armonk NY

International Classification:

G06F 17/50
G06F 17/10

US Classification:

716122, 716111, 716132, 703 2, 703 16

Abstract:

A system and method are disclosed for legalizing a flat or hierarchical VLSI layout to meet multiple grid constraints and conventional ground rules. Given a set of ground rules with multiple grid constraints and a VLSI layout (either hierarchical or flat) which is layout-versus-schematic (LVS) correct but may not be ground rule correct, the system and method provide a legalized layout which meets the multiple grid constraints while maintaining LVS correctness and fixing the ground rule errors as much as possible with minimum layout perturbation from the input design. The system and method support multiple grid pitch constraints for hierarchical design, and provide for LVS correctness to be maintained while an on-grid solution possibly with some spacing violations.

US Patent:

8296706, Oct 23, 2012

Filed:

Apr 26, 2010

Appl. No.:

12/767375

Inventors:

Michael S. Gray - Fairfax VT, US
Xiaoping Tang - Mohegan Lake NY, US
Xin Yuan - Roseville CA, US

Assignee:

International Business Machines Corporation - Armonk NY

International Classification:

G06F 17/50

US Classification:

716122, 716110, 716113, 716123, 716126, 716132, 716136, 716139

Abstract:

A computer-implemented method for handling a plurality of constraints in layout optimization for an integrated circuit (IC) layout is disclosed. In one embodiment, the method includes building a graph representing the plurality of constraints; marking two-dimensional constraints in the plurality of constraints; generating two-dimensional clusters including groups of the two-dimensional constraints; handling at least one of the two-dimensional clusters, the handling including finding a solution for the two-dimensional constraints in the at least one two-dimensional cluster; repeating the handling for any unprocessed two-dimensional clusters until all of the two-dimensional clusters are handled; and adopting the solution for each of the two-dimensional clusters to solve at least a portion of the plurality of constraints including the two-dimensional clusters.

US Patent:

8302062, Oct 30, 2012

Filed:

Feb 25, 2010

Appl. No.:

12/712880

Inventors:

Michael S. Gray - Fairfax VT, US
Xiaoping Tang - Mohegan Lake NY, US
Xin Yuan - Roseville CA, US

Assignee:

International Business Machines Corporation - Armonk NY

International Classification:

G06F 17/50

US Classification:

716132, 716124, 716135, 716139

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.