Computer-aided design and analysis of circuits and semiconductor – Nanotechnology related integrated circuit design
Reexamination Certificate
1999-03-22
2002-04-09
Nelms, David (Department: 2818)
Computer-aided design and analysis of circuits and semiconductor
Nanotechnology related integrated circuit design
C716S030000, C716S030000
Reexamination Certificate
active
06370673
ABSTRACT:
BACKGROUND OF THE INVENTION
1. Field of the Invention
The present invention relates to the field of electronic design automation (EDA). More specifically, the present invention relates to layout placement of cells within the field of electronic design automation used in the design and fabrication of integrated circuit devices.
2. Related Art
The rapid growth of the complexity of modern electronic circuits has forced electronic circuit designers to rely upon computer programs to assist and automate most steps of the integrated circuit design process. Typical circuits today contain hundreds of thousands or millions of individual pieces or “cells.” In many design architectures, the cells can have variable widths but constant heights or the cells can have variable heights but constant widths. Modern integrated circuit designs are much too large for a circuit designer or even an engineering team of designers to manage effectively by manual techniques. To automate the circuit design and fabrication of integrated circuit devices, electronic design automation (EDA) systems have been developed.
Within the automatic design process, an integrated circuit description is translated, by circuit synthesis processes, from a high level design language (HDL) format into a netlist description. The netlist description (“netlist”) contains technology specific cells that are connected together by wire connections. The cells of the netlist are then placed by computer implemented placement processes that include a coarse placer process (also called a “global” placer). The coarse placer process assigns each cell with a substrate location defined by two dimensional coordinates (x, y). The coarse placer process places the cells in an effort to maintain certain circuit constraints such as: wire length minimization; signal delay minimizations; power constraints and substrate area constraints. The coarse placer process attempts to improve the quality of the integrated circuit design by minimizing the wire lengths between connected cells. The coarse placer process also avoids cell overlap with large obstacles.
However, the cell locations assigned by the coarse placer process are not initially legal locations for the cells because the coarse placer process assigns precise cell coordinates using floating point values. In the actual physical device, cells need to be assigned to locations that align within a matrix of allowable x and y discrete grid lines. Also, the cell locations determined by the coarse placer process may not be legal due to cell-to-cell overlaps or overlaps between cells and small obstacles. As a result of the above, a detailed (also called “fine”) placement process is used on the results of the coarse placer. The detailed placement process yields a legal cell placement that satisfies the following: (1) it aligns all cells to the x and y grid lines; (2) it contains no cell-to-cell overlaps; and (3) it contains no cell-to-obstacle overlaps. The detailed placement process generally does not attempt to improve wire length of the design, rather, it slightly degrades wire length in an effort to arrive at legal cell placements.
FIG. 1A
illustrates a portion
10
of an exemplary cell layout as generated by a coarse placement process. Layout portion
10
contains cells
20
a
-
20
g
having their upper left corners located at floating point coordinate positions that do not necessarily align with the horizontal
12
and vertical
14
lines of the (x, y) grid matrix. Therefore, these initial cell placements are not legal. For instance, assume cell
20
a
is located at (
12
.
34
,
43
.
92
); cell
20
b
is located at (
12
.
24
,
47
.
52
); cell
20
c
is located at (
30
.
19
,
47
.
56
); cell
20
d
is located at (
52
.
34
,
16
.
12
); cell
20
e
is located at (
28
.
56
,
59
.
11
); cell
20
f
is located at (
13
.
89
,
69
.
21
); and cell
20
g
is located at (
39
.
01
,
68
.
32
). These placements from the coarse placer process are then provided to a detailed placer of the prior art which attempts to align the cells with the discrete (x, y) grid lines.
One prior art detailed placer process “snaps” all of the cells to their nearest grid intersection in an attempt to align the cell locations with the grid matrix.
FIG. 1B
illustrates such an output where the cells
20
a
-
20
g
are “snapped” to the nearest grid intersection. For instance, cell
20
c
is snapped to location (
30
,
45
), cell
20
d
is snapped to location (
15
,
50
), cell
20
e
is snapped to location (
25
,
55
), cell
20
f
is snapped to location (
15
,
65
) and so forth. However, cells
20
b
and
20
a
share the same grid location (
10
,
40
) and therefore overlap with each other. This detailed placement process of the prior art has a disadvantage in that many cells, after being snapped to their nearest grid locations, end up overlapping other cells, sometimes causing thousands of overlaps. The problem is severe because when the detailed placer process attempts to move an overlapping cell to another location, it must also check for a possible overlap condition at the new location, and so forth. This process of moving cells, checking for overlapping conditions and moving cells, etc., can take many iterations per cell thereby consuming a relatively large amount of processing time. In an effort to reduce this problem, complex, detailed and time consuming programming processes are introduced which add processing penalties and technical complexities to the detailed placer process.
In addition to taking a relatively large amount of processing time to complete, this prior art method of detailed placement also causes some cells to be moved quite a distance from their original position in order to locate a non-overlapping site. This is especially true for high density cell layouts. Another disadvantage of this prior art detailed process is that it does not fully take advantage of the two dimensional nature of the detailed placement problem and thereby generates cell placements that are not typically uniform in nature. Another disadvantage of this detailed cell placement process is that it does not easily or readily deal with cell obstructions. In order to cope with cell obstructions in the layout area, complex and detailed heuristics need to be incorporated into the prior art detailed placement process.
Accordingly, what is needed is a detailed placer process that yields grid aligned legal coordinates but does not consume a relatively long processing period to compute. What is also needed is a detailed placer process that does not move the cells very far from their original positions as determined from the coarse placer process. What is needed further is a detailed placer process that yields a relatively uniform placement while avoiding cell-to-cell overlaps and avoiding cell-to-obstruction overlaps. The present invention provides these advantages. These and other advantages of the present invention not specifically mentioned above will become clear within discussions of the present invention presented herein.
SUMMARY OF THE INVENTION
A method and system are described herein for high speed detailed placement of cells within an integrated circuit design. The novel detailed placement system receives a set of cells of an integrated circuit design where the cells have undergone coarse placement. Cells have variable width but the same height (or vice-versa in other embodiments). As a result of coarse placement, the cells are each assigned an initial coordinate position, e.g., using floating point precision values. During detailed placement, the cell coordinates are assigned to non-overlapping positions within x-axis and y-axis grid lines.
The detailed placement process of the present invention sorts the cells based on their coordinate values along a first axis, e.g., their x-axis coordinates. This sort order dictates the cell placement order during the detailed placement process. In one embodiment, sort order preference is given to the wider cells to place them earlier in the placement process. Preference can be given, in one imple
Auduong Gene N.
Nelms David
Synopsys Inc.
Wagner, Murabito&Hao LLP
LandOfFree
Method and system for high speed detailed placement of cells... does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Method and system for high speed detailed placement of cells..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Method and system for high speed detailed placement of cells... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-2892891