Delay estimation for restructuring

Details Delay estimation for restructuring Delay estimation for restructuring

1997-03-14

2004-01-06

Teska, Kevin J. (Department: 2768)

Reexamination Certificate

active

06672776

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, target 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.


REFERENCES:
patent: 5282148 (1994-01-01), Poirot et al.
patent: 5500808 (1996-03-01), Wang
G. Hachtel and F. Somenzi, “Logic Synthesis and Verification Algorithms”, Kluwer Academic Publishers, 1996.
G. De Micheli, “Systhesis and Optimization of Digital Circuit”, McGraw-Hill, Inc., 1994.
J. Mohnke and S. Malik, “Limits of using Signatures for Permutation Independent Boolean Comparison”, Proceedings of the ASP-DAC' 95/CHDL' 95/VLSI' 95 Asia and South Pacific Design Automation Conference, Aug. 29-Sep. 1, 1995.
R. Bryant, “Graph-Based Algorithms for Boolean Function Manipulation”, IEEE Transactions on Computers, vol. C-35, No. 8 p. 670, Aug. 1986.
I. Pomeranz and S. Reddy, “On Diagnosis and Correction of Design Errors”, IEEE/ACM International Conference on Comput

Affiliated with

Also associated with

Rating

Delay estimation for restructuring 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, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Delay estimation for restructuring will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFUS-PAI-O-3187786