Computer-aided design and analysis of circuits and semiconductor – Nanotechnology related integrated circuit design
Reexamination Certificate
2002-12-11
2004-06-29
Smith, Matthew (Department: 2825)
Computer-aided design and analysis of circuits and semiconductor
Nanotechnology related integrated circuit design
C716S030000
Reexamination Certificate
active
06757883
ABSTRACT:
FIELD OF THE INVENTION
This invention relates to integrated circuit (IC) fabrication, and particularly to estimating free space in a routed design of an IC chip.
BACKGROUND OF THE INVENTION
Chip fabrication processes often require a uniform distribution of metal or polysilicon on layers of a chip. Metal wires and polysilicon features on a layer in a routed chip design are often concentrated in groups, leaving spaces on the layer. Consequently, material filling is a post-routing step in the chip design that requires that some of the unoccupied free space in the design be filled with “dummy” material to ensure a uniform distribution of the material over the layer. The distribution of dummy material requires identifying and storing representations of free space in the design.
Prior to the present invention, identification of free space on a layer of a routed IC design was accomplished by a grid-subtraction algorithm, which removed a grid location from a space if the grid location intersects a database object. Using the grid-subtraction algorithm, a uniform x-y grid of a layer of the routed design was created. Each grid cell was initially assumed to be a free-space cell representing a possible location for adding dummy metal. A database is created during chip design process, which defines polygons representing metal wires, pins, vias, etc. in the layout. The grid-subtraction algorithm operates on the polygons in the database to delete each free-space cell that intersects with a database polygon. Selection of the actual shape and location for metal filling is then determined from the grid coordinates of the free-space cells and the routed design.
One disadvantage of the grid-subtraction algorithm is that it is computationally intensive. More particularly, the uniform size of the grid cells usually resulted in numerous contiguous free-space grid cells. Contiguous cells could be merged, but merging is a computationally intensive operation. Alternatively, the plural contiguous free-space cells could be processed as individual cells, but that resulted in extensively long GDS2 files for the layout. Long GDS2 files require computationally intensive filling and design checking operations, and subsequent checking and fabrication operations are less efficient. Accordingly, there is a need for a process and apparatus for estimating free space on layers of a routed IC design that is more efficient and less computationally intensive and that is useful with polysilicon layers as well as metal layers.
SUMMARY OF THE INVENTION
A first embodiment of the invention is a process for estimating free space on a layer of a routed integrated circuit design. A hierarchical search tree, such as a quadtree or octree, contains nodes defining respective rectangular spaces on the layer of the design and polygons representing free space within the respective rectangular space. Feature polygons representing occupied space within the rectangular space are subtracted from the free space polygon in the tree node. The free spaces are summed to estimate the free space on the layer.
In some embodiments, a database defines the feature polygons on the layer. A first node is created in the search tree defining a rectangular space of the layer. Initially the free space polygon in the node is set equal to the rectangular space. Feature polygons from the database are considered sequentially such that if a polygon intersects a node of the tree, its definition is subtracted from the free space polygon defined by the node. A cost factor is identified for the node, and the process is repeated with additional polygons until either the cost factor exceeds a predetermined maximum value or no further polygons exist in the database.
In some embodiments, if the cost factor for a node exceeds the predetermined value, the node is fractured into child nodes, each defining a rectangular space that is a respective portion of the parent rectangular space. The tree recursively divides the rectangular space into quadrants, and the polygon definitions in the parent node are assigned to respective child nodes. The process is repeated for each child node until either the cost factor for each node is not greater than the predetermined maximum value or a dimension of the rectangular space of the child node reaches a predetermined minimum value.
A second embodiment of the invention is a computer readable program containing computer readable code that causes a computer to define a hierarchical search tree and carry out the processes of the invention on a database or file defining at least a layer of the routed integrated circuit chip.
REFERENCES:
patent: 4468728 (1984-08-01), Wang
patent: 4918614 (1990-04-01), Modarres et al.
patent: 5625564 (1997-04-01), Rogoyski
patent: 5963728 (1999-10-01), Hathaway et al.
“Improved Quadtree Algorithm Based on Joint Coding for Piecewise Smooth Image Compression” by R. Shukla et al., for the Swiss National Science Foundation, date unknown (4 pages).
Chip-Level CMP Modeling and Smart Dummy for HDP and Conformal CVD Films; 1999 CMP-MIC Conference; pp 120-127, Feb. 11-12, 1999;1999 IMIC-400P/99/0120—Author(s)—George Y. Liu, et al.
Raman Santhanakris
Shrowty Vikram
Lin Sun James
LSI Logic Corporation
Smith Matthew
Westman Champlin & Kelly
LandOfFree
Estimating free space in IC chips does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Estimating free space in IC chips, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Estimating free space in IC chips will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-3294217