Computer-aided design and analysis of circuits and semiconductor – Nanotechnology related integrated circuit design
Reexamination Certificate
1999-12-16
2003-04-01
Smith, Matthew (Department: 2825)
Computer-aided design and analysis of circuits and semiconductor
Nanotechnology related integrated circuit design
C716S030000, C716S030000, C716S030000, C716S030000
Reexamination Certificate
active
06543037
ABSTRACT:
TECHNICAL FIELD
This invention relates to a method, article of manufacture, and apparatus for logic synthesis and mapping a technology-independent network to a technology-dependent network in the design of integrated circuits. More particularly, this invention relates to estimating delays of networks.
BACKGROUND
In the design of integrated circuits, there is a tradeoff between competing design goals: area of the circuit, critical path delay (speed) of the circuit, testability of the circuit, and power consumption of the circuit. The rapidly growing complexity in very large scale integrated (VLSI) circuits and the sheer mass of detail in VLSI designs necessitates the use of automated synthesis tools in order to design an optimized circuit which balances all of these design constraints. Logic synthesis is described in
Logic Synthesis and Verification Algorithms
, by Gary D. Hachtel and Fabio Somenzi, and in
Synthesis and Optimization of Digital Circuits
, by Giovanni De Micheli, the disclosures of which are hereby incorporated by reference.
Automated design systems are used in converting logic designs to specific circuits in the production of application specific integrated circuits (ASICs). This typically involves mapping the logic design, called a “technology-independent circuit” (or network), into one or more logic gates in a pre-designed set of gates called a technology library. The resulting circuit may be variously called “technology-dependent”, “technology-mapped”, or simply “mapped”.
The technology library depends on the manufacturer and the target technology selected.
For example, et technologies might include CMOS (complementary metal-oxide-semiconductor), NMOS (n-type metal-oxide-semiconductor), PMOS (p-type metal-oxide-semiconductor), TTL (bipolar transistor-to-transistor logic), and ECL (emitter-coupled logic). Further differentiation among target technologies may be based on minimum feature size, resulting in, for example, a 0.25 micron CMOS technology, a 1.0 micron CMOS technology, and a 2.0 micron CMOS technology.
Initially, the logic design may be specified in the form of Boolean equations or an HDL (hardware description language) description in a language such as Verilog or VHDL (Very High Speed Integrated Circuits Hardware Description Language). The automated design system generates a technology-independent, unmapped network that is a directed graph where the vertices represent logic gates and the edges represent the nets connecting the gate outputs to gate inputs. This technology-independent network is optimized and mapped, producing a technology-mapped network. Typically, some restructuring is performed in order to meet specified design criteria (delay times, area, etc.). This is generally a repetitive optimizing process that involves countless changes to the logic network, with many recalculations of various network parameters after each change. One such parameter is speed, which is related to the time required for a change in one of the inputs to travel through the network to produce a change in one of the outputs.
Most target technology libraries contain timing information for various cells in the library, which can be used to accurately determine the delays in a mapped network. However, the restructuring is performed at the technology-independent level, and as stated above, many changes may be made to the logic network. Mapping the network and recalculating delays after every change would dramatically increase the computation required, and for larger, more complex circuits, this would render the task intractable.
Thus, automated design systems typically estimate the delay from the technology-independent network, without mapping each change to determine the effect of the change on the timing. One method of estimating time delay in a technology-independent network is to determine the length of the longest dependency chain present in the network. The dependency chain is thought of as the “critical path”, and its length as the “critical path delay”. This critical path is the limiting factor in the speed of the circuit, and the restructuring process focuses on reducing the critical path delay in order to meet timing requirements. Typically, a fixed delay is assigned to each of the logic vertices, and the estimated time delay is a function of the delays of the vertices in the critical path. This method has the advantage of simplicity, but fails to account for the complexity of the functions, the effect of the mapping and optimization on the mapped network time delay, or the characteristics of the target technology. Often, the estimated delays do not accurately characterize the actual delays of the mapped network.
Another method, described in U.S. Pat. No. 5,500,808, issued Mar. 19, 1996, attempts to include the fanins and fanouts for each logic node in estimating the delay of the unmapped network. Other methods have been used, with varying degrees of success and computational tractability.
Furthermore, restructuring programs generally focus on the critical path. Because the technology-independent network has estimated time delays and may not even have the same structure as the technology-mapped network, the critical path of the technology-independent network may not be the same as the critical path of the technology-mapped network. This may result in poor performance of the restructuring program.
Thus, there is a need for a method and apparatus for estimating time delays with a high degree of accuracy and which is not so complex as to require substantially increased computation, and for improved critical path selection to guide the restructuring process.
SUMMARY OF THE INVENTION
Briefly, therefore, this invention provides for a method, article of manufacture, and apparatus for estimating delays of networks. An automated design system comprises a computer configured to identify a critical path in a network, calculate a delay for the technology-mapped version of the network, calculate a delay for the technology-independent version of the network, calculate a scale factor from the technology-mapped and technology-independent delays, and apply the scale factor to all the delays in the technology-independent network.
In an embodiment of the invention, an automated design system processes a circuit which has been mapped to a chosen technology. The system identifies a critical path in the technology-mapped circuit and computes the critical path delay using information from the chosen technology library. The technology-mapped circuit is then unmapped into a technology-independent circuit using inverters and two-input representative functions such as NAND. The delays of an inverter cell and of a two-input representative function cell are determined using the delay information of such cells from the chosen technology library. The automated design system then identifies a critical path in the technology-independent circuit based on the critical path in the technology-mapped circuit, and computes its delay using the inverter and representative function cell delays. The technology-mapped critical path delay is divided by the technology-independent critical path delay to obtain a scale factor, which is applied to all the delays in the technology-independent circuit to produce estimated delays.
The advantages and further details of the present invention will become apparent to one skilled in the art from the following detailed description when taken in conjunction with the accompanying drawings.
REFERENCES:
patent: 5406497 (1995-04-01), Altheimer et al.
patent: 5475605 (1995-12-01), Lin
Belkhale Krishna
Li Hong
Limqueco Johnson Chan
Varma Devadas
Cadence Design Systems Inc.
Do Thuan
Glenn Michael A.
Glenn Patent Group
LandOfFree
Delay estimation for restructuring the technology... does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Delay estimation for restructuring the technology..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Delay estimation for restructuring the technology... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-3060487