International Business Machines Corporation

Xiaoping Tang

Xin Yuan

Michael S Gray

Minsik Cho

Kevin W McCullen

Matthew Thomas Guzowski

Rajiv V Joshi

Ruchir Puri

Fook-Luen Heng

Haoxing Ren

Alexey Y Lvov

Hua Xiang

Matthew Mantell Ziegler

Robert F Walker

Rani Narayan

An initial layout of at least a portion of a given layer of an integrated circuit design is decomposed into multiple sub-layouts by splitting each of a plurality of shapes of the initial layout into multiple segments, constructing a constraint graph to represent relationships between the segments, reducing the constraint graph to a stitch graph, determining at least one cut line of the stitch graph, and generating a decomposed layout based on the determined cut line. The decomposed layout in an illustrative embodiment includes first and second sub-layouts comprising respective disjoint subsets of the segments, with each of the sub-layouts of the decomposed layout being associated with a different pattern mask of a double patterning lithography process. The layout decomposition process advantageously minimizes the number of stitches between the sub-layouts without introducing excessive computational complexity.

Layout decomposition method and apparatus for multiple patterning lithography

Systems and methods for relative ordering circuit synthesis are provided herein. One aspect provides for generating at least one circuit design via at least one processor accessible by a computing device; wherein generating at least one circuit design comprises: generating at least one relative order structure based on at least one circuit design layout, the at least one relative order structure comprising at least one placement constraint associated with at least one circuit element; placing the at least one circuit element associated with the at least one placement constraint within a circuit design according to the at least one placement constraint; and placing circuit elements not associated with the at least one placement constraint within the circuit design. Other embodiments and aspects are also described herein.

Relative ordering circuit synthesis

Approaches are provided for fixing pin mismatches from swapping library cells in layout migration. Specifically, a method is provided that includes collecting information about a first technology pin from a library cell in a first technology. The method further includes swapping the library cell in the first technology with a library cell in a second technology. The method further includes collecting information about a second technology pin from the library cell in the second technology. The method further includes building a pin-mapping table that is configured to map the first technology pin to the second technology pin. The method further includes scaling a layout from the first technology to the second technology. The method further includes modifying the layout based on the pin-mapping table to match the at least one first technology pin to the at least one second technology pin while satisfying ground rules of the second technology.

Systems and methods for fixing pin mismatch in layout migration

Solutions for optimizing an integrated circuit layout for implementation in an integrated circuit are disclosed. In one embodiment, a computer-implemented method is disclosed including: obtaining a plurality of hierarchical constraints in mathematical form, the plurality of hierarchical constraints defining a first integrated circuit layout; partitioning the plurality of hierarchical constraints into groups according to one or more partitioning rules; determining whether a boundary condition exists between two of the groups, and distributing a slack or a gap between the two of the groups in the case that the boundary condition exists; creating a plurality of integer linear programming problems associated with each of the groups; determining a solution for each of the plurality of integer linear programming problems; and integrating each solution together to form a second integrated circuit layout.

Parallel solving of layout optimization

An approach for decomposing a layout for triple patterning lithography is described. In one embodiment, a triple patterning conflict graph is built from a layout having pattern features specified as shapes. The triple patterning conflict graph represents the shapes in the layout and coloring constraints associated with the shapes. The shapes represented by the triple patterning conflict graph are decomposed into three colors to avoid color conflict, while balancing the color density among the three colors and minimizing a number of stitches used to represent the shapes in the layout. Color conflicts in the decomposition are resolved by selectively segmenting the shapes in the decomposition that are associated with the color conflict.

Decomposing layout for triple patterning lithography

Methods and systems for migrating circuit layouts. A floorplan layout is built for a target circuit using a subset of constraints that characterize a layout structure of an original circuit. Shape-constraint-based scaling is used on the floorplan layout by scaling parts of the floorplan layout in accordance with a plurality of different scaling ratios such that portions of the floorplan layout are concurrently scaled with the plurality of different scaling ratios. Cells are placed at locations defined by the floorplan layout. The floorplan layout is checked with shape-constraint-based legalization using all of the constraints to produce a migrated layout.

Structural migration of integrated circuit layout

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.

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

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.

Handling two-dimensional constraints in integrated circuit layout

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.

VLSI artwork legalization for hierarchical designs with multiple grid constraints

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.

Method and system to redistribute white space for minimizing wire length

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.

Adaptive weighting method for layout optimization with multiple priorities

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.

Growing community of inventors

Mohegan Lake, NY, United States of America

Xiaoping Tang