Computer-aided design and analysis of circuits and semiconductor – Nanotechnology related integrated circuit design
Reexamination Certificate
2001-01-24
2003-12-30
Garbowski, Leigh M. (Department: 2825)
Computer-aided design and analysis of circuits and semiconductor
Nanotechnology related integrated circuit design
C716S030000
Reexamination Certificate
active
06671859
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 techniques for cell placement and other optimizations used in the design and fabrication of integrated circuit devices.
2. Related Art
An electronic design automation (EDA) system is a computer software system used for designing integrated circuit (IC) devices. The EDA system typically receives one or more high level behavioral descriptions of an IC device (e.g., in HDL languages like VHDL, Verilog, etc.), as represented by HDL
12
of
FIG. 1
, and translates this high level design language description into netlists of various levels of abstraction. At a higher level of abstraction, a generic netlist is typically produced based on technology independent primitives. The generic netlist can be translated into a lower level technology-specific netlist based on a technology-specific library that has gate-specific models for timing and power estimation. A netlist describes the IC design and is composed of nodes (elements) and edges, e.g., connections between nodes, and can be represented using a directed cyclic graph structure having nodes which are connected to each other with signal lines. A single node can have multiple fan-ins and multiple fan-outs. The netlist is typically stored in computer readable media within the EDA system and processed and verified using many well known techniques. One result is a physical device layout in mask form which can be used to directly implement structures in silicon to realize the physical IC device, step
28
of FIG.
1
.
The rapid growth of the complexity of modem electronic circuits has forced electronic circuit designers to rely upon computer programs to assist or automate most steps of the design process. Typical circuits today contain hundreds of thousands or millions of individual pieces or “cells.” Such a design is much too large for a circuit designer or even an engineering team of designers to manage effectively manually.
FIG. 1
shows a typical system
10
of computer programs used to automate the design of electronic circuits. Within system
10
, the designer first produces a high-level description
12
of the circuit in a hardware description language such as Verilog or VHDL. Then this high-level description
12
is converted into a netlist
16
a
using a computer implemented synthesis process
14
such as a the “Design Compiler” by Synopsys of Mountain View, Calif. A netlist
16
a
is a description of the electronic circuit which specifies what cells compose the circuit and which pins of which cells are to be connected together using wires (“nets”). Importantly, the netlist
16
a
does not specify where on a circuit board or silicon chip the cells are placed or where the wires run which connect them together. Determining this geometric information is the function of an automatic placement process
18
and an automatic routing process
22
, both of which are shown in FIG.
1
and are typically computer programs.
Next, the designer supplies the netlist
16
a
into the computer implemented automatic cell placement process
18
of FIG.
1
. The automatic placement computer program
18
finds a location for each cell on a circuit board or silicon chip. The locations are specified, typically, in two dimensional spatial coordinates, e.g., (x, y) coordinates, on the circuit board or silicon chip. The locations are typically selected to optimize certain objectives such as wire length, wire routibility, circuit speed, circuit power consumption, and/or other criteria, subject to the condition that the cells are spread evenly over the circuit board or silicon chip and that the cells do not overlap with each other. The output of the automatic cell placement process
18
includes a data structure
20
including the (x, y) position for each cell of the IC design. In some cases, the netlist
16
a
is modified and a new netlist
16
b
is generated. In other cases, the netlist
16
b
is the same as netlist
16
a.
Next, the designer supplies the netlist
16
a
and the cell location data structure
20
, generated by the placement program
18
, to a computer implemented automatic wire routing process
22
. This computer program
22
generates wire geometry within data structure
24
. The wire geometry data structure
24
and cell placement data structure
20
together are used to make the final geometric database needed for fabrication of the circuit as shown by process
28
.
FIG. 2
illustrates the subprocesses of the automatic placement process
18
in more detail. Typically, placement is done in 2 steps including a first coarse placement process
30
, then detailed a placement process
34
. The coarse placement process
30
finds approximate cell locations which optimize the desired metrics and spreads cells evenly across the silicon chip or circuit board. In the output data structure
32
, some cells still overlap and no cells are in legal site locations, so the coarse placement
30
needs to be legalized before the circuit can be fabricated. The detailed placement
34
inputs the data structure
32
output by the coarse placement
32
and generates the detailed placement
20
, discussed in
FIG. 1
, which does not have overlap and all are located on legal sites.
FIG. 3A
shows an example coarse placement
40
a
including the positions of cells A-I. The detailed placer process
34
changes cell locations a small amount in order to make the placement able to be manufactured. Generally, it is best to move cells as small a distance as possible to avoid disturbing the coarse placement result. Some detailed placer programs also attempt to further optimize the metrics used to drive coarse placement. An example detailed placement
40
b
is shown. in
FIG. 3B
illustrating the new locations of cells A-I. As shown, the cells A-I in
FIG. 3B
are more aligned along the horizontal rows.
Other prior art methods of finding coarse placement are described. The early methods of performing coarse placement used some variety of simulated annealing as described in a journal article entitled, “Optimization by Simulated Annealing,” by S. Kirkpatrick, C. Gelatt, M. Vecchi, which appeared in “Science,” May 13, 1983, Volume 220, Number 4598, on pages 671-680. Simulated annealing is a general method of finding good solutions to complex combinatorial optimization problems with a wide variety objective functions. Simulated annealing works by proposing random small changes to the current placement and accepting the changes with probability as shown by equation (1) below:
probability of acceptance=1, if &Dgr;objective is≦to 0
e
−(&Dgr;objective/temperature)
, if &Dgr;objective>0 (1)
In operation, changes that are not accepted are rejected, and undone. A control parameter “temperature” is used to control the number of acceptances. Temperature starts high and decreases toward 0 as the optimization proceeds. The optimization concludes when the temperature reaches 0.
Simulated annealing has many advantages. Simulated annealing based placement algorithms can combine both coarse and detailed placement in a single step. It can be shown (e.g., in a conference paper entitled, “Convergence of the Annealing Algorithm,” by M. Lundy and A. Mees, which appeared in “Proceedings of the Simulated Annealing Workshop,” 1984) that simulated annealing converges to an optimal solution with probability 1, if run for a long enough amount of time. Simulated annealing can optimize a wide variety of objective functions.
However, simulated annealing has more recently lost favor as a method of coarse placement because of the following disadvantages. First, for circuits larger than a few thousand cells, simulated annealing does not achieve a good result unless run for a prohibitively long amount of time. Circuits today have hundreds of thousands or millions of cells. Second, for various technical reasons, simulated annealing is not able to optimize circuit timing very effectively. As ci
Donelly Ross
Naylor William C.
Sha Lu
Bever Hoffman & Harms LLP
Garbowski Leigh M.
Harms Jeanette S.
Synopsys Inc.
LandOfFree
Non-linear optimization system and method for wire length... does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Non-linear optimization system and method for wire length..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Non-linear optimization system and method for wire length... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-3098247