Computer-aided design and analysis of circuits and semiconductor – Nanotechnology related integrated circuit design
Reexamination Certificate
2002-05-30
2004-11-30
Do, Thuan (Department: 2825)
Computer-aided design and analysis of circuits and semiconductor
Nanotechnology related integrated circuit design
C703S002000, C716S030000, C716S030000, C716S030000
Reexamination Certificate
active
06826733
ABSTRACT:
FIELD OF THE INVENTION
The invention is related to the field of Electronic Design Automation, and more particularly, to a method of optimizing the design of an integrated circuit chip or system in the presence of uncertainty in the modeling or predictability of the design variables and functions, by reducing the number of design functions at limiting values in the final design.
BACKGROUND OF THE INVENTION
A wide variety of methods are employed in the optimization of integrated circuit designs. These techniques attempt to improve the design (i.e., to minimize some overall design cost or objective function) while meeting a set of constraints. Examples of design constraints include limits on the total silicon area occupied by the circuit, limits on the amount of power which can be consumed by the circuit, limits on the noise (i.e., unintended signals occurring on nets within the design due to such things as coupling from other wires) on any net in the design, and limits on the maximum path delay through the circuit (and hence on the maximum clock frequency and minimum clock period at which the circuit can operate). Each of these parameters may also contribute to the overall design objective function which is to be minimized. By way of example, a design objective may be to minimize (rather than to limit) the maximum path delay through the circuit, the area occupied by the circuit, the power consumed by the circuit, or some combination of these functions.
In many cases, the limits imposed by constraints are not absolute limits, but instead represent engineering judgment regarding the point beyond which the constrained function will unduly impact the correctness, reliability, performance, or other aspects of the design. Thus, these constraints are not hard, meaning that the design will fail if they are not met, and minor violations of the constraints may be acceptable. In many optimization methods, constraints are modeled as part of the objective function. In such instances, a constraint contributes nothing to the design objective if it is met, but violation of the constraint causes a large increase in the objective function, often proportional to the magnitude of the violation or to some power (e.g., the square) of the magnitude of the violation. Note that even a design objective which is to be maximized may be represented as part of an objective function to be minimized by suitable transformation, e.g., by including its negative (or for functions which are strictly greater than zero, its inverse) as part of the minimization objective. Where the ensuing description refers to minimizing an objective function it should be understood to include such transformations.
Many different methods can be used to optimize a design. Domain-specific heuristic search techniques can be used to propose a variety of small changes to a design which are expected, due to domain knowledge, to improve the objective function. One or more of these proposed change which gives the greatest reduction in the objective function is then chosen and implemented. This process is repeated until no further improvement is possible or until the processing time allowed for optimization has been exhausted.
Simulated annealing techniques optimize a system by a method analogous to process of annealing a physical material. Such methods propose a random change to a design, determine the increase or decrease in the objective function due to the change, accept all proposed changes which decrease the objective function, and only accept changes which increase the objective function according to a probability function related to the amount of increase in the objective function. This process is repeated many times, and a “temperature” parameter is slowly decreased during the optimization process, causing the probability of accepting objective function-degrading changes to decrease until, at the end, only objective function-improving changes are accepted. Further details about simulated annealing are described in U.S. Pat. No. 4,495,559 to Gelatt Jr. et al.
Numerical optimization techniques, as described, e.g., in the publication entitled “LANCELOT: A Fortran Package for Large-Scale Nonlinear Optimization” by A. R. Conn, et al., Springer-Verlag, 1992, use numerical methods to minimize an objective function represented as a function of a set of problem variables. Allowed ranges are defined for problem variables, and a set of constraints is given, each specifying that some linear or nonlinear function of some group of problem variables is less than zero (Note: any inequality constraint between functions of variables of a design can be converted to this form). The optimizer attempts to minimize the objective function subject to the imposed constraints by varying the problem variables within their allowed ranges. This type of optimization is often referred to as design tuning. Details of this technique may be found in an article entitled “Gradient-based optimization of custom circuits using a static-timing formulation” by A. R. Conn, et al., Proceedings of the 1999 IEEE/ACM Design Automation Conference. The inequality constraints are often converted to equality constraints by introducing constraint slack variables which are required to be greater than or equal to zero. For example, the following constraint (in which f and g are functions and x, y, z, u, v, and w are design variables):
f
(
x,y,z
)≧
g
(
u,v,w,x
)
can be converted to the following by the introduction of constraint slack variable s:
0
=s+f
(
x,y,z
)−
g
(
u,v,w,x
),
s≧0
In many instances, the design objective function or some component thereof, will be the maximum of some set of functions of design variables. For example, if the objective is to minimize the longest path delay in a circuit, the value to be minimized will be the maximum of the path delay over all circuit paths, where each of these delays is a function of design variables such as transistor widths and wire widths. Optimization problems with objectives of this nature are often referred to as minimax problems, the variable to be minimized is the minimax variable, and constraints involving it are called minimax constraints. In a numerical optimization framework, assume that the set of design functions involved include f
1
, . . . , fn and the associated minimax variable representing the maximum of these values is z. The problem will then be to minimize z (or some monotonically increasing function of z) subject to constraints:
z≧f
1
z≧fn
Similarly, a design objective function may include a variable to be maximized which is itself the minimum of some set of functions of design variables. Such a problem and variable are referred to as a maximin problem and variable, respectively, and can be transformed to a minimax problem and variable by negating the maximin variable and all functions constraining it. Hereinafter references to minimax problems and variables will be understood to include maximin problems and variables transformed in this manner.
There are multiple ways of modeling a design constraint or objective function involving the maximum (or minimum) delay through a circuit. One method is to identify every possible path through the integrated circuit and to constrain the delay of each identified path to be less than a limit. But the number of paths through a circuit can be very large, potentially growing exponentially with the size of the circuit, thus introducing an enormous number of constraints into the optimization problem.
An alternative method is to use a node-oriented static timing analysis algorithm as described, e.g., in U.S. Pat. No. 4,263,651 to Donath et al. Therein, a timing graph is created with nodes representing points in the network at which digital signal transitions (typically voltage transitions between ground and the supply voltage Vdd) occur and edges representing the dependencies between these nodes, so that an edge is present from node X to node Y if and only if, under some circumstances, a signal transition at X can directly cause a signal transition at Y.
Bai Xiaoliang
Hathaway David J.
Strenski Philip N.
Visweswariah Chandramouli
Do Thuan
International Business Machines - Corporation
Schnurmann H. Daniel
LandOfFree
Parameter variation tolerant method for circuit design... does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Parameter variation tolerant method for circuit design..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Parameter variation tolerant method for circuit design... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-3295473