US 5,689,433 A · Method and apparatus for compacting integrated circuits with wire length minimization

Abstract

A computer-aided design method and apparatus for compacting semiconductor circuit layouts to meet a specified set of design rules begins by fracturing a specified circuit layout into a set of trapezoids and storing the resulting cells in a database identifying the boundaries of each cell, and the cell adjacent each boundary. The method additionally includes a procedure for minimizing wire lengths in the compacted layout. Nonempty cells are identified as being of specific materials, and empty spaces between cells are represented. For each cell boundary, the database also stores data representing the boundary edge's end points. Neighboring cells on the same and related layers of the circuit layout share edges in the database. When a point on an edge of a cell is moved, the edge of each neighboring cell that shares that point is also moved. To adjust a circuit layout, the cells in the layout are processed in a sorted order. For each cell, width and spacing design rules are applied to first and second edges of the cell, which may result in movement of the cell and/or adjustment of the cell's width. An adjacent cell adjustment process conforms cells shared points with the adjusted cell. Once the compaction procedure is carried out in a positive x-direction, the coordinates are reversed and it is carried out again in a second pass. The compaction method is performed once for x-direction compaction and once for y-direction compaction. The compaction process is computationally efficient because each cell is linked by the database to its adjacent cells, virtually eliminating the need to search through cells not needed for each design rule check, and because movement of one cell's edges automatically adjusts adjacent cells via their shared edges. The wire minimization embodiment of the invention includes determining whether the second edges have been moved in the second pass, and if so applying the width rules to the first edges to minimize the length of wire represented by the width of the cell having the adjusted edges.

Claims15

Dependent claims

A computer-aided design system for revising a multilayer integrated circuit layout, comprising:

data receiving means for receiving data representing said integrated circuit layout;
a design rule dictionary representing a set of design rules, a first subset of said design rules involving spacing design rules and a second subset of said design rules including width design rules;
a circuit layout database including:
a cell table representing cells, each cell representing a region of an identified layer of said integrated circuit layout, said cell table including cells representing all empty spaces between non-empty regions of each layer of said integrated circuit layout;
edge data representing all edges of all said cells in said cell table, said edge data including point data representing each edge's endpoints such that each point which is an edge endpoint of two or more edges is represented by a single, shared point datum;
each said point datum representing a point location and a move value indicating movement of an edge's endpoint;
adjacent cell data indicating adjacent cell data indicating, for each edge of each cell, which other cell is adjacent said cell at said edge;
circuit layout compaction mechanism, said mechanism including:
a circuit layout compaction procedure for adjusting, in accordance with said design rules represented by said design rule dictionary, said point data in said database so as to adjust said cells' positions and sizes;
wherein each adjustment of said point data for one edge of one cell automatically adjusts a corresponding edge of said other cell adjacent to said one edge by way of their shared point data in said database;
a wire length minimization procedure for minimizing a width of each non-empty cell whose width is not minimal and that meets a predefined criteria;
wherein said wire length minimization procedure readjusts said point data for more than one edge of a selected cell and for those edges adjacent to each readjusted edge;
and
revised circuit layout generation mechanism for generating a revised circuit layout in accordance with said adjusted point data in said database.

11 more elements

A computer readable storage medium for storing data for access by programs being executed on a data processing system including at least one server computer and a plurality of client computers, said medium comprising:

data receiving means for receiving data representing said integrated circuit layout;
a design rule dictionary representing a set of design rules, a first subset of said design rules involving spacing design rules and a second subset of said design rules including width design rules;
a circuit layout database including:
a cell table representing cells, each cell representing a region of an identified layer of said integrated circuit layout, said cell table including cells representing all empty spaces between non-empty regions of each layer of said integrated circuit layout;
edge data representing all edges of all said cells in said cell table, said edge data including point data representing each edge's endpoints such that each point which is an edge endpoint of two or more edges is represented by a single, shared point datum;
each said point datum representing a point location and a move value indicating movement of an edge's endpoint;
adjacent cell data indicating adjacent cell data indicating, for each edge of each cell, which other cell is adjacent said cell at said edge;
circuit layout compaction mechanism, said mechanism including:
a circuit layout compaction procedure for adjusting, in accordance with said design rules represented by said design rule dictionary, said point data in said database so as to adjust said cells' positions and sizes;
wherein each adjustment of said point data for one edge of one cell automatically adjusts a corresponding edge of said other cell adjacent to said one edge by way of their shared point data in said database;
a wire length minimization procedure for minimizing a width of each non-empty cell whose width is not minimal and that meets a predefined threshold criteria;
wherein said wire length minimization procedure readjusts said point data for more than one edge of a selected cell and for those edges adjacent to each readjusted edge;
and
revised circuit layout generation mechanism for generating a revised circuit layout in accordance with said adjusted point data in said database.

