Title: Method of incremental recharacterization to estimate performance of integrated disigns
Abstract: A technique to verify, evaluate, and estimate the performance of an integrated circuit is embodied in a computer software program that is executable by a computer system. The technique accurately estimates of the performance (e.g., transient delays) of an integrated circuit, and has fast execution times. The technique includes an incremental recharacterization feature where only portions of the design which have been changed or are new or different will need to be recharacterized during subsequent runs of the software. Portions of the design which are the same need not be recharacterized, and results for those portions from a previous run (stored in a database) are used. This saves execution time since the performance recharacterization or evaluation process is generally more time consuming than a database look up. The technique is applicable to small circuits having relatively few transistors, and especially well suited for integrated circuits having millions of transistors and components. The technique handles the effects of deep-submicron integrated circuit technology.
Patent Number: 6,851,095 Issued on 02/01/2005 to Srinivasan, et al.
| Inventors:
|
Srinivasan; Arvind (San Jose, CA);
Chaudhri; Haroon (Berkeley, CA)
|
| Assignee:
|
Magma Design Automation, Inc. (Santa Clara, CA)
|
| Appl. No.:
|
999222 |
| Filed:
|
November 24, 2001 |
| Current U.S. Class: |
716/4; 703/13; 716/7 |
| Intern'l Class: |
G06F 017/50 |
| Field of Search: |
716/1-11,18
703/13-15,19
|
References Cited [Referenced By]
U.S. Patent Documents
| 5305229 | Apr., 1994 | Dhar.
| |
| 5331568 | Jul., 1994 | Pixley | 716/3.
|
| 5416721 | May., 1995 | Nishiyama et al.
| |
| 5440720 | Aug., 1995 | Baisuck et al. | 703/2.
|
| 5533148 | Jul., 1996 | Sayah et al. | 382/240.
|
| 5553008 | Sep., 1996 | Huang et al.
| |
| 5640328 | Jun., 1997 | Lam.
| |
| 5757655 | May., 1998 | Shih et al. | 716/2.
|
| 6058256 | May., 2000 | Mellen et al. | 713/12.
|
| 6138266 | Oct., 2000 | Ganesan et al.
| |
| 6249898 | Jun., 2001 | Koh et al.
| |
Other References
Bryant, R.E., "Algorithmic Aspects of Symbolic Switch Network Analysis,"
IEEE Trans. Computer-Aided Design, vol. CAD-6, No. 4, Jul. 1987, pp.
618-633.
Bryant, R.E., "Graph-Based Algorithms for Boolean Function Manipulation,"
IEEE Trans. Comput., vol. C-35, Aug. 1986, pp. 677-691.
Appenzeller, David P. et al., "Formal Verification of a PowerPC.TM.
Microprocessor," Report RC (19971), IBM T.J. Watson Research Center,
Yorktown Heights, NY 10598, Mar. 1995, pp. 1-6.
|
Primary Examiner: Garbowski; Leigh M.
Attorney, Agent or Firm: Townsend and Townsend and Crew LLP
Parent Case Text
CROSS-REFERENCES TO RELATED APPLICATIONS
This application is a division of U.S. patent application Ser. No.
09/357,940, filed Jul. 21, 1999, now U.S. Pat. No. 6,499,129 issued Dec.
24, 2002, which claims the benefit of U.S. provisional patent application
Ser. No. 60/093,830, filed Jul. 22, 1998. The above applications, in their
entirety as filed, and all the references cited in this application are
incorporated by reference.
Claims
What is claimed is:
1. A method of estimating the performance of an integrated circuit design
comprising:
making a first estimation of the transient performance of the integrated
circuit design;
during the first estimation of the transient performance of the integrated
circuit design, creating a database to store estimated transient
performance results for the integrated circuit design;
making a second estimation of the transient performance of the integrated
circuit design; and
during the second estimation of the transient performance of the integrated
circuit design, reading the database and using the stored estimated
transient performance results of at least a portion of the integrated
circuit design, wherein the transient performance results for the portion
of the integrated circuit design were estimated during the first
estimation.
2. The method of claim 1 wherein the stored estimated transient performance
results comprise circuit simulation results, partitioning information,
transient delays, slope information, or simulation data.
3. The method of claim 1 wherein reading the database comprises:
loading a first partition stored in the database and the stored estimated
transient performance results corresponding to the first partition,
determined during the first estimation of the performance of the
integrated circuit design;
comparing a second partition obtained during the second estimation of the
transient performance of the integrated circuit design to the first
partition; and
if the first and second partitions match, using the stored estimated
transient performance results for the first partition as the estimated
performance results for the second partition, wherein calculation of the
estimated transient performance results for the second partition is
avoided.
4. The method of claim 3 wherein the first partition matches the second
partition if:
circuit topologies between the first and second partitions are the same;
input waveform coefficients for the first and second partitions are within
a constant a of each other;
sizes of devices for the first and second partitions are within a constant
b of each other; and
any output load devices for the first and second partitions are within a
constant c of each other.
5. The method of claim 4 wherein a, b, and c are user-defined tolerance
parameters.
6. The method of claim 3 wherein a partition comprises a strongly coupled
component.
7. The method of claim 3 further comprising:
if the first and second partitions do not match, calculating new estimated
transient performance results for the second partition; and
storing the second partition and new estimated transient performance
results in the database, wherein the new estimated transient performance
results may be used during a third estimation of the transient performance
of the integrated circuit design.
8. The method of claim 7 wherein calculating new estimated performance
results comprises:
generating vectors for the second partition;
selecting a plurality of vectors to cause a transition at an output of the
second partition; and
simulating the performance of the second partition using the plurality of
vectors.
9. The method of claim 1 wherein the database is stored using a disk drive.
10. The method of claim 1 wherein the first estimation is performed and
completed using a computer before the second estimation begins.
11. The method of claim 1 wherein making the first estimation comprises:
generating vectors for a partition of integrated circuit design;
selecting a plurality of vectors to cause a transition at an output of the
second partition; and
simulating the transient performance of the partition using the plurality
of vectors.
12. The method of claim 1 wherein the stored estimated transient
performance results comprises slope information including rate of output
waveform rise or fall time.
13. The method of claim 1 wherein the first estimate of the transient
performance of the integrated circuit design comprises the sum of the
first estimates of the transient performance of the first and second
circuit blocks.
14. The method of claim 1 wherein the second estimate of the transient
performance of the integrated circuit comprises the sum of the second
estimate of the transient performance of the first circuit block and the
first estimate of the transient performance of second circuit block from
the database.
15. A method of estimating the performance of an integrated circuit design
comprising:
making a first estimation of the performance of the integrated circuit
design;
during the first estimation of the performance of the integrated circuit
design, creating a database to store estimated performance results for the
integrated circuit design;
making a second estimation of the performance of the integrated circuit
design; and
during the second estimation of the performance of the integrated circuit
design, reading the database and using the stored estimated performance
results of at least a portion of the integrated circuit design, wherein
the performance results for the portion of the integrated circuit design
was estimated during the first estimation,
wherein the stored estimated performance results comprises slope
information including rate of output waveform rise or fall time.
16. A method of evaluating the performance of an integrated circuit design
comprising:
making a first estimate of the transient performance of the integrated
circuit design comprising making a first estimate of the transient
performance of a first circuit block of the integrated circuit design and
making a first estimate of the transient performance of a second circuit
block of the integrated circuit design;
storing the first estimates of the transient performance of the first and
second circuit blocks in a database; and
making a second estimate of the transient performance of the integrated
circuit design comprising reading the database with the stored first
estimates of the transient performance of the first and second circuit
blocks, making a second estimate of the transient performance of the first
circuit block of the integrated circuit design, and using the first
estimate of the transient performance of the second circuit block stored
in the database.
17. The method of claim 16 further comprising:
after storing the first estimates of the transient performance of the first
and second circuit blocks in the database, making an alteration to the
second circuit block of the integrated circuit design.
18. The method of claim 16 further comprising:
during the making of the second estimate of the transient performance of
the integrated circuit design, determining whether the first and second
circuit blocks have been altered.
19. The method of claim 16 further comprising:
during the making of the second estimate of the transient performance of
the integrated circuit design, determining that the second circuit block
is substantially the same as the second circuit block during the first
estimate of the transient performance of the integrated circuit.
20. A method of evaluating the performance of an integrated circuit design
comprising:
making a first estimate of the performance of the integrated circuit design
comprising making a first estimate of the performance of a first circuit
block of the integrated circuit design and making a first estimate of the
performance of a second circuit block of the integrated circuit design;
storing the first estimates of the performance of the first and second
circuit blocks in a database; and
making a second estimate of the performance of the integrated circuit
design comprising reading the database with the stored first estimates of
the performance of the first and second circuit blocks, making a second
estimate of the performance of the first circuit block of the integrated
circuit design, and using the first estimate of the second circuit block
stored in the database;
wherein the first estimate of the performance of the integrated circuit
design comprises the sum of the first estimates of the performance of the
first and second circuit blocks.
21. A method of evaluating the performance of an integrated circuit design
comprising:
making a first estimate of the performance of the integrated circuit design
comprising making a first estimate of the performance of a first Circuit
block of the integrated circuit design and making a first estimate of the
performance of a second circuit block of the integrated circuit design;
storing the first estimates of the performance of the first and second
circuit blocks in a database; and
making a second estimate of the performance of the integrated circuit
design comprising reading the database with the stored first estimates of
the performance of the first and second circuit blocks, making a second
estimate of the performance of the first circuit block of the integrated
circuit design, and using the first estimate of the second circuit block
stored in the database;
wherein the second estimate of the performance of the integrated circuit
comprises the sum of the second estimate of the performance of the first
circuit block and the first estimate of the second circuit block from the
database.
22. A method of estimating the performance of an integrated circuit design
comprising:
making a first estimation of the performance of the integrated circuit
design;
during the first estimation of the performance of the integrated circuit
design, creating a database to store estimated performance results for the
integrated circuit design;
making a second estimation of the performance of the integrated circuit
design; and
during the second estimation of the performance of the integrated circuit
design, reading the database and using the stored estimated performance
results of at least a portion of the integrated circuit design, wherein
the performance results for the portion of the integrated circuit design
were estimated during the first estimation, and the reading of the
database further comprises:
loading a first partition stored in the database and the stored estimated
performance results for the first partition, determined during the first
estimation of the performance of the integrated circuit design;
comparing a second partition obtained during the second estimation of the
performance of the integrated circuit design to the first partition; and
if the first and second partitions match, using the stored estimated
performance results for the first partition as the estimated performance
results for the second partition, wherein calculation of the estimated
performance results for the second partition is avoided,
wherein the first partition matches the second partition if:
circuit topologies between the first and second partitions are the same;
input waveform coefficients for the first and second partitions are within
a constant a of each other;
sizes of devices for the first and second partitions are within a constant
b of each other; and
any output load devices for the first and second partitions are within a
constant c of each other.
23. The method of claim 22 wherein a, b, and c are user-defined tolerance
parameters.
24. The method of claim 22 wherein a partition comprises a strongly coupled
component.
25. A method of estimating the performance of an integrated circuit design
comprising:
making a first estimation of the performance of the integrated circuit
design;
during the first estimation of the performance of the integrated circuit
design, creating a database to store estimated performance results for the
integrated circuit design;
making a second estimation of the performance of the integrated circuit
design; and
during the second estimation of the performance of the integrated circuit
design, reading the database and using the stored estimated performance
results of at least a portion of the integrated circuit design, wherein
the performance results for the portion of the integrated circuit design
were estimated during the first estimation,
wherein making the first estimation comprises:
generating vectors for a partition of integrated circuit design;
selecting a plurality of vectors to cause a transition at an output of the
second partition; and
simulating the performance of the partition using the plurality of vectors.
Description
BACKGROUND OF THE INVENTION
The present invention relates to the field of electronic design automation
(EDA) software, and more specifically, to techniques of verifying,
evaluating, and estimating the performance of integrated circuits.
Integrated circuit technology is a marvel of the modem age. Integrated
circuits are used in many applications such as computers, consumer
electronics, networking, and telecommunications. There are many types of
integrated circuits including microprocessors, microcontrollers,
application specific integrated circuits (ASICs), gate arrays,
programmable logic devices (PLDs), field programmable gate arrays (FPGAs),
dynamic random access memories (DRAMs), static random access memories
(SRAMs), erasable programmable read only memories (EPROMs), electrically
erasable programmable read only memories (EEPROMs), and Flash memories.
Integrated circuits are also sometimes referred to as "chips."
Integrated circuit technology continues to rapidly advance. Automation
tools are needed to simplify and expedite the task of designing an
integrated circuit. It is important to be able to accurately predict or
estimate the performance of an integrated circuit before the integrated
circuit is fabricated. Techniques are needed to provide accurate, fast
estimates of the performance of an integrated circuit.
As semiconductor processing techniques continue to improve, the performance
of integrated circuits also continues to improve. Deep-submicron
integrated circuit technology has enabled commercial multimillion
transistor commercial integrated circuits operating at, for example, 500
megahertz. High clock frequencies require the ability to reliably analyze
the performance of circuits with little tolerance for error. A 10 percent
tolerance in a performance estimate of a 500 megahertz design equates to a
margin of 200 picoseconds, which is 0.200 nanoseconds. In other words,
there is little room for error in performance estimation.
In addition to accuracy, capacity, and speed are also important
considerations for any performance estimation technique. For example,
time-to-market pressures demand performance analysis tools with the
ability to obtain an accurate snapshot of the performance of a
10-million-transistor design within a day so that system architects can
make meaningful architectural tradeoffs without having to wait for days to
obtain an accurate result.
As can be seen, techniques are needed to predict and estimate the
performance of integrated circuits, especially fast and efficient
techniques that provide accurate results for integrated circuit designs
with a large number of transistors.
SUMMARY OF THE INVENTION
The present invention provides a technique for the performance
verification, evaluation, and estimation of integrated circuits. In an
embodiment, the technique of the present invention is embodied in a
computer software program that is to be executed by a computer system. In
particular, the technique facilitates accurate estimates of the
performance (e.g., transient delays) of an integrated circuit and has fast
execution times. Although applicable to small circuits having relatively
few transistors, the technique is especially suited for integrated
circuits having millions of transistors and components.
The technology of the present invention is broadly applicable to custom,
semicustom, and high-performance integrated circuits. The present
invention may be used to accurately estimate the performance of all the
paths of an integrated circuit. When used in designs operating in the 250
megahertz to 1 gigahertz range, and greater, the software of present
invention can provide results within a design tolerance of about two
percent.
Further, the present invention handles the complexities of integrated
circuit technology, including deep-submicron effects. To achieve such
tight tolerances, the performance estimation technique handles the
deep-submicron effects of RC-interconnect and transistor interaction,
cross-coupling capacitance, simultaneous-switching, and waveform shape.
These effects are dynamic in nature and traditional techniques of static
transistor-level path analysis or library-based approaches cannot
incorporate these dynamic effects. The present invention provides
significantly more accurate performance estimates for deep-submicron
designs compared to other techniques such as static path analysis.
Since the present invention uses a dynamic simulation approach, it is able
to incorporate cross-coupling capacitance, simultaneous-switching, and
waveform shape effects with results that are comparable to Spice-level
simulation. The present invention also produces fewer false paths with
resulting savings in designer time and effort. A divide-and-conquer
approach enables the present invention to deal with very large designs,
with turnaround times of under a day for 10-million-transistor designs.
In an embodiment of the present invention, the performance of an integrated
circuit is estimated by partitioning a netlist into strongly coupled
components (SCCs). A plurality of vectors is generated for each of the
strongly coupled components. Strongly driven nodes are determined for each
SCC. Vector pairs are sequenced and accurate simulation is performed on
each strongly coupled component. The result is an accurate estimate of the
performance of the integrated circuit, covering all the paths. Moreover,
strongly coupled components and the simulation results obtained during a
first execution of software of the present invention are saved in a
database. During subsequent executions, these saved strongly coupled
components and the simulation results are reused for those strongly
coupled components that are unchanged, saving considerable time.
Other aspects of the present invention include tighter integration between
timing analysis and characterization by including Boolean information and
automatic elimination of global (block-level) false paths.
In an embodiment, the invention is a method of evaluating the performance
of an integrated circuit. A netlist or circuit description is partitioned
into strongly coupled components. A number of vectors is generated for the
strongly coupled components. The strongly driven nodes are determined.
Stimulus is generated for the strongly coupled components. A strongly
coupled component includes a first channel-connected component and a
second channel-connected component. The first channel-connected component
influences a Boolean output of the second channel-connected component, and
the second channel-connected component influences a Boolean output of the
first channel connected component. A strongly driven node includes a
logical element driving the node with a drive strength greater than
another logical element driving the same node.
In another embodiment, the invention is a computer program product
including a computer usable medium with computer readable code for causing
an evaluation of the performance of an integrated circuit. The computer
program product includes computer readable code devices configured to
cause a computer to effect partitioning a netlist into strongly coupled
components; computer readable code devices configured to cause a computer
to effect generating a plurality of vectors for the strongly coupled
components; and computer readable code devices configured to cause a
computer to effect determining strongly driven nodes.
The invention is further a method of estimating the performance of an
integrated circuit design including selecting a circuit block of the
integrated circuit design. The circuit block may be described in a Spice
or netlist format. A logic function is obtained for a node of the circuit
block. In a specific embodiment, the logic function includes four
subfunctions f0, f1, f0', and f1'. Using the logic function, a set of
vectors is determined that switch or transition the logic function at the
node. A table is formed including the set of vectors.
In a further embodiment, the invention is a method of estimating the
performance of an integrated circuit design including making a first
estimation of the performance of the integrated circuit design. During the
first estimation of the performance of the integrated circuit design, a
database is created to store estimated performance results for the
integrated circuit design. A second estimation of the performance of the
integrated circuit design is made. During the second estimation of the
performance of the integrated circuit design, the database is read. The
stored estimated performance results from the database of at least a
portion of the integrated circuit design are used, where the performance
results for the portion of the integrated circuit design was estimated
during the first estimation.
The invention includes a method of estimating the performance of an
integrated circuit design including selecting a circuit block of the
integrated circuit design. A logic function for a node of the circuit
block is obtained. Using the logic function, a set of vectors is
determined that will switch the logic function at the node. A table
including the set of vectors is formed.
The invention includes a method of estimating the performance of an
integrated circuit design including dividing the integrated circuit design
into channel-connected components, where a channel-connected component
includes nodes and transistors reachable by tracing source-drain
connections of the transistors. Channel-connected components are
identified that are connected in a feedback loop, where a feedback loop of
channel-connected components includes an output of a first
channel-connected component driving an input of a second channel-connected
component and an output of the second channel-connected component driving
an input of the first channel-connected component. Channel-connected
components connected in a feedback loop are merged together to form first
strongly coupled components.
Other objects, features, and advantages of the present invention will
become apparent upon consideration of the following detailed description
and the accompanying drawings, in which like reference designations
represent like features throughout the figures.
BRIEF DESCRIPTION OF THE DRAWINGS
FIG. 1 shows a system of the present invention of estimating the
performance of an integrated circuit;
FIG. 2 shows a system block diagram of a computer system used to execute
the software of the present invention;
FIG. 3 shows a flow diagram for the design of an integrated circuit;
FIG. 4A shows a flow diagram of a technique of performance estimation of
the invention;
FIG. 4B shows a more detailed flow diagram of the technique of performance
estimation of the invention;
FIG. 5 shows a channel-coupled circuit;
FIG. 6 shows another channel-coupled circuit;
FIG. 7 shows a strongly coupled circuit;
FIG. 8 shows another strongly coupled circuit;
FIG. 9 shows a multiplexer circuit as an example of a strongly coupled
component;
FIG. 10 shows a circuit description partitioned into strongly coupled
components;
FIG. 11 shows a waveform represented using a set of coefficients;
FIG. 12 shows a multiplexer circuit with output functions that can be
handle using don't care expansion; and
FIG. 13 shows a strongly coupled circuit where logic functions are to be
determined at a node of the circuit.
DETAILED DESCRIPTION
A portion of the disclosure of this patent document contains material which
is subject to copyright protection. The copyright owner has no objection
to the facsimile reproduction by anyone of the patent document or the
patent disclosure, as it appears in the Patent and Trademark Office patent
file or records, but otherwise reserves all copyright rights whatsoever.
FIG. 1 shows a system of the present invention for estimating the
performance of an integrated circuit. FIG. 1 may comprise a computer or
digital system used to execute the software of the present invention. For
example, the method of the present invention may be performed using a
computer workstation. FIG. 1 shows a computer system 1 that includes a
monitor 3, screen 5, cabinet 7, keyboard 9, and mouse 11. Mouse 11 may
have one or more buttons such as mouse buttons 13. Cabinet 7 houses
familiar computer components, some of which are not shown, such as a
processor, memory, mass storage devices 17, and the like. Mass storage
devices 17 may include mass disk drives, floppy disks, Iomega.RTM. ZIP.TM.
disks, magnetic disks, fixed disks, hard disks, CD-ROMs, recordable CDs,
DVDs, tape storage, reader, and other similar media, and combinations of
these. A binary, machine-executable version, of the software of the
present invention may be stored or reside on mass storage devices 17.
Furthermore, the source code of the software of the present invention may
also be stored or reside on mass storage devices 17 (e.g., magnetic disk,
tape, or CD-ROM).
FIG. 2 shows a system block diagram of computer system 1 used to execute
the software of the present invention. As in FIG. 1, computer system 1
includes monitor 3, keyboard 9, and mass storage devices 17. Computer
system 1 further includes subsystems such as central processor 102, system
memory 104, input/output (I/O) controller 106, display adapter 108, serial
port 112, network interface 118, and speaker 120. The invention may also
be use with computer systems with additional or fewer subsystems. For
example, a computer system could include more than one processor 102
(i.e., a multiprocessor system) or a system may include a cache memory.
Arrows such as 122 represent the system bus architecture of computer system
1. However, these arrows are illustrative of any interconnection scheme
serving to link the subsystems. For example, speaker 120 could be
connected to the other subsystems through a port or have an internal
direct connection to central processor 102. Computer system 1 shown in
FIG. 2 is but an example of a computer system suitable for use with the
present invention. Other configurations of subsystems suitable for use
with the present invention will be readily apparent to one of ordinary
skill in the art.
A system including a computer or other programmed machine executing
electronic design automation (EDA) software is used in the design of
integrated circuits. EDA software tools include schematic editors,
performance estimation software, circuit simulators, layout editors,
design rule checkers, parasitic extractors, and many others. In a
preferred embodiment, the techniques of the present invention are
implemented in an EDA software program and executed on a computer. The
software of the present invention provides performance estimation and
verification of integrated circuits. The software may be stored on a mass
storage device such as a disk drive or other computer readable medium, and
then loaded (partially or entirely) into the memory of the computer for
execution.
FIG. 3 shows a design flow for the design of an integrated circuit. This
process may be used to design of a deep-submicron integrated circuit. In
step 303, the design of circuitry and logic gates for the integrated
circuit is defined. A circuit or logic design engineer defines the
integrated circuit by inputting a schematic, specifying the logic using a
high level design language (e.g., VHDL or Verilog), or otherwise
synthesizing the logic. The result is a netlist file containing components
and connections between the components. Interconnections between the
components are referred to as nets. The netlist file can also be used to
estimate performance of the circuitry and verify proper functionality of
the logic. For example, a Spice file can be created from the netlist. A
circuit simulator such as Spice uses the Spice file to estimate the timing
of the circuity.
In step 308, a layout for the integrated circuit is created. The layout can
be manually generated or automatically generated. The layout is typically
contained in a database file such as a GDSII format file. The layout
contains polygons and geometries on various layers that are used to
generate the mask set for fabricating the integrated circuit. In step 312,
parasitic and other parameters affecting circuit performance are extracted
from the layout. Before the layout is prepared, the design engineer cannot
be certain of what the parasitic capacitance and resistance the nets will
be. Using the layout, the lengths, widths, area, and sizes of various
circuit paths are measured. The capacitance and resistance parameters for
a process technology are defined in a technology model file. Using these
process parameters and the circuit path information, the parasitic
capacitances and resistances are calculated. Parasitic capacitance and
resistance creates propagation delays based on resistance-capacitance (RC)
delay.
In step 317, the parasitic capacitances and resistances are put into the
netlist or Spice file. This approach is referred to as backannotating the
parasitics into the simulation file. The circuit simulator analyzes and
estimates the performance of the circuitry with the parasitic resistance
and capacitance information. In step 320, the design engineer looks at the
performance estimates to see whether they meet the performance targets. If
not, the design engineer may need to make changes to the circuit or logic
design or layout. If the performance targets are met, the integrated
circuit design can be fabricated.
Although the techniques may be applied with any process technology, in an
embodiment, the invention specifically handles CMOS technology. CMOS
technology makes use of PMOS and NMOS transistors. A MOS transistor has
drain, gate, source, and substrate or well connections. A size of a MOS
transistor is defined by its gate width (W) and channel length (L). The
principles of the invention are applicable to designs using technologies
other than MOS transistor technology by analogy. For example, an NMOS
transistor has a source and a drain which are analogous to the collector
and emitter of a npn bipolar transistor.
Some factors to consider when designing integrated circuit is that with
advances in process technology, integrated circuits continue to become
smaller and faster. Channel lengths of transistors are much less than one
micron. In fact, integrated circuits are being designed with transistors
having channel lengths in the range from about 0.18 microns to 0.35
microns. And, in the future, transistors will undoubtedly have even
shorter channel lengths. The channel length is also referred to as "L
effective" or Leff. The characteristics and performance of
short-channel-length transistors are governed in part by what are known as
short channel effects. For long channel length transistors such as those
with channel lengths greater than one micron, the short channel effects
are largely negligible compared to the basic transistor characteristics.
However, for short channel transistors, the short channel effects are
significant and become more of a dominant factor in the performance. Short
channel effects are modeled using somewhat complex equations, and
consideration of short channel effects generally requires more computing
time.
As process technology advances, integrated circuits generally become
smaller. More transistors and circuits are being placed on a single chip.
Consequently, there are a greater number of circuit paths within the
integrated circuit for which the performance needs to be considered. And,
to make the task more complicated, some of the paths may be dependent on
other paths. To estimate the performance of the integrated circuit, each
of the various paths needs to be identified and analyzed. The performance
of these circuit paths are compared against the target of expected
performance for the integrated circuit. As the number of circuit paths
increase, there will be more paths to check, and this will increase the
computing time.
A typical integrated circuit system can be divided into a number of
functional blocks ranging in size from about 50,000 to over 500,000
transistors. During the initial phases of the design process, integrated
circuit designers create functional blocks with estimated resistive and
capacitive interconnect models. Later on in the design cycle, accurate
netlists for the functional blocks may be extracted from layout geometry.
Extracted netlists are typically very large. For example, a
500,000-transistor design may contain from 3 million to 5 million devices
(including MOSFETs, resistors, and capacitors) after extraction.
Therefore, when designing a modem integrated circuit, it is important to
consider short-channel or deep-submicron transistor effects and
interconnect behaviors to obtain an accurate performance estimate. It is
important to consider all the critical circuit and performance paths. And,
it is important that these performance estimates be done efficiently to
minimize processing time of the system.
FIG. 4A shows a flow diagram for a technique of the invention to estimate
the performance of an integrated circuit. An example of computer software
that may be used to perform performance estimation of integrated circuits
is the DynaBlock.TM. software. A source code listing in the C++
programming language is provided in the microfiche appendix. Other
examples of performance estimation software include DynaCore.TM.,
DynaRAM.TM., and DynaCell.TM.. The technique of the present invention
includes areas from logic minimization to automated test pattern
generation (ATPG), switch-level analysis simulation, and graph
isomorphism.
In step 404, the invention takes as input either a prelayout or extracted
netlist for a design. The input also includes boundary information such as
inputs, outputs, clocks, input arrival time windows, and output required
time windows and clock timing information. Additionally, the user can
specify input waveform information, such as rise and fall slew rates, and
second-order rate of change of slew information. This second-order
information allows the tool to model the input waveform very accurately.
Since the input waveform may affect the performance of the integrated
circuit, the user can specify the input waveform and evaluate its effect
on performance.
In step 409, the netlist is partitioned into strongly coupled components
(SCCs), which are fundamental units of analysis. One SCC may also be
referred to as one partition. Strongly coupled components typically range
in size from, for example, 5 to 2000 transistors. Strongly coupled
components are analyzed in level order, and logic functions are derived
for the outputs of the strongly coupled components including the effect of
charging and discharging times. Strongly coupled components are then
classified as combinational or state holding. The logic functions are
represented using a modification of ordered-binary-decision diagrams
(OBDDs).
In step 414, the logic functions are used derive a set of sensitizing
vectors for each SCC output. During the sensitization process, great care
is taken to generate true vectors that do not cause a conflict or exercise
"sneak" paths. A conflict occurs when there are simultaneous charging and
discharging paths in the SCC. Conflicting or false paths cause problems
during simulation because they lead spurious (usually high) delay results.
The result of the sensitization process is a set of vectors for the
slowest and fastest input sequences for each output of a strongly coupled
component, taking into account the state-dependent behavior of the SCC.
The sensitization process may generate a large number of vectors,
especially for strongly coupled circuits such as barrel shifters and wide
multiplexers. A two-level logic minimization algorithm is utilized to
reduce the vector set. The minimization algorithm models the delay of a
term to obtain a reduced set of delay vectors.
Subsequently, in step 419, waveform stimulus is generated for the strongly
coupled components taking into account the arrival time windows at a
strongly coupled component. Each strongly coupled component is simulated
in level order. Input waveforms are modeled using a three-coefficient
piecewise linear function.
In step 424, the user simulates the circuitry. The technique of the
invention allows the user to choose among different simulation techniques
providing the designer trade off between run time and accuracy. For
example, some of the simulation techniques the user can choose include the
high performance simulation technique of the invention, commercially
available Spice software, and commercially available piecewise linear
simulation. The simulation is performed "in-place," to preserve the exact
driver and load information for the strongly coupled component.
The simulation technique of the invention performs output data reduction
and circuit equation reduction to speed up simulation and reduce memory
consumption without sacrificing accuracy. A two-terminal capacitor model,
such as a BSIM3 version 3 capacitor model, is used to speed up simulation
of load devices. The BSIM user's guide is incorporated by reference.
Output delays and output waveform shape coefficients are derived from the
simulation and this information is passed to the next strongly coupled
component in level order. Since dynamic simulation is utilized during the
delay calculation process, the present invention permits the accurate
modeling of the effects of coupling capacitance, simultaneous-switching,
and waveform shape.
A technique of the invention is to maintain a database 431 of strongly
coupled components and their associated characterization information
during its operation. Using this technique reduces the execution time of
the software. Before a strongly coupled component is simulated, a database
search is performed to identify a match based upon topology, load and
input arrival, and slew. If a match is found in the database, simulation
can be avoided completely. For data-path circuits such as adders,
multipliers, and comparators, the time saved using this method can be
enormous. When a run is completed, the database is stored on disk.
Subsequent reruns of the software can utilize the information in the
database. For example, during the design phase, as the designer makes
modifications to the design and reruns the software, only the strongly
coupled components that were not matched in the database are resimulated.
This incremental recharacterization feature enables completing performance
verification of multimillion-transistor designs quickly.
FIG. 4B shows a more detailed diagram of the flow of the invention. The
steps in the flow are clock network analysis 451, partition into SCCs 454,
check each SCC for match in the model database 457, function generation
and state point identification 460, strong node identification 464, don't
care expansion 467, vector generation 469, waveform or stimulus generation
472, simulation 475, and model generation 477. More detail about these
steps are provided in the source code appendix and are also discussed
below. Steps 451, 454, 457, 460, and 464 are portions of circuit
partitioning 409. Steps 467 and 469 are portions of binary vector
generation 414.
Circuit Partitioning
In the invention, circuit partitioning is performed using a divide and
conquer approach where the circuitry is broken into smaller groupings of
circuit elements. These groupings of circuit elements are called strongly
coupled components or SCCs. The partitioned circuit elements are analyzed
and evaluated. The results of the analysis of these partitioned circuit
elements are combined to determine the total result for the entire circuit
block or integrated circuit. Depending on how the circuit elements are
partitioned, the analysis will be performed more efficiently and
accurately. A technique of the invention will partition a circuit
description containing transistors, interconnect resistors, interwire
coupling capacitors, grounded capacitors, and other active components. The
method includes the steps of initial grouping of circuits by clock network
analysis, tight coupling analysis, and state-point identification.
Clock Network Analysis
To estimate the performance of an integrated circuit, the clock network is
identified. Knowing all the clock nets permits identification of
state-holding subcircuits and permits setup and hold checks to be
performed on clocked logic such as latches and footed and footless domino
logic. It also enables setup and hold timing verification checks to be
performed on primary outputs. Previous methods for tracing the clock tree
involve looking for topological matches for inverters, buffers, and other
gates along the clock tree. A major drawback of these techniques is that
if the user changes the topology, the clock tree is no longer recognized
and timing analysis is inhibited.
In the invention, starting from the user-identified clock starting points,
the clock network is traced by Boolean analysis. From each user-defined
clock starting point, a forward trace is performed. The forward trace
identifies the channel-connected components (CCCs) connected to the clock
starting point. A channel-connected component is defined to be the set of
nodes and attached transistors that are strongly reachable by tracing or
following source-drain connections. In the invention, this definition
includes reachability through resistors and also includes any capacitors
connected to the nodes that are in the channel-connected component. How
CCCs are found is discussed below.
A Boolean logic function is obtained for each of the outputs of the CCC.
Subsequently, a Boolean test is applied to each output of the CCC to
determine whether the clock signal propagates to the output or not. If the
clock signal propagates to an output, the forward trace is repeated on the
output. Because the clock network is identified by Boolean analysis, even
if there are later topological changes in the clock network, the clock
tree will still be recognized because it has been represented
functionally.
The clock input to the CCC to be analyzed is called c. A complement of the
clock signal is denoted by c or c'. The function of the output to be
tested is denoted by f. First, the terms of f that depend on the clock c
are identified by calculating the following expression:
f.sub.c.sym.c =(f.sub.c.sym.f.sub.c)^f
The subscript denotes the cofactor operation. In order for the output to be
a clock signal, the output depends on c and will be either positive unate
or negative unate with respect to c. Therefore the test is:
(f.sub.c.sym.c.vertline..sub.c.noteq.0{character
pullout}f.sub.c.sym.c.vertline..sub.c =0){character
pullout}(f.sub.c.sym.c.vertline..sub.c =0{character
pullout}f.sub.c.sym.c.vertline..sub.c.noteq.0)
TABLE 1
Clock Network Analysis
1. Start from a user specified clock net c.
2. Identify all CCCs connected to the clock net c.
3. Calculate the logic functions for each output of each CCC
connected to the clock net.
4. For each output of each CCC connected to the clock net,
test if the output depends on c and is either positive
unate or negative unate with respect to c. An output is
considered positive unate with respect to c if changing
c from 0 to 1 (while keeping other inputs constant)
always causes the output to either remain unchanged, OR,
change from 0 to 1. An output is considered negative
unate with respect to c if changing c from 0 to 1
(while keeping other inputs constant) always causes
the output to either remain unchanged, OR,
change from 1 to 0.
5. Mark each unate output as a clock net. For each unate
output, repeat the clock network analysis above,
until all nodes are examined.
Tight Coupling Analysis
Tight coupling analysis is a technique of identifying circuit structures
that behave as a single logical unit. For partitioning of a circuit with
MOS transistors, a channel-connected component or CCC is defined to be the
set of nodes and attached transistors that are strongly reachable by
tracing or following source-drain connections. In the invention, this
definition includes reachability through resistors, and also includes any
capacitors connected to the nodes that are in the channel-connected
component. A first step in partitioning is to group the circuit into
channel-connected components.
FIG. 5 shows a standard CMOS inverter 505. This is an example of a
channel-connected component. Transistors 510 and 515 of the inverter are
channel-connected components. A signal can be traced from the drain to
source of transistor 510 to the drain to source of transistor 515.
FIG. 6 shows another example of a channel-connected component. All
transistors including those used to create inverter 610, and transistor
630 are channel connected. Transistor 625 is connected to the gate of
inverter 610 and is not part of the CCC of inverter 610 and transistor
630.
The behavior of a channel-connected component however cannot always be
analyzed in isolation. Some circuits have feedback paths. The presence of
feedback and interaction between channel-connected components can result
in a combined behavior that is significantly different from the behavior
of individual components. For example, large coupling capacitors between
two channel-connected components can also significantly alter the timing
behavior of the circuit.
The present invention analyzes the circuit for strong interaction between
the components using graph traversal techniques. Channel-connected
components are grouped into strongly coupled components or SCCs.
Subsequently, the nodes of a strongly coupled component are classified as
being an input, output, or internal. In addition to the traditional static
CMOS circuits, examples of SCCs include footed and footless domino logic,
differential cascode voltage switch (DCVS) logic, and similar structures
with feedback.
SCCs are formed from CCCs that have a two-way influence relationship. In
other words, if two CCCs are connected in a feedback loop they are merged
to form an SCC. FIG. 7 shows a circuit with two channel-connected
components 730 and 735. In FIG. 7, both channel-connected components 730
and 735 form a strongly coupled component 760 because the output of
component 735 influences a Boolean output of component 730, and an output
component 730 influences a Boolean output of component 735. These CCCs
will be merged together to form an SCC 760.
Table 2 summarizes a flow for a technique of the invention for partitioning
a circuit description into strongly coupled components.
TABLE 2
Circuit Partitioning
1. Identify all the channel connected components in the
circuit. A channel-connected component may be defined
to be the set of nodes and attached transistors that
are strongly reachable by tracing or following
source-drain connections. In the invention, this
definition includes reachability through resistors,
and also includes any capacitors connected to the
nodes that are in the channel-connected component.
2. Identify inputs and outputs of all channel
connected components: Gate terminals of transistors
that are not driven by any other source or drain
from within the channel connected component are
considered inputs. Nets that are connected to
the gates of transistors belonging to any other
channel connected component are considered outputs.
3. While merging is still occurring: Identify pairs
of channel connected components (CCC) that are
connected in a feedback loop. A pair of channel
connected components CCC1 and CCC2 are in a
feedback loop relationship if an output of
CCC1 drives an input of CCC2, AND, an output
of CCC2 drives an input of CCC1. Merge the transistors,
capacitors and resistors of the two CCC (CCC1
and CCC2) to form an SCC.
4. While merging is still occurring: Identify pairs of
SCCs that are connected in a feedback loop.
A pair of strongly coupled components SCC1 and SCC2
are in a feedback loop relationship if an output of
SCC1 drives an input of SCC2, AND, an output of SCC2
drives an input of SCC1. Merge the transistors,
capacitors, and resistors of the two SCCs
(SCC1 and SCC2) to form SCC3.
In step 1 of table 2, the channel-connected components (CCCs) are
identified by tracing source-drain connections for transistors. In step 2,
the inputs and outputs are identified.
In step 3, the strongly connected components are identified from these
channel-connected components. SCCs are formed from CCCs that have a
two-way influence relationship. In other words, if two CCCs are connected
in a feedback loop they are merged to form an SCC. FIG. 7 shows an example
of two CCCs with a feedback relationship. CCCs are merged into a single
SCC, such as SCC 760. SCCs will be considered and analyzed as a single
component.
In step 4, SCCs are examined to determine if additional merging is
possible. For example, SCCs generated from step 3 may have may have
additional feedback or coupling and could be combined with other SCCs. In
step 4, larger groups absorb smaller groups. This will grow the clusters
to build bigger SCCs.
When the above technique is applied to the circuit in FIG. 8, in step 1, an
inverter 820 and a transmission gate 825 will be identified as a
channel-connected component 835. Inputs and outputs are identified in step
2. In step 3, CCC 835 will be combined with inverter 837 to form a
strongly coupled component because b
