Method and apparatus for compacting integrated circuits with wire length minimization

Claim 1

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.

Claim 9

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.

Claim 10

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.

Claim 15

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.

Claim 16

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.