US 5,515,293 A · Method and apparatus for generating a linked data structure for integrated circuit layout

Abstract

A method an apparatus for generating and storing a connectivity data structure representing a circuit layout. The data structure includes a list of pointers representing cells of the layout, and each cell pointer points to an entry in a cell table. The cell table entries include a field pointing to a cell types table, and another entry pointing to a boundary table, which itself stores fields identifying edges and adjacent cells. The edge entries point to an edge table including fields representing the endpoints of the edge. The endpoint fields point to a point table including coordinates of the endpoint in question and a move field identifying whether the edge has been moved in a layout modification routine. The method of generating this data structure involves entering a layout, adding new cells one by one, and when each new cell is added, generating entries for all the cells, boundaries, edges and edge endpoints of the new cell, and storing them in the data structure. As the cells are entered, they are fractured to generate horizontal edges and convex shapes, and once all cells are entered, cells of like materials are recombined while maintaining convexity. Links are generated for cells connected across layers of the layout. The apparatus of the layout is a computer system including a inputs and a CPU controlling a memory storing a program for generating all of the objects in the data structure, allowing simple user input of graphical objects representing the objects in the circuit layout.

Claims12

Dependent claims

A method executed by a computer under the control of a program, said computer including a memory for storing said program, said method comprising the steps of:

(1) receiving in said computer a list of cells representing a circuit layout, each cell having a specified type;
(2) storing in said memory a cell record in a cell table for each received cell, each said cell record including a boundary pointer pointing to a boundary record in a boundary table, each boundary record including an adjacent cell pointer, an edge pointer and a next entry pointer for the next record in the boundary table, the adjacent cell pointer pointing to a cell adjacent to the cell for the current boundary record, if any, and the edge pointer pointing to an edge record in an edge table;
(3) selecting a cell as the current cell;
(4) selecting an edge of the current cell as the current edge;
(5) generating a division line along the current edge;
(6) subdividing any edges stored in the data structure that are intersected by the generated division line into smaller edges, and generating and storing one said edge record for each of the smaller edges;
(7) repeating steps 4-6 until each edge of the current cell has been processed by said steps 4-6;
(8) repeating steps 3-7 until each cell has been processed by said steps 3-7;
and
(9) storing in each edge record a first endpoint entry and a second endpoint entry, the first endpoint entry including a pointer to a point record in a point table, each point record including entries representing coordinates of the point represented by the point record.

7 more elements

A computer readable memory that can be used to direct a computer to function in a specified manner, comprising:

cell data stored in said memory, said cell data including:
(1) a list of cells representing a circuit layout, each cell having a specified type,
(2) a cell record in a cell table for each cell of said list of cells, each said cell record including a boundary pointer pointing to a boundary record in a boundary table, each boundary record including an adjacent cell pointer, an edge pointer and a next entry pointer for the next record in the boundary table, the adjacent cell pointer pointing to a cell adjacent to the cell for the current boundary record, if any, and the edge pointer pointing to an edge record in an edge table;
and
executable instructions stored in said memory, said executable instructions including:
(3) instructions to select a cell as the current cell,
(4) instructions to select an edge of the current cell as the current edge,
(5) instructions to produce a division line along the current edge,
(6) instructions to subdivide any edges stored in the data structure that are intersected by the generated division line into smaller edges and thereafter store one said edge record for each of the smaller edges,
(7) loop control instructions for repeating the execution of instructions (4)-(6) until each edge of the current cell has been processed by instructions (4)-(6),
(8) loop control instructions for repeating the execution of instructions (3)-(7) until each cell has been processed by instructions (3)-(7), and
(9) instructions to store in each edge record a first endpoint entry and a second endpoint entry, the first endpoint entry including a pointer to a point record in a point table, each point record including entries representing coordinates of the point represented by the point record.

9 more elements

Dependencies are inferred from the claim text.

Method and apparatus for generating a linked data structure for integrated circuit layout

Life of this patent

Method and apparatus for generating a linked data structure for integrated circuit layout

Life of this patent

Abstract

Claims12