Computer-aided design and analysis of circuits and semiconductor – Nanotechnology related integrated circuit design
Reexamination Certificate
1998-10-08
2001-09-11
Smith, Matthew (Department: 2825)
Computer-aided design and analysis of circuits and semiconductor
Nanotechnology related integrated circuit design
C716S030000, C703S002000
Reexamination Certificate
active
06289490
ABSTRACT:
This invention was made with the support of the National Science Foundation and the Air Force Office of Scientific Research. The U.S. Government has certain rights in this invention.
FIELD OF THE INVENTION
The present invention generally relates to integrated circuits, and more specifically to a method that uses a dominant time constant of an integrated circuit to optimize the circuit with respect to certain properties.
BACKGROUND
Because of the rapid growth rate of the electronics industry, each year integrated circuits are required to be smaller, more dense, and faster than before. Integrated circuits can be extremely complex, with millions of transistors on a single chip. Typically one needs to minimize some property of the circuit—for example, the size of the circuit or the power dissipated by the circuit—while preserving a rapid response time. Optimizing the circuit in the face of the extreme complexity of the circuit is therefore a difficult problem.
The integrated circuit constantly undergoes transitions in which some of the active elements of the circuit change state from a logical “low” to a logical “high,” and other elements change from “high” to “low.” After one such transition takes place, some time must elapse for the remainder of the circuit to equilibrate before another transition can occur. The amount of time that must elapse is the response time of the circuit, and this response time in general depends on the transition. When attempting to optimize the circuit, the transition corresponding to the slowest response time, or else several transitions simultaneously, are considered.
Conventional approaches to the optimization problem estimate the response time of the circuit by the Elmore delay of one or more transitions of the circuit. Such approaches are disclosed, for example, in Pillage, Ratzlaff, and Gopal, U.S. Pat. No. 5,379,231, and in Dunlop and Fishburn, U.S. Pat. No. 4,827,428. Sizes of elements of the circuit are optimized with respect to a certain property of the circuit, while keeping the Elmore delay suitably small. A severe limitation of these methods, however, is that the Elmore delay cannot be used for a circuit that has a non-tree topology. In other words, if the circuit has loops, the above methods cannot be used.
A typical solution is to simply ignore the non-tree nature of the circuit, and use the Elmore delay methods anyway. In this approach, circuit interconnects that form loops in the circuit are ignored during the optimization procedure. However, as the circuits get smaller and smaller, crosstalk between the elements becomes increasingly import ant. Because of the crosstalk, the circuits effectively comprise loops, even if the circuits are manufactured with an intended tree topology. Pre sent methods do not allow the crosstalk, or any other loops, to be taken into account when designing an optimum layout of the circuit.
Another disadvantage of the conventional methods is that the topology of the circuit must be fixed in advance, and cannot be determined as part of the optimization procedure. It is desirable to have a method for designing integrated circuits that not only optimizes the sizes of the elements, but determines which connections are necessary and which should be omitted in the optimum case. Such flexibility is not possible when the Elmore delay methods are used.
OBJECTS AND ADVANTAGES
It is therefore a primary object of the present invention to provide a method for finding an optimum design for a circuit, where the method is effective even when the circuit has a non-tree topology. It is another object of the invention to provide a method for finding an optimum topology of the circuit. Other objects of the invention are to provide an optimization method wherein a plurality of transitions of the circuit can be considered simultaneously, and wherein constraints on the physical layout of the circuit can be incorporated. These objects yield a method that has the advantage that circuits may be more accurately modeled and their design more effectively optimized, whereby integrated circuits of improved performance may be manufactured.
SUMMARY
A method for optimizing an integrated circuit employs a dominant time constant of a transition of the circuit as an estimate for the response time of the circuit. A physical layout of the circuit is characterized in terms of design parameters. The design parameters relate, for example, to sizes of elements of the circuit, or to spacings between the elements. The method comprises the step of finding the values of the design parameters that optimize a property of the circuit while simultaneously keeping the dominant time constant below some pre-selected maximum t
max
. The property optimized is typically a size of the circuit, an energy dissipated by a transition of the circuit, or the dominant time constant itself.
The above step of optimizing the property while keeping the dominant time constant below t
max
presents a complicated problem in linear algebra that has only in recent years become tractable. Recently developed mathematical tools have made it possible to carry out the above step using a conventional digital computer. The mathematical tools are known as semi-definite programming and generalized eigenvalue minimization. To use these tools, the circuit is modeled by a conductance matrix G and a capacitance matrix C, where matrices G and C are affine functions of the design parameters.
The optimization method can be used even when the circuit has a non-tree topology. Furthermore, when the design parameters comprise variables that relate to sizes of elements of the circuit, the topology of the circuit is optimized by the optimization method, the optimum topology being dictated by those elements whose optimum size is zero.
In some embodiments, a plurality of transitions is considered. In these embodiments, the optimization method comprises the step of optimizing the property while requiring that dominant time constants for a set of transitions are all simultaneously less than the maximum value t
max
. In some embodiments, the design parameters are subject to design constraints.
REFERENCES:
patent: 4630219 (1986-12-01), DiGiacomo et al.
patent: 4827428 (1989-05-01), Dunlap et al.
patent: 5303161 (1994-04-01), Burns et al.
patent: 5379231 (1995-01-01), Pillage et al.
patent: 5453991 (1995-09-01), Suzuki et al.
patent: 5758148 (1998-05-01), Lipovski
patent: 5818729 (1998-10-01), Wang et al.
patent: 5910899 (1999-06-01), Barrientos
patent: 6064809 (1998-06-01), Braatz et al.
Vandenberghe, V. et al., Semidefinate Programming, SIAM Review, 38, pp. 49-95, 1996.
Boyd, Stephen et al., Method of Centers for Minimizing Generalized Eigenvalues, Linear Algebra and Appl., 188, pp. 63-111, 1993.
Vandenberghe, V. et al., Optimizing Dominant Time Constant in RD Circuits, IEEE Transactions in Computer Aided Design, 17, pp. 110-125, Feb. 1998.
Optimal Wire and Transistor Sizing for Circuits with Non-Tree Topolgy, Proceedings of ICCAD '97, Nov. 9-13, 1997 in San Jose, California, pp. 252-259.
Boyd Stephen P.
El Gamal Abbas
Vandenberghe Lieven
Garbowski Leigh Marie
Lumen Intellectual Property Services
Smith Matthew
The Board of Trustees of the Leland Stanford Junior University
LandOfFree
Optimization of integrated circuit properties through... does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Optimization of integrated circuit properties through..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Optimization of integrated circuit properties through... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-2438830