11 more elements

A method for compacting an integrated circuit layout in accordance with a specified set of spacing design rules and width design rules, the method being executed by a processor having a memory and controlled by a program stored in the memory and including the steps of:

(1) selecting a first coordinate direction;
(2) storing in said memory a connectivity data structure representing the integrated circuit layout as a set of cells, each said cell being defined as being of a given material or as empty, the data structure including data representing points defining edges and boundaries of said cells;
(3) designating each edge of each cell in having a lower value in the selected coordinate direction as a bottom edge, and designating each edge of each cell having a higher value in the selected coordinate direction as a top edge;
(4) ordering the cells into an sorted cell list in accordance with the first coordinate direction;
(5) assigning to each point of the layout an offset reposition that point at the least-valued location of the layout in the selected coordinate direction;
(6) for each cell of the sorted cell list, selecting that cell as the current cell, and:
for each point on the top edge of the current cell, assigning each point on the top edge the maximum move distance for any points on the top edge;
for each bottom edge of the current cell, applying the spacing design rules to position edges of other cells a minimum allowable distance from an edge of the current cell, and applying the width design rules to position top and bottom edges of the current cell a minimum allowable width from one another;
for each top edge of the current cell, applying the width design rules to position top and bottom edges of the current cell a minimum allowable width from one another, and applying the spacing design rules to position edges of other cells a minimum allowable distance from an edge of the current cell;
(7) recursively adjusting edges of cells sharing points with edges having at least one point that was moved in step 6 to move edges that share points the same distance:
(8) propagating the moves of top edges that were moved in step 6 to other edges having higher-valued positions in the input layout, according to the first coordinate direction, for positioning said other edges the minimum allowable spacing distance from said top edges moved in step 6;
(9) using the move assignments of said top edges to calculate further move assignments for said bottom edges, to maximize the compaction effect on the integrated circuit layout;
(10) reversing the values of the positions of objects in the first coordinate direction such that said top edges are redefined as new bottom edges and said bottom edges are defined as new top edges;
and
(11) using the move assignments of the former bottom edges (new top edges) as adjusted in step 9 to calculate further move assignments for the former top edges (new bottom edges) to maximize the compaction effect on the integrated circuit layout.

12 more elements

A method for revising an integrated circuit layout in accordance with a specified set of spacing design rules and width design rules, the method being executed by a processor having a memory and controlled by a program stored in the memory and including the steps of:

(1) selecting a first coordinate direction;
(2) storing in said memory a connectivity data structure representing the integrated circuit layout as a set of cells, each said cell being defined as being of a given material or as empty, the data structure including data representing points defining edges and boundaries of said cells;
(3) designating each edge of each cell having a lower value in the selected coordinate direction as a bottom edge, and designating each edge of each cell having a higher value in the selected coordinate direction as a top edge;
(4) ordering the cells into an sorted cell list in accordance with the selected coordinate direction;
(5) for each cell of the sorted cell list, selecting that cell as the current cell, and:
applying said spacing and width design rules to each top and bottom edge of said current cell, said application adjusting said edge's position and size;
and
recursively adjusting edges of adjacent cells affected by the application of said design rules to said current cell;
(6) designating each edge of each cell having a lower value in the selected coordinate direction as a top edge, and designating each edge of each cell having a higher value in the selected coordinate direction as a bottom edge;
(7) for each cell of the sorted cell list, selecting that cell as the current cell, and:
(i) determining a position for a bottom edge of said current cell;
(ii) applying said width design rules to a top edge of said current cell in order to position said top edge within a minimum width distance from said bottom edge;
(iii) positioning bottom edges associated with each cell located in front of said current cell in accordance with said width design rules;
and
(iv) adjusting select edges of adjacent cells to said current cell.

12 more elements

Dependencies are inferred from the claim text.

Method and apparatus for compacting integrated circuits with wire length minimization

Life of this patent

Method and apparatus for compacting integrated circuits with wire length minimization

Life of this patent

Abstract

Claims